| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 448361 | dutch | 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 int64_t
using namespace std;
template<class T> struct SegmentTree{
T comb(T &x, T &y){
if(x[0] + y[1] > y[0]){
return {x[0] + y[1], x[1] + y[1], x[2]};
}else{
return {y[0], x[1] + y[1], y[2]};
}
}
int n = 1, i; vector<T> a;
SegmentTree(int N){ while((n+=n)<N); a.resize(2*n); }
SegmentTree& operator[](int j){ i=j+n; return *this; }
void operator=(int v){
a[i] = {max(v, 0LL), v, i-n};
while(i/=2) a[i] = comb(a[2*i], a[2*i+1]);
}
T operator()(int l, int r){
T lx = {0, 0, 0}, rx = lx;
for(l+=n, r+=n+1; l<r; l/=2, r/=2){
if(l & 1) lx = comb(lx, a[l++]);
if(r & 1) rx = comb(a[--r], rx);
}
return comb(lx, rx);
}
};
struct FenwickTree{
vector<int> a; int n;
FenwickTree(int N) : a((n=N)+1) {}
void add(int i, int v){
for(++i; i<=n; i+=i&-i) a[i] += v;
}
int get(int i){
int v = 0;
for(++i; i>=1; i-=i&-i) v += a[i];
return v;
}
int lower_bound(int v){
int i = 0, j = 1<<19;
while(j/=2)
if(i+j<=n && a[i+j]<v) v -= a[i+=j];
return i;
}
};
const int LIM = 2.5e5+1;
int n, m, q, groupAt[LIM], ans[LIM];
array<int, 3> a[LIM];
vector<int> qL[LIM], qR[LIM], b[LIM];
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q;
for(int i=0, t; i<q; ++i){
auto &[l, r, k] = a[i];
cin >> t >> l >> r;
if(t < 3){
qL[l].push_back(i);
qR[r].push_back(i);
}
if(t < 2){
cin >> groupAt[i] >> k;
}else if(t < 3){
cin >> k; k = -k;
}else{
b[l].push_back(i);
l = -1;
}
}
SegmentTree<array<int, 3>> st(q);
FenwickTree F(q);
for(int i=1; i<=n; ++i){
for(int &j : qR[i-1]){
st[j] = 0;
if(a[j][2] > 0) F.add(j,-a[j][2]);
}
for(int &j : qL[i]){
st[j] = a[j][2];
if(a[j][2] > 0) F.add(j, a[j][2]);
}
for(int &j : b[i]){
auto v = st(0, j);
if(v[0] >= a[j][1]){
ans[j] = groupAt[F.lower_bound(F.get(j) - v[0] + a[j][1])];
}
}
}
for(int i=0; i<q; ++i){
if(a[i][0] < 0) cout << ans[i] << '\n';
}
}