Codeforces 887D Ratings and Reality Shows
最编程
2024-08-07 09:08:09
...
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long
using namespace std;
const int N = 3e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;
const double PI = acos(-1);
int Log[N];
struct ST {
LL dp[N][20]; int ty;
void build(int n, LL b[], int _ty) {
ty = _ty;
for(int i = -(Log[0]=-1); i < N; i++)
Log[i] = Log[i - 1] + ((i & (i - 1)) == 0);
for(int i = 1; i <= n; i++) dp[i][0] = ty * b[i];
for(int j = 1; j <= Log[n]; j++)
for(int i = 1; i+(1<<j)-1 <= n; i++)
dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
}
inline LL query(int x, int y) {
int k = Log[y - x + 1];
return ty * max(dp[x][k], dp[y-(1<<k)+1][k]);
}
};
int n, a, b, c, d, start, len;
int t[N], q[N];
LL sum[N];
ST rmq;
int main() {
cin >> n >> a >> b >> c >> d >> start >> len;
for(int i = 1; i <= n; i++) {
cin >> t[i] >> q[i];
if(q[i]) sum[i] = sum[i - 1] + c;
else sum[i] = sum[i - 1] - d;
}
t[0] = -1;
rmq.build(n, sum, -1);
LL prefix = start;
int ans = -1;
for(int i = 0; i <= n; i++) {
if(i) {
if(q[i]) prefix += a;
else prefix -= b;
}
if(prefix < 0) break;
int p = lower_bound(t + 1, t + 1 + n, t[i] + 1 + len) - t - 1;
if(p <= i) {
ans = t[i] + 1;
break;
} else {
int L = i + 1, R = p;
LL mn = rmq.query(L, R) - sum[i];
if(prefix + mn >= 0) {
ans = t[i] + 1;
break;
}
}
}
printf("%d\n", ans);
return 0;
}
/*
*/