#include <bits/stdc++.h>
using namespace std;
struct aaa {
int t, c;
long long k;
};
const int MAX_N = 3e5;
int bucket[MAX_N + 1], leftB[MAX_N + 1], rightB[MAX_N + 1];
long long queueIndexSize[MAX_N + 1], queueBucketSize[MAX_N + 1];
vector <aaa> queueIndex[MAX_N + 1], queueBucket[MAX_N + 1];
struct SegTree {
struct info {
long long sum, minn;
info operator+( info &x ) {
info ans;
ans.minn = min( minn, sum + x.minn );
ans.sum = sum + x.sum;
return ans;
}
};
info lazy[4 * MAX_N];
void propag( int v, int l, int r ) {
if ( l != r ) {
lazy[v * 2 + 1] = lazy[v * 2 + 1] + lazy[v];
lazy[v * 2 + 2] = lazy[v * 2 + 2] + lazy[v];
lazy[v] = { 0, 0 };
}
}
void update( int v, int l, int r, int lu, int ru, int x ) {
propag( v, l, r );
if ( l > ru || r < lu )
return;
if ( lu <= l && r <= ru ) {
info add = { x, min( x, 0 ) };
lazy[v] = lazy[v] + add;
propag( v, l, r );
return;
}
int mid = (l + r) / 2;
update( v * 2 + 1, l, mid, lu, ru, x );
update( v * 2 + 2, mid + 1, r, lu, ru, x );
}
long long query( int v, int l, int r, int p ) {
propag( v, l, r );
if ( l == r )
return lazy[v].sum - lazy[v].minn;
int mid = (l + r) / 2;
if ( p <= mid )
return query( v * 2 + 1, l, mid, p );
return query( v * 2 + 2, mid + 1, r, p );
}
} qs;
signed main() {
ios_base::sync_with_stdio( false );
cin.tie( NULL );
cout.tie( NULL );
int n, m, q;
cin >> n >> m >> q;
int bs = sqrt( n / 2 );
for ( int i = 1; i <= n; i++ ) {
bucket[i] = i / bs;
queueIndex[i].push_back( { -1, 0, 0 } );
}
for ( int b = 0; b * bs <= n; b++ ) {
leftB[b] = b * bs;
rightB[b] = min( n, (b + 1) * bs - 1 );
queueBucket[b].push_back( { -1, 0, 0 } );
}
for ( int t = 0; t < q; t++ ) {
int type;
cin >> type;
if ( type == 1 ) {
int l, r, c, k;
cin >> l >> r >> c >> k;
qs.update( 0, 1, n, l, r, k );
int bl = bucket[l], br = bucket[r];
if ( bl == br ) {
for ( int i = l; i <= r; i++ ) {
queueIndexSize[i] += k;
queueIndex[i].push_back( { t, c, queueIndexSize[i] } );
}
} else {
for ( int i = l; i <= rightB[bl]; i++ ) {
queueIndexSize[i] += k;
queueIndex[i].push_back( { t, c, queueIndexSize[i] } );
}
for ( int i = leftB[br]; i <= r; i++ ) {
queueIndexSize[i] += k;
queueIndex[i].push_back( { t, c, queueIndexSize[i] } );
}
for ( int b = bl + 1; b <= br - 1; b++ ) {
queueBucketSize[b] += k;
queueBucket[b].push_back( { t, c, queueBucketSize[b] } );
}
}
} else if ( type == 2 ) {
int l, r, k;
cin >> l >> r >> k;
qs.update( 0, 1, n, l, r, -k );
} else {
int p;
long long x;
cin >> p >> x;
int b = bucket[p];
x += queueIndexSize[p] + queueBucketSize[b] - qs.query( 0, 1, n, p );
cout << (x <= queueIndexSize[p] + queueBucketSize[b]) << "\n";
/*int l = -1, r = t;
while ( r - l > 1 ) {
int mid = (l + r) / 2;
int lp = 0, rp = queueIndex[p].size();
while ( rp - lp > 1 ) {
int mp = (lp + rp) / 2;
if ( queueIndex[p][mp].t > mid )
rp = mp;
else
lp = mp;
}
int lb = 0, rb = queueBucket[b].size();
while ( rb - lb > 1 ) {
int mb = (lb + rb) / 2;
if ( queueBucket[b][mb].t > mid )
rb = mb;
else
lb = mb;
}
long long k = (queueIndex[p].size() == 0 ? 0 : queueIndex[p][lp].k) + (queueBucket[b].size() == 0 ? 0 : queueBucket[b][lb].k);
if ( k >= x )
r = mid;
else
l = mid;
}
int lp = 0, rp = queueIndex[p].size();
while ( rp - lp > 1 ) {
int mp = (lp + rp) / 2;
if ( queueIndex[p][mp].t > r )
rp = mp;
else
lp = mp;
}
int lb = 0, rb = queueBucket[b].size();
while ( rb - lb > 1 ) {
int mb = (lb + rb) / 2;
if ( queueBucket[b][mb].t > r )
rb = mb;
else
lb = mb;
}
if ( queueIndex[p][lp].t == r )
cout << queueIndex[p][lp].c << "\n";
else if ( queueBucket[b][lb].t == r )
cout << queueBucket[b][lb].c << "\n";
else
cout << "0\n";*/
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
17500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
17500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
24668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1016 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
17500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
334 ms |
202376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
17500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
17500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
