//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;
struct TreeSum{
vector<int>tab;
int size = 1;
TreeSum(int n){
while (size < n) size*=2;
tab.assign(2*size, 0);
}
void update(int l, int r, int v){
for (l += size-1, r += size+1; r-l>1; l/=2, r/=2){
if (!(l&1)) tab[l+1] += v;
if (r&1) tab[r-1] += v;
}
}
void clear(){
tab.assign(2*size, 0);
}
int query(int x){
x += size;
int ans = 0;
while (x){
ans += tab[x];
x/=2;
}
return ans;
}
};
struct Tree{
struct Node{
int mn = 0, lazy = 0, sum = 0, mnlazy = 0;
};
vector<Node>tab;
int size = 1;
Tree(int n){
while (size < n) size*=2;
tab.resize(2*size);
}
void push(int x){
for (auto k: {2*x, 2*x+1}){
tab[k].mn = min(tab[k].mn, tab[k].sum + tab[x].mnlazy);
tab[k].sum += tab[x].lazy;
tab[k].lazy += tab[x].lazy;
tab[k].mnlazy = min(tab[k].mnlazy, tab[k].lazy);
}
tab[x].lazy = 0;
tab[x].mnlazy = 0;
}
int query(int x, int lx, int rx, int pos){
if (lx == rx) {
debug(tab[x].sum, tab[x].mn);
return tab[x].sum - tab[x].mn;
}
push(x);
int m = (lx+rx)/2;
if (pos <= m) return query(2*x, lx, m, pos);
return query(2*x+1, m+1, rx, pos);
}
void update(int x, int lx, int rx, int l, int r, int v){
if (lx != rx) push(x);
if (lx > r || rx < l) return;
if (lx >= l && rx <= r){
debug(tab[x].sum, tab[x].mn, lx, rx, v);
tab[x].sum += v;
tab[x].mn = min(tab[x].mn, tab[x].sum);
// if (lx != rx) push(x);
tab[x].lazy += v;
tab[x].mnlazy = min(tab[x].mnlazy, tab[x].lazy);
return;
}
int m = (lx+rx)/2;
update(2*x, lx, m, l, r, v);
update(2*x+1, m+1, rx, l, r, v);
}
};
struct TreeMin{
vector<T>tab;
vector<int>lazy;
int size = 1;
TreeMin(int n){
while (size < n) size*=2;
tab.assign(2*size, {oo, oo});
lazy.assign(2*size, 0);
}
void set(int x, int lx, int rx, int pos, T val){
if (lx == rx) {
tab[x] = val;
return;
}
push(x);
int m = (lx+rx)/2;
if (pos <= m) set(2*x, lx, m, pos, val);
else set(2*x+1, m+1, rx, pos, val);
tab[x] = min(tab[2*x], tab[2*x+1]);
}
void push(int x){
for (auto k: {2*x, 2*x+1}){
tab[k].first += lazy[x];
lazy[k] += lazy[x];
}
lazy[x] = 0;
}
T query(int x, int lx, int rx, int l, int r){
if (lx != rx) push(x);
if (lx > r || rx < l) return {oo, oo};
if (lx >= l && rx <= r) return tab[x];
int m = (lx+rx)/2;
return min(query(2*x, lx, m, l, r), query(2*x+1, m+1, rx, l, r));
}
void update(int x, int lx, int rx, int l, int r, int v){
if (lx != rx) push(x);
if (lx > r || rx < l) return;
if (lx >= l && rx <= r){
tab[x].first += v;
lazy[x] += v;
debug(lx, rx, v, tab[x]);
return;
}
int m = (lx+rx)/2;
update(2*x, lx, m, l, r, v);
update(2*x+1, m+1, rx, l, r, v);
tab[x] = min(tab[2*x], tab[2*x+1]);
}
};
void solve(){
int n, m, q; cin >> n >> m >> q;
Tree t(n+2);
TreeSum sum(n+2);
vector<vector<T>>sweep(n+1);
vector<tuple<int, int, int, int, int>>groups;
vector<int>ans(q+1, -1);
for (int i = 0; i<q; i++){
int type; cin >> type;
if (type == 1){
int l, r, c, k; cin >> l >> r >> c >> k;
t.update(1, 0, t.size-1, l, r, +k);
sum.update(l, r, +k);
groups.emplace_back(i, l, r, c, k);
}
if (type == 2){
int l, r, k; cin >> l >> r >> k;
t.update(1, 0, t.size-1, l, r, -k);
}
if (type == 3){
int a, b; cin >> a >> b;
int present = max(0LL, t.query(1, 0, t.size-1, a));
int all = sum.query(a);
int deleted = all - present;
int now = deleted + b;
debug(all, present, deleted, now);
if (now > all) {
ans[i] = 0;
} else {
debug(now, i);
sweep[a].emplace_back(now, i);
}
}
}
vector<int>ptr(n+1);
for (int i = 1; i<=n; i++) {
sort(sweep[i].begin(), sweep[i].end());
}
int ck = 0;
int last = -1;
TreeMin tt(n+2);
for (int i = 1; i<=n; i++){
if (sweep[i].size()){
tt.set(1, 0, tt.size-1, i, {sweep[i][0].first, i});
debug(i, sweep[i][0].first);
}
}
sum.clear();
auto forward = [&](int i){
while (ck < (int)groups.size() && get<0>(groups[ck]) <= i){
auto [ii, l, r, c, k] = groups[ck];
sum.update(l, r, +k);
tt.update(1, 0, tt.size-1, l, r, -k);
debug(l, r, -k);
last = c;
ck++;
}
};
for (int rep = 0; rep<=q; rep++){
forward(rep);
while (1){
auto maybe = tt.query(1, 0, tt.size-1, 1, n);
debug(maybe);
if (maybe.first > 0) break;
debug(maybe);
int i = maybe.second;
int idx = sweep[i][ptr[i]].second;
ans[idx] = last;
debug(idx, last);
ptr[i]++;
T now = {oo, oo};
if (ptr[i] < (int)sweep[i].size()) now = {sweep[i][ptr[i]].first-sum.query(i), i};
tt.set(1, 0, tt.size-1, i, now);
}
}
for (int i = 0; i<q; i++){
if (ans[i] != -1){
cout << ans[i] << "\n";
}
}
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
116 ms |
12620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
730 ms |
46408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
191 ms |
13496 KB |
Output is correct |
| 2 |
Correct |
198 ms |
14384 KB |
Output is correct |
| 3 |
Correct |
189 ms |
14700 KB |
Output is correct |
| 4 |
Correct |
153 ms |
13404 KB |
Output is correct |
| 5 |
Correct |
180 ms |
14148 KB |
Output is correct |
| 6 |
Correct |
198 ms |
14776 KB |
Output is correct |
| 7 |
Correct |
43 ms |
4000 KB |
Output is correct |
| 8 |
Correct |
28 ms |
3596 KB |
Output is correct |
| 9 |
Correct |
160 ms |
14712 KB |
Output is correct |
| 10 |
Correct |
128 ms |
13116 KB |
Output is correct |
| 11 |
Correct |
163 ms |
14668 KB |
Output is correct |
| 12 |
Correct |
164 ms |
14700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
