This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1000005;
const ll MOD = 1000000007;
const ll INF = 0x3f3f3f3f3f3f3f3f;
vector<pair<int, ll> > upd[N], que[N];
int ans[N];
int col[N];
ll sum[N], p1[N], p2[N];
void update(int id, int l, int r, int x, int v){
if(l > x || r < x)
return;
if(l == r){
if(v > 0){
if(p1[id] < 0)
p1[id] = 0;
else
p2[id] = sum[id] = v;
} else {
if(p2[id] > 0)
p2[id] = sum[id] = 0;
else
p1[id] = v;
}
return;
}
int m = (l + r) >> 1;
update(id << 1, l, m, x, v);
update(id << 1 | 1, m + 1, r, x, v);
sum[id] = sum[id << 1] + sum[id << 1 | 1];
p2[id] = max(p2[id << 1] + p1[id << 1 | 1], 0LL) + p2[id << 1 | 1];
p1[id] = p1[id << 1] + min(p2[id << 1] + p1[id << 1 | 1], 0LL);
}
int query(int id, int l, int r, ll k){
if(l == r) return l;
int m = (l + r) >> 1;
if(sum[id << 1] >= k)
return query(id << 1, l, m, k);
return query(id << 1 | 1, m + 1, r, k - sum[id << 1]);
}
void query2(int id, int l, int r, int x, ll& s1, ll& c1){
if(l > x) return;
if(r <= x){
s1 += sum[id];
c1 = max(c1 + p1[id], 0LL) + p2[id];
return;
}
int m = (l + r) >> 1;
query2(id << 1, l, m, x, s1, c1);
query2(id << 1 | 1, m + 1, r, x, s1, c1);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m, q;
cin>>n>>m>>q;
for(int t, i = 1; i <= q; ++i){
cin>>t;
ans[i] = -1;
if(t == 1){
int l, r, c;
ll k;
cin>>l>>r>>c>>k;
col[i] = c;
upd[l].push_back({i, k});
upd[r + 1].push_back({i, -k});
} else if(t == 2){
int l, r;
ll k;
cin>>l>>r>>k;
upd[l].push_back({i, -k});
upd[r + 1].push_back({i, k});
} else {
int a;
ll b;
cin>>a>>b;
que[a].push_back({i, b});
}
}
for(int i = 1; i <= n; ++i){
for(auto &[x, v] : upd[i])
update(1, 1, q, x, v);
for(auto &[x, v] : que[i]){
ll s1 = 0, c1 = 0;
query2(1, 1, q, x, s1, c1);
if(c1 < v){
ans[x] = 0;
continue;
}
ans[x] = col[query(1, 1, q, v + s1 - c1)];
}
}
for(int i = 1; i <= q; ++i)
if(ans[i] != -1)cout<<ans[i]<<'\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |