#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define rb(x) ((x)&(-(x)))
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const bool debug = 0;
const int MAXN = 1000055;
const int MAXM = 1000055;
struct BIT {
ll d[MAXN];
void upd(int x, ll r) {
for(x += 5; x < MAXN; x += rb(x))
d[x] += r;
}
ll get(int x) {
ll r = 0; for(x += 5; x; x -= rb(x))
r += d[x];
return r;
}
ll get(int s, int e) { return s > e ? 0 : get(e) - get(s-1); }
} bit;
struct NOD {
NOD(int i, int s, int e)
: i(i), s(s), e(e) {}
int i, s, e;
};
struct SEG {
ll ds[MAXN*3];
bitset<MAXN*3> dz;
void prop(int i, int s, int e) {
if(dz[i]) {
ds[i] = 0;
if(s != e) dz[i<<1] = dz[i<<1|1] = true;
dz[i] = false;
return;
}
if(s == e) return;
ds[i] = 0;
if(!dz[i<<1]) ds[i] += ds[i<<1];
if(!dz[i<<1|1]) ds[i] += ds[i<<1|1];
}
void updz(int i, int s, int e, int p, int q) {
prop(i, s, e); if(q < p || e < p || q < s) return;
if(p <= s && e <= q) {
dz[i] = true;
prop(i, s, e);
return;
}
int m = (s+e) >> 1;
updz(i<<1, s, m, p, q);
updz(i<<1|1, m+1, e, p, q);
ds[i] = ds[i<<1] + ds[i<<1|1];
}
void updp(int i, int s, int e, int x, ll r) {
prop(i, s, e); if(x < s || e < x) return;
if(s == e) {
ds[i] = r;
return;
}
int m = (s+e) >> 1;
updp(i<<1, s, m, x, r);
updp(i<<1|1, m+1, e, x, r);
ds[i] = ds[i<<1] + ds[i<<1|1];
}
void upddx(int i, int s, int e, int x, ll r) {
prop(i, s, e); if(x < s || e < x) return;
if(s == e) {
ds[i] += r;
return;
}
int m = (s+e) >> 1;
upddx(i<<1, s, m, x, r);
upddx(i<<1|1, m+1, e, x, r);
ds[i] = ds[i<<1] + ds[i<<1|1];
}
ll get(int i, int s, int e, int p, int q) {
prop(i, s, e); if(q < p || e < p || q < s) return 0;
if(p <= s && e <= q) return ds[i];
int m = (s+e) >> 1;
ll ret = get(i<<1, s, m, p, q) + get(i<<1|1, m+1, e, p, q);
ds[i] = ds[i<<1] + ds[i<<1|1];
return ret;
}
ll get(int i, int s, int e, int x) { return get(1, s, e, x, x); }
void getNodes(vector<NOD> &V, int i, int s, int e, int p, int q) {
prop(i, s, e); if(q < p || e < p || q < s) return;
if(p <= s && e <= q) {
V.eb(i, s, e);
return;
}
int m = (s+e) >> 1;
getNodes(V, i<<1, s, m, p, q);
getNodes(V, i<<1|1, m+1, e, p, q);
// TODO
}
} seg;
vector<pii> PopEV[MAXM];
vector<pii> PushEV[MAXM];
ll SA[MAXN], SB[MAXM];
int FI[MAXN], GI[MAXM];
ll C[MAXN], D[MAXM];
int A[MAXN], B[MAXM];
int E[MAXN], F[MAXM];
ll Delta;
int N, M;
int main() {
ios::sync_with_stdio(false);
cin >> N >> M;
for(int i = 1; i <= N; i++)
cin >> A[i] >> C[i] >> E[i];
for(int i = 1; i <= M; i++)
cin >> B[i] >> D[i] >> F[i];
for(int i = 1; i <= N; i++) SA[i] = SA[i-1] + A[i];
for(int i = 1; i <= M; i++) SB[i] = SB[i-1] + B[i];
for(int i = 1; i <= N; i++)
FI[i] = int(upper_bound(SB, SB+M+1, C[i]-SA[i])-SB) - 1;
for(int i = 1; i <= M; i++)
GI[i] = int(upper_bound(SA, SA+N+1, D[i]-SB[i])-SA) - 1;
for(int i = 1; i <= N; i++) if(0 <= FI[i] && E[i]) {
if(0 < E[i]) {
PopEV[FI[i]+1].eb(i, E[i]);
bit.upd(i, E[i]);
} else {
Delta += E[i];
if(FI[i] < M) PushEV[FI[i]].eb(i, -E[i]);
}
}
for(int i = 1; i <= M; i++) if(0 <= GI[i] && F[i]) {
if(0 < F[i]) PushEV[i-1].eb(GI[i], F[i]);
else {
Delta += F[i];
if(GI[i] < N) {
PopEV[i].eb(GI[i]+1, -F[i]);
bit.upd(GI[i]+1, -F[i]);
}
}
}
if(debug) {
printf("N=%d, M=%d\n", N, M);
for(int i = 1; i <= N; i++) printf("%d ", FI[i]);
puts("");
for(int i = 1; i <= M; i++) printf("%d ", GI[i]);
puts("");
}
for(int j = 1; j <= M; j++) {
for(auto &ev : PushEV[j-1]) {
int i, ei; tie(i, ei) = ev;
Delta += ei;
int s = i+1, e = N+1; for(int m; s < e;) {
m = (s+e) >> 1;
if(seg.get(1, 1, N, i+1, m) < ei) s = m+1;
else e = m;
}
ll t = seg.get(1, 1, N, i+1, s-1);
seg.updz(1, 1, N, i+1, s-1);
if(s <= N) seg.upddx(1, 1, N, s, t-ei);
}
for(auto &ev : PopEV[j]) {
int i, ei; tie(i, ei) = ev;
bit.upd(i, -ei);
seg.upddx(1, 1, N, i, ei);
if(debug) {
printf("j=%d, pop %d %d\n", j, i, ei);
}
}
if(debug) {
printf("j=%d / %lld\n", j, Delta);
for(int i = 1; i <= N; i++) printf("%lld ", bit.get(i, i));
puts("");
for(int i = 1; i <= N; i++) printf("%lld ", seg.get(1, 1, N, i));
puts("");
}
}
cout << bit.get(1, N) + seg.get(1, 1, N, 1, N) + Delta << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2346 ms |
76252 KB |
Output is correct |
| 2 |
Incorrect |
1961 ms |
76452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
47784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
47784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
47784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
47784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
47784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2346 ms |
76252 KB |
Output is correct |
| 2 |
Incorrect |
1961 ms |
76452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2346 ms |
76252 KB |
Output is correct |
| 2 |
Incorrect |
1961 ms |
76452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
