#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;
}
Compilation message
foodcourt.cpp: In member function 'void SegTree::update(long long int, long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:46:39: error: no matching function for call to 'min(long long int&, int)'
46 | info add = { x, min( x, 0 ) };
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from foodcourt.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
230 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: template argument deduction/substitution failed:
foodcourt.cpp:46:39: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
46 | info add = { x, min( x, 0 ) };
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from foodcourt.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
278 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: template argument deduction/substitution failed:
foodcourt.cpp:46:39: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
46 | info add = { x, min( x, 0 ) };
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from foodcourt.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
3468 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: template argument deduction/substitution failed:
foodcourt.cpp:46:39: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
46 | info add = { x, min( x, 0 ) };
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from foodcourt.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
3474 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: template argument deduction/substitution failed:
foodcourt.cpp:46:39: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
46 | info add = { x, min( x, 0 ) };
| ^
