#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define int long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i , a , b) for(int i=a;i >= b;i--)
using namespace std ;
const int maxn = 3e5 + 10 , N = 1e5 +1 , lg = 20 , maxq = 202 , inf = 1e9 , maxk = 2022 , mod =998244353;
int n , q , m , ds[maxn] , ans[maxn ];
struct n1{
int mn , lz ,id = 0;
n1(){
mn =0 , lz =0 ;
}
};
n1 s1[4*maxn] ;
n1 operator+(n1 a , n1 b){
n1 r ;
r.mn = min(a.mn , b.mn);
r.lz =0 ;
if(a.mn == r.mn)r.id = a.id ;
if(b.mn == r.mn)r.id = b.id;
return r ;
}
void sh1(int p){
int pl = p<<1,pr=p<<1|1;
s1[pl].lz += s1[p].lz ;
s1[pr].lz += s1[p].lz ;
s1[pl].mn += s1[p].lz ;
s1[pr].mn += s1[p].lz ;
s1[p].lz =0 ;
}
void bui(int p = 1 , int l = 0 , int r = q){
int pl = p<<1 ,pr=p<<1|1 ,mid=(l+r)/2 ;
if(l == r){
s1[p].id = l ;
s1[p].mn = 0;
return ;
}
bui(pl,l,mid);bui(pr,mid+1,r);
s1[p] = s1[pl] + s1[pr];
}
void upd(int le, int ri ,int x , int p =1 , int l = 0 , int r =q){
int pl = p<<1 ,pr=p<<1|1 ,mid=(l+r)/2 ;
if(le > r|| l > ri)return ;
if(l!=r)sh1(p);
if(le <= l && r <= ri){
s1[p].lz += x;
s1[p].mn += x;
return ;
}
upd(le,ri,x,pl,l,mid);
upd(le,ri,x,pr,mid+1,r);
s1[p]= s1[pl] + s1[pr];
}
n1 que(int le, int ri , int p= 1 ,int l =0 , int r = q){
int mid = (l+r)/2 , pl=p<<1,pr=p<<1|1;
if(le <= l && r <= ri)return s1[p];
sh1(p);
if(mid >= ri)return que(le,ri,pl,l,mid);
if(mid < le)return que(le,ri,pr,mid+1,r);
return que(le,ri,pl,l,mid) + que(le,ri,pr,mid+1,r) ;
}
vector <pii> q1[maxn] ;
vector <pii> v1[maxn] , v2[maxn] ;
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> m >> q ;
rep(i , 1 , q){
int t ;
cin >> t ;
if(t == 3){
int a, b ;
cin >> a >> b;
q1[a].pb({i , b}) ;
}
if(t==2){
int l ,r , k ;
cin >> l >> r >> k ;
v2[l].pb({i , k});
v1[r+1].pb({i , k}) ;
}
if(t==1){
int l ,r , k , c;
cin >> l >> r >> c >> k ;
ds[i] = c;
v1[l].pb({i , k});
v2[r+1].pb({i , k}) ;
}
ans[i] = -1 ;
}
bui() ;
rep(t ,1 ,n){
for(auto [i , k] : v2[t]){
upd(i, q , -k) ;
}
for(auto [i , k] : v1[t]){
upd(i , q , k) ;
}
for(auto [i , k] : q1[t]){
upd(i , i , -(k-1));
if(que(0 , i).id != i){
ans[i] =1 ;
}else{
ans[i] =0 ;
}
upd(i , i , +(k-1)) ;
}
}
rep(i ,1 ,q){
if(ans[i] == -1)continue ;
cout << ans[i] << "\n" ;
}
cout << "\n";
}
/*
3 1 6
1 1 3 1 2
2 2 2 4
3 2 1
3 1 1
3 3 3
3 3 2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
49752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
49752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
93 ms |
55248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
405 ms |
69448 KB |
Output is correct |
| 2 |
Correct |
292 ms |
65620 KB |
Output is correct |
| 3 |
Correct |
431 ms |
71284 KB |
Output is correct |
| 4 |
Correct |
297 ms |
65936 KB |
Output is correct |
| 5 |
Correct |
292 ms |
66128 KB |
Output is correct |
| 6 |
Correct |
393 ms |
72036 KB |
Output is correct |
| 7 |
Correct |
165 ms |
64444 KB |
Output is correct |
| 8 |
Correct |
178 ms |
64500 KB |
Output is correct |
| 9 |
Correct |
385 ms |
70236 KB |
Output is correct |
| 10 |
Correct |
372 ms |
70468 KB |
Output is correct |
| 11 |
Correct |
378 ms |
70992 KB |
Output is correct |
| 12 |
Correct |
394 ms |
71792 KB |
Output is correct |
| 13 |
Correct |
407 ms |
71140 KB |
Output is correct |
| 14 |
Correct |
393 ms |
71804 KB |
Output is correct |
| 15 |
Correct |
395 ms |
71732 KB |
Output is correct |
| 16 |
Correct |
466 ms |
71736 KB |
Output is correct |
| 17 |
Correct |
402 ms |
71720 KB |
Output is correct |
| 18 |
Correct |
435 ms |
71456 KB |
Output is correct |
| 19 |
Correct |
429 ms |
71708 KB |
Output is correct |
| 20 |
Correct |
423 ms |
71328 KB |
Output is correct |
| 21 |
Correct |
401 ms |
71764 KB |
Output is correct |
| 22 |
Correct |
439 ms |
71764 KB |
Output is correct |
| 23 |
Correct |
443 ms |
71752 KB |
Output is correct |
| 24 |
Correct |
405 ms |
71764 KB |
Output is correct |
| 25 |
Correct |
328 ms |
70260 KB |
Output is correct |
| 26 |
Correct |
316 ms |
70740 KB |
Output is correct |
| 27 |
Correct |
310 ms |
72444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
49752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
89 ms |
54612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
49752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
49752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
