#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
typedef long long lint;
typedef pair<lint, lint> ii;
const lint inf = 1234567890123456;
int n, M, Q;
struct thing{ lint v, l, r; };
inline thing merge(thing a, thing b){
if(a.v == b.v and a.r == b.l - 1) return {a.v, a.l, b.r};
else if(a.v > b.v) return b;
else return a;
}
const int B = 18;
const int N = 1 << B;
struct seg{
thing tree[2*N];
lint lazy[2*N];
inline int l(int u){ return (u<<1); }
inline int r(int u){ return (u<<1|1); }
inline bool has(int mask, int b){ return (mask>>b)&1; }
seg(){
fill(lazy,lazy+2*N,0);
for(int i = 0;i < N;i++) tree[i] = {0,i,i};
for(int i = N-1;i;i >>= 1) tree[i] = merge(tree[i], tree[r(i)]);
}
void apply(int u, lint L){
tree[u].v += L;
lazy[u] += L;
}
void push(int u){
if(u < N){
apply(l(u), lazy[u]);
apply(r(u), lazy[u]);
lazy[u] = 0;
}
}
void update(int u, int s, int e, int S, int E, lint L){
if(S <= s and e <= E){
apply(u, L);
return;
}
push(u);
int m = (s+e)>>1;
if(S <= m) update(l(u), s, m, S, E, L);
if(E > m) update(r(u), m+1, e, S, E, L);
tree[u] = merge(tree[l(u)], tree[r(u)]);
}
void update(int S, int E, int L){ update(1, 1, n, S, E, L); }
thing query(int u, int s, int e, int S, int E){
push(u);
if(S <= s and e <= E) return tree[u];
int m = (s+e)>>1;
if(E <= m) return query(l(u), s, m, S, E);
else if(S > m) return query(r(u), m+1, e, S, E);
else return merge(query(l(u), s, m, S, E), query(r(u), m+1, e, S, E));
}
thing query(int S, int E){ return query(1, 1, n, S, E); }
} *root;
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> M >> Q;
root = new seg();
for(int i = 0;i < Q;i++){
int t; cin >> t;
if(t == 1){
int l, r, c, k; cin >> l >> r >> c >> k;
root->update(l,r,k);
}
else if(t == 2){
int l, r, k; cin >> l >> r >> k;
root->update(l,r,-k);
while(true){
thing small = root->query(1,n);
if(small.v >= 0) break;
root->update(small.l, small.r, -small.v);
//show2(small.l, small.r);
}
}
else{
lint a, b; cin >> a >> b;
thing res = root->query(a,a);
if(res.v >= b) cout << "1\n";
else cout << "0\n";
}
//for(int i = 1;i <= n;i++) cout << root->query(i,i).v << " "; cout << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
10572 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
10572 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1091 ms |
10572 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1094 ms |
10572 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
10572 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
10572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
10572 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
10572 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
