Submission #1189154

#TimeUsernameProblemLanguageResultExecution timeMemory
1189154mychecksedadFood Court (JOI21_foodcourt)C++20
0 / 100
247 ms90304 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30; const ll INF = 1e18; int n, m, q; vector<array<ll, 3>> Q[N], QQ[N]; array<ll, 3> T[N]; // remove, add, id ll TT[N]; void comb(int k){ if(T[k<<1|1][0] >= T[k<<1][1]){ T[k] = {T[k<<1][0] + T[k<<1|1][0] - T[k<<1][1], T[k<<1|1][1], -1}; }else{ T[k] = {T[k<<1][0], T[k<<1][1] - T[k<<1|1][0] + T[k<<1|1][1], -1}; } TT[k] = TT[k<<1] + TT[k<<1|1]; } void add(int l, int r, int p, int k, int c, ll val){ if(l == r){ if(val < 0){ T[k] = {-val, 0, c}; TT[k] = 0; }else{ T[k] = {0, val, c}; TT[k] = val; } return; } int mid = l+r>>1; if(p <= mid) add(l, mid, p, k<<1, c, val); else add(mid+1, r, p, k<<1|1, c, val); comb(k); } void rem(int l, int r, int p, int k, int c, ll val){ if(l == r){ T[k] = {0, 0, -1}; TT[k] = 0; return; } int mid = l+r>>1; if(p <= mid) rem(l, mid, p, k<<1, c, val); else rem(mid+1, r, p, k<<1|1, c, val); comb(k); } array<ll, 2> get(int l, int r, int p, int k){ if(r <= p){ return array<ll,2>{T[k][0], T[k][1]}; } int mid = l+r>>1; if(p <= mid) return get(l, mid, p, k<<1); auto R = get(mid + 1, r, p, k<<1|1); if(R[0] >= T[k<<1][1]){ return array<ll,2>{T[k<<1][0] + R[0] - T[k<<1][1], R[1]}; } return array<ll,2>{T[k<<1][0], T[k<<1][1] - R[0] + R[1]}; } array<ll, 2> get2(int l, int r, int p, int k, ll val){ int mid = l+r>>1; if(r <= p){ if(TT[k] < val){ // if not enough return array<ll, 2>{TT[k], T[k][2]}; } if(l == r){ // leaf case, end of the search assert(TT[k] >= val); return {TT[k], T[k][2]}; // result we want } if(TT[k<<1|1] >= val){ // right is enough return get2(mid+1, r, p, k<<1|1, val); } // descend left again return get2(l, mid, p, k<<1, val - TT[k<<1|1]); } if(p <= mid) return get2(l, mid, p, k<<1, val); auto R = get2(mid+1, r, p, k<<1|1, val); if(R[0] >= val) return R; auto res = get2(l, mid, p, k<<1, val - R[0]); return {res[0] + R[0], res[1]}; } void solve(){ cin >> n >> m >> q; vector<ll> ans(q + 1); int qq = 0; for(int i = 1; i <= q; ++i){ int tp; cin >> tp; if(tp == 1){ ll l, r, c, k; cin >> l >> r >> c >> k; Q[l].pb({i, c, k}); Q[r + 1].pb({-i, c, k}); }else if(tp == 2){ ll l, r, k; cin >> l >> r >> k; Q[l].pb({i, -1, k}); Q[r + 1].pb({-i, -1, k}); }else{ ll a, b; cin >> a >> b; QQ[a].pb({i, b, ++qq}); } } for(int i = 1; i <= 4*q; ++i) T[i] = {0, 0, -1}, TT[i] = 0; for(int i = 1; i <= n; ++i){ for(auto [t, c, k]: Q[i]){ if(c == -1){ if(t < 0){ rem(1, q, -t, 1, c, k); }else{ add(1, q, t, 1, c, -k); } }else{ if(t < 0){ rem(1, q, -t, 1, c, k); }else{ add(1, q, t, 1, c, k); } } } for(auto [t, k, idx]: QQ[i]){ auto val = get(1, q, t, 1); ans[idx] = val[1] < k ? 0ll : get2(1, q, t, 1, val[1] - k + 1)[1]; } } for(int i = 1; i <= qq; ++i){ cout << ans[i] << '\n'; } } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...