| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 890542 | LucaIlie | Food Court (JOI21_foodcourt) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
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() {
int n, m, q;
cin >> n >> m >> q;
int bs = sqrt( n );
for ( int i = 1; i <= n; i++ )
bucket[i] = i / bs;
for ( int b = 0; b * bs <= n; b++ ) {
leftB[b] = b * bs;
rightB[b] = min( n, (b + 1) * bs - 1 );
}
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 );
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;
}
if ( r == t )
cout << "0\n";
else {
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 ( queueBucket[b].size() == 0 || (queueIndex[p].size() > 0 && queueIndex[p][lp].t > queueBucket[b][rb].t) )
cout << queueIndex[p][lp].c << "\n";
else
cout << queueBucket[b][lb].c << "\n";
}
}
}
return 0;
}