#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define ll long long
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(x) [&](decltype(x) _x) {cerr << #x << " = " << _x << endl; return _x;}(x)
using pii = pair<int, int>;
const ll inf = 1ll << 60;
template <typename T, typename U>
ostream& operator<<(ostream& out, pair<T, U> p) {
return out << "(" << p.f << ", " << p.s << ")";
}
template <typename T, typename = decltype(begin(declval<T>()))>
typename enable_if<!is_same<T, string>::value, ostream&>::type operator<<(ostream& out, T x) {
string dlm = "";
out << "{";
for(auto i : x) {
out << dlm << i;
dlm = ", ";
}
return out << "}";
}
struct segnode {
signed tl, tr;
int v, lz;
segnode *lc, *rc;
void push() {
signed tm = (tl + tr) / 2;
if(!lc) lc = new segnode{tl, tm};
if(!rc) rc = new segnode{tm, tr};
if(!lz) return;
v += lz;
lc->lz += lz;
rc->lz += lz;
lz = 0;
}
void update(int i, int x) {
if(tl + 1 == tr) {
v = x;
lz = 0;
return;
}
push();
int tm = (tl + tr) / 2;
if(i < tm) lc->update(i, x);
else rc->update(i, x);
lc->push();
rc->push();
v = min(lc->v, rc->v);
}
void add(int ul, int ur, int x) {
if(ul >= tr || ur <= tl) return;
if(ul <= tl && ur >= tr) {
lz += x;
return;
}
push();
lc->add(ul, ur, x);
rc->add(ul, ur, x);
lc->push();
rc->push();
v = min(lc->v, rc->v);
}
int get(int i) {
push();
if(tl + 1 == tr) return v;
int tm = (tl + tr) / 2;
if(i < tm) return lc->get(i);
return rc->get(i);
}
int walk(int ql, int qr, int x) { // walk for leftmost i such that v[i] < x
if(v >= x) return -1;
if(ql >= tr || qr <= tl) return -1;
if(ql <= tl && qr >= tr) return walk_helper(x);
push();
int res = lc->walk(ql, qr, x);
if(res != -1) return res;
return rc->walk(ql, qr, x);
}
int walk_helper(int x) {
if(tl + 1 == tr) return tl;
push();
lc->push();
if(lc->v < x) return lc->walk_helper(x);
return rc->walk_helper(x);
}
};
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n = 1e9;
int q, l; cin >> q >> l;
map<int, int> asp, ssp; // spares
asp[inf] = -1;
ssp[inf] = -1;
segnode lst{0, (int)5e8 + 5}, rst{0, (int)5e8 + 5};
int ans = 0;
while(q--) {
int t, x, a; cin >> t >> x >> a;
assert((t + x) % 2 == 0);
x /= 2;
// debug(asp);
// debug(ssp);
if(t == 1) {
while(true) {
int v = min(a, ssp[x]);
ans += v;
a -= v;
ssp[x] -= v;
if(ssp[x] == 0) ssp.erase(x);
lst.add(x, x + 1, v);
v = min(a, ssp[x + 1]);
ans += v;
a -= v;
ssp[x + 1] -= v;
if(ssp[x + 1] == 0) ssp.erase(x + 1);
rst.add(x, x + 1, v);
if(a > lst.get(x + 1)) {
int dif = a - lst.get(x + 1);
// debug(x);
asp[x] += dif;
a -= dif;
}
if(a == 0) break;
int i = lst.walk(x + 1, inf, a);
assert(i != -1);
i = min(i, ssp.lower_bound(x)->f);
lst.add(x + 1, i, -a);
rst.add(x, i - 1, a);
x = i - 1;
}
} else {
while(true) {
int v = min(a, asp[x - 1]);
ans += v;
a -= v;
asp[x - 1] -= v;
if(asp[x - 1] == 0) asp.erase(x - 1);
rst.add(x - 1, x, v);
v = min(a, asp[x]);
ans += v;
a -= v;
asp[x] -= v;
if(asp[x] == 0) asp.erase(x);
lst.add(x, x + 1, v);
if(a > rst.get(x)) {
int dif = a - rst.get(x);
ssp[x] += dif;
a -= dif;
}
if(a == 0) break;
// debug(x);
int i = rst.walk(x, inf, a);
// debug(i);
assert(i != -1);
i = min(i, asp.lower_bound(x)->f);
rst.add(x, i, -a);
lst.add(x, i, a);
x = i;
}
}
cout << ans << '\n';
}
}
Compilation message
sugar.cpp: In function 'int main()':
sugar.cpp:102:7: warning: unused variable 'n' [-Wunused-variable]
102 | int n = 1e9;
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1098 ms |
87380 KB |
Output is correct |
| 5 |
Execution timed out |
4064 ms |
8088 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
