#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1e18;
struct segtree{
struct node{
ll sm, lazy_mx, lazy_add;
pair<ll, ll> mn, mn2;
node(){
sm = 0LL, lazy_mx = -inf, lazy_add = 0LL;
mn = {0, 1};
mn2 = {inf, 0};
}
void calc(node a, node b){
sm = a.sm+b.sm;
vector<pair<ll, ll>> v;
v.pb(a.mn);
v.pb(a.mn2);
if(b.mn.f == v[0].f) v[0].sc+=b.mn.sc;
else if(b.mn.f == v[1].f) v[1].sc+=b.mn.sc;
else v.pb(b.mn);
if(b.mn2.f == v[0].f) v[0].sc+=b.mn2.sc;
else if(b.mn2.f == v[1].f) v[1].sc+=b.mn2.sc;
else v.pb(b.mn2);
sort(v.begin(), v.end());
mn = v[0];
mn2 = v[1];
}
};
int k;
vector<node> v;
segtree(int n){
k = 1;
while(k <= n) k*=2; k*=2;
v.resize(k, node());
for(int i = k/2-1; i > 0; i--) v[i].calc(v[2*i], v[2*i+1]);
}
void chmx(int l, int r, int nd, int a, int b, ll exs, ll ex, ll x, bool tt){
//clog << nd << " " << v[nd].mn.f << " " << v[nd].mn2.f << " nd\n";
if(a > r || b < l || (tt ? ex:v[nd].mn.f+exs) >= x){
if(tt){
v[nd].lazy_mx = ex;
v[nd].lazy_add+=exs;
v[nd].sm+=(b-a+1-v[nd].mn.sc)*exs + v[nd].mn.sc*(ex-v[nd].mn.f);
v[nd].mn.f = ex;
}
else{
if(v[nd].lazy_mx != -inf) v[nd].lazy_mx+=exs;
v[nd].lazy_add+=exs;
v[nd].sm+=(b-a+1)*exs;
v[nd].mn.f+=exs;
if(v[nd].mn2.f != inf) v[nd].mn2.f+=exs;
}
return;
}
if(a >= l && b <= r && v[nd].mn2.f+exs > x){
v[nd].lazy_mx = x;
v[nd].lazy_add+=exs;
v[nd].sm+=(b-a+1-v[nd].mn.sc)*exs + v[nd].mn.sc*(x-v[nd].mn.f);
v[nd].mn.f = x;
return;
}
exs+=v[nd].lazy_add;
if(!tt){
if(v[nd].lazy_mx != -inf){
tt = 1;
ex+=v[nd].lazy_mx;
}
}
if(!tt){
ex+=v[nd].lazy_add;
}
v[nd].lazy_mx = -inf;
v[nd].lazy_add = 0LL;
int md = (a+b)/2;
chmx(l, r, 2*nd, a, md, exs, ex, x, tt);
chmx(l, r, 2*nd+1, md+1, b, exs, ex, x, tt);
if(2*nd+1 < k) v[nd].calc(v[2*nd], v[2*nd+1]);
}
void chmx(int l, int r, ll x){
chmx(l, r, 1, 0, k/2-1, 0, 0, x, 0);
}
void add(int l, int r, int nd, int a, int b, ll exs, ll ex, ll x, bool tt){
if(a > r || b < l){
if(tt){
v[nd].lazy_mx = ex;
v[nd].lazy_add+=exs;
v[nd].sm+=(b-a+1-v[nd].mn.sc)*exs + v[nd].mn.sc*(ex-v[nd].mn.f);
v[nd].mn.f = ex;
}
else{
if(v[nd].lazy_mx != -inf) v[nd].lazy_mx+=exs;
v[nd].lazy_add+=exs;
v[nd].sm+=(b-a+1)*exs;
v[nd].mn.f+=exs;
if(v[nd].mn2.f != inf) v[nd].mn2.f+=exs;
}
return;
}
if(a >= l && b <= r){
if(tt){
v[nd].lazy_mx = ex;
v[nd].lazy_add+=exs;
v[nd].sm+=(b-a+1-v[nd].mn.sc)*exs + v[nd].mn.sc*(ex-v[nd].mn.f);
v[nd].mn.f = ex;
}
else{
if(v[nd].lazy_mx != -inf) v[nd].lazy_mx+=exs;
v[nd].lazy_add+=exs;
v[nd].sm+=(b-a+1)*exs;
v[nd].mn.f+=exs;
if(v[nd].mn2.f != inf) v[nd].mn2.f+=exs;
}
if(v[nd].lazy_mx != -inf) v[nd].lazy_mx+=x;
v[nd].lazy_add+=x;
v[nd].sm+=(b-a+1)*x;
v[nd].mn.f+=x;
if(v[nd].mn2.f != inf) v[nd].mn2.f+=x;
return;
}
exs+=v[nd].lazy_add;
if(!tt){
if(v[nd].lazy_mx != -inf){
tt = 1;
ex+=v[nd].lazy_mx;
}
}
if(!tt){
ex+=v[nd].lazy_add;
}
v[nd].lazy_mx = -inf;
v[nd].lazy_add = 0LL;
int md = (a+b)/2;
add(l, r, 2*nd, a, md, exs, ex, x, tt);
add(l, r, 2*nd+1, md+1, b, exs, ex, x, tt);
if(2*nd+1 < k) v[nd].calc(v[2*nd], v[2*nd+1]);
}
void add(int l, int r, ll x){
add(l, r, 1, 0, k/2-1, 0, 0, x, 0);
}
ll sum(int l, int r, int nd, int a, int b, ll exs, ll ex, bool tt){
clog << nd << " " << v[nd].mn.f << " " << v[nd].mn2.f << " " << ex << " " << exs << " " << tt << " d\n";
if(a > r || b < l){
if(tt){
v[nd].lazy_mx = ex;
v[nd].lazy_add+=exs;
v[nd].sm+=(b-a+1-v[nd].mn.sc)*exs + v[nd].mn.sc*(ex-v[nd].mn.f);
v[nd].mn.f = ex;
}
else{
if(v[nd].lazy_mx != -inf) v[nd].lazy_mx+=exs;
v[nd].lazy_add+=exs;
v[nd].sm+=(b-a+1)*exs;
v[nd].mn.f+=exs;
if(v[nd].mn2.f != inf) v[nd].mn2.f+=exs;
}
return 0LL;
}
if(a >= l && b <= r){
if(tt){
v[nd].lazy_mx = ex;
v[nd].lazy_add+=exs;
v[nd].sm+=(b-a+1-v[nd].mn.sc)*exs + v[nd].mn.sc*(ex-v[nd].mn.f);
v[nd].mn.f = ex;
}
else{
if(v[nd].lazy_mx != -inf) v[nd].lazy_mx+=exs;
v[nd].lazy_add+=exs;
v[nd].sm+=(b-a+1)*exs;
v[nd].mn.f+=exs;
if(v[nd].mn2.f != inf) v[nd].mn2.f+=exs;
}
return v[nd].sm;
}
exs+=v[nd].lazy_add;
if(!tt){
if(v[nd].lazy_mx != -inf){
tt = 1;
ex+=v[nd].lazy_mx;
}
}
if(!tt){
ex+=v[nd].lazy_add;
}
v[nd].lazy_mx = -inf;
v[nd].lazy_add = 0LL;
int md = (a+b)/2;
ll rt = sum(l, r, 2*nd, a, md, exs, ex, tt) + sum(l, r, 2*nd+1, md+1, b, exs, ex, tt);
if(2*nd+1 < k) v[nd].calc(v[2*nd], v[2*nd+1]);
return rt;
}
ll sum(int l, int r){
return sum(l, r, 1, 0, k/2-1, 0, 0, 0);
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, q; cin >> n >> m >> q;
segtree seg(n);
while(q--){
int tt; cin >> tt;
if(tt == 1){
int l, r, c; ll k; cin >> l >> r >> c >> k; l--, r--;
seg.add(l, r, k);
}
else if(tt == 2){
int l, r; ll k; cin >> l >> r >> k; l--, r--;
seg.add(l, r, -k);
seg.chmx(0, seg.k/2-1, 0);
}
else{
int a; ll b; cin >> a >> b; a--;
cout << (seg.sum(a, a) >= b ? 1:0) << "\n";
}
}
}
Compilation message
foodcourt.cpp: In constructor 'segtree::segtree(int)':
foodcourt.cpp:38:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
38 | while(k <= n) k*=2; k*=2;
| ^~~~~
foodcourt.cpp:38:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
38 | while(k <= n) k*=2; k*=2;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
794 ms |
35852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1080 ms |
63048 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
893 ms |
57976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
