#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define pb push_back
#define endl "\n"
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
const int inf = 1e18;
const int mod = 1e9+7;
#ifdef ONLINE_JUDGE
template<typename... Args>
inline void debug(const Args&... args){
return void("59");
}
#else
inline void debug(){cerr<<endl;}
template<typename... Args>
inline void debug(const Args&... args){
((cerr<<args<<' '),...)<<endl;
}
#endif
struct SegmentTree{
//~ int a[1000005] = {0};
int ST1[1000005] = {0}, ST2[1000005] = {0};
ii ST3[1000005] = {{0, 0}};
int lazy[1000005] = {0};
SegmentTree(){}
void push(int ind, int l, int r){ //min icin
if(l!=r){
lazy[ind*2] += lazy[ind];
lazy[ind*2+1] += lazy[ind];
}
ST3[ind].fi += lazy[ind];
lazy[ind] = 0;
}
void build3(int ind, int l, int r){
if(l==r){
ST3[ind].se = l;
return;
}
int m = (l+r)/2;
build3(ind*2, l, m);
build3(ind*2+1, m+1, r);
ST3[ind].se = ST3[ind*2].se;
}
void update1(int ind, int l, int r, int u, int v){ //ekleme
if(l>u || r<u)return;
if(l == r){
ST1[ind] += v;
return;
}
int m = (l+r)/2;
update1(ind*2, l, m, u, v);
update1(ind*2+1, m+1, r, u, v);
ST1[ind] = ST1[ind*2] + ST1[ind*2+1];
}
void update2(int ind, int l, int r, int u, int v){ //cikarma
if(l>u || r<u)return;
if(l == r){
ST2[ind] += v;
return;
}
int m = (l+r)/2;
update2(ind*2, l, m, u, v);
update2(ind*2+1, m+1, r, u, v);
ST2[ind] = ST2[ind*2] + ST2[ind*2+1];
}
void update3(int ind, int l, int r, int s, int f, int v){
push(ind, l, r);
if(l>f || r<s)return;
if(l>=s && r<=f){
lazy[ind] += v;
push(ind, l, r);
return;
}
int m = (l+r)/2;
update3(ind*2, l, m, s, f, v);
update3(ind*2+1, m+1, r, s, f, v);
//~ ST3[ind].fi = min(ST3[ind*2].fi, ST3[ind*2+1].fi);
ST3[ind] = ST3[ind*2].fi<ST3[ind*2+1].fi ? ST3[ind*2] : ST3[ind*2+1];
}
int query1(int ind, int l, int r, int s, int f){
if(l>f || r<s)return 0;
if(l>=s && r<=f)return ST1[ind];
int m = (l+r)/2;
return query1(ind*2, l, m, s, f) + query1(ind*2+1, m+1, r, s, f);
}
int walk(int ind, int l, int r, int cur, int x){
if(l==r){
if(x>cur+ST1[ind]){
return -1;
}
return l;
}
int m = (l+r)/2;
if(cur + ST1[ind*2] >= x){
return walk(ind*2, l, m, cur, x);
}
else{
return walk(ind*2+1, m+1, r, cur + ST1[ind*2], x);
}
}
int query2(int ind, int l, int r, int s, int f){
if(l>f || r<s)return 0;
if(l>=s && r<=f)return ST2[ind];
int m = (l+r)/2;
return query2(ind*2, l, m, s, f) + query2(ind*2+1, m+1, r, s, f);
}
ii query3(int ind, int l, int r, int s, int f){
push(ind, l, r);
if(l>f || r<s)return {inf, -1};
if(l>=s && r<=f)return ST3[ind];
int m = (l+r)/2;
ii t1 = query3(ind*2, l, m, s, f);
ii t2 = query3(ind*2+1, m+1, r, s, f);
return t1<t2 ? t1 : t2;
}
};
int n, m, q, cnt, sorgucnt;
vector<array<int, 4>> inp;
set<array<int, 4>> st;
//~ set<array<int, 4>> inp2;
vector<vector<iii>> qinp;
vector<int> ans;
int32_t main(){
fast;
cin>>n>>m>>q;
SegmentTree* ST = new SegmentTree();
qinp.assign(n+5, vector<iii>());
inp.pb(array<int, 4>());
while(q--){
int x;
cin>>x;
if(x == 1){
cnt++;
int l, r, c, k;
cin>>l>>r>>c>>k;
inp.pb({l, r, k, c});
st.insert({l, cnt, k, 1});
st.insert({r+1, cnt, -k, 1});
}
else if(x == 2){
cnt++;
int l, r, k;
cin>>l>>r>>k;
inp.pb({l, r, k, -1});
st.insert({l, cnt, -k, -1});
st.insert({r+1, cnt, k, -1});
}
else{
sorgucnt ++;
int a, b;
cin>>a>>b;
qinp[a].pb({cnt, b, sorgucnt}); //a dukkanina cnt update'ten sonra b queryisi geldi
}
}
ST->build3(1, 1, cnt);
ans.assign(sorgucnt+5, -1);
//~ cerr<<cnt<<endl;
//~ cerr<<sorgucnt<<endl;
auto it = st.begin();
for(int i=1;i<=n;i++){
//~ cerr<<" a "<<i<<endl;
while(it != st.end() && (*it)[0]<=i){
//~ cerr<<"it"<<endl;
//~ for(int j=0;j<=3;j++){
//~ cout<<(*it)[j]<<" .it. "<<i<<endl;
//~ }cout<<endl;
if((*it)[3] == 1){
ST->update1(1, 1, cnt, (*it)[1], (*it)[2]);
ST->update3(1, 1, cnt, (*it)[1], cnt, (*it)[2]);
}
else{
ST->update2(1, 1, cnt, (*it)[1], (*it)[2]);
ST->update3(1, 1, cnt, (*it)[1], cnt, (*it)[2]);
}
it++;
}
//~ cerr<<"b"<<endl;
for(int j=0;j<(ll)qinp[i].size();j++){
//~ int ind = qinp[i][j].fi, k = qinp[i][j].se;
int ind, k, sorguind;
tie(ind, k, sorguind) = qinp[i][j];
int mn, mnind;
tie(mn, mnind) = ST->query3(1, 1, cnt, 1, cnt);
if(mn > 0)mnind = 0;
int negval = ST->query2(1, 1, cnt, mnind+1, ind);
int sira = (mnind > 0 ? ST->query1(1, 1, cnt, 1, mnind) : 0) - negval + k;
int qind = ST->walk(1, 1, cnt, 0, sira);
//~ cout<<i<<" .i. "<<ind<<" .ind. "<<k<<" .k. "<<mn<<" .mn. "<<mnind<<" .mnind. "<<negval<<" .negval. "<<sira<<" .sira. "<<qind<<" .qind. "<<endl;
//~ if(qind == -1)cout<<0<<endl;
//~ else cout<<inp[qind][3]<<endl;
if(qind == -1)ans[sorguind] = 0;
else ans[sorguind] = inp[qind][3];
}
}
//~ cout<<sorgucnt<<" .sorgucnt. "<<endl;
for(int i=1;i<=sorgucnt;i++){
cout<<ans[i]<<endl;
}
}
# | 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... |