Submission #939847

#TimeUsernameProblemLanguageResultExecution timeMemory
939847n3rm1nFood Court (JOI21_foodcourt)C++17
0 / 100
1083 ms524288 KiB
#include<bits/stdc++.h> using namespace std; const long long MAXN = 3e5+10; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } long long n, m, que; vector < pair < long long/**type*/, long long/**number*/ > > q[MAXN]; vector < long long > pref[MAXN]; long long total[MAXN]; long long type; long long l, r, c, k, a, b; long long t[MAXN * 4], lazy[MAXN * 4]; void push_lazy(long long i, long long l, long long r) { if(lazy[i]) t[i] += (r - l + 1) * lazy[i]; if(lazy[i] && l != r) { lazy[2*i] += lazy[i]; lazy[2*i+1] += lazy[i]; } lazy[i] = 0; } long long ql, qr, val; long long query(long long i, long long l, long long r) { push_lazy(i, l, r); if(ql <= l && r <= qr)return t[i]; if(qr < l || r < ql)return 0; long long mid = (l + r)/2; return query(2*i, l, mid) + query(2*i+1, mid+1, r); } void update(long long i, long long l, long long r) { push_lazy(i, l, r); if(qr < l || ql > r)return; if(ql <= l && r <= qr) { lazy[i] = val; push_lazy(i, l, r); return; } long long mid = (l + r)/2; update(2*i, l, mid); update(2*i+1, mid+1, r); t[i] = t[2*i] + t[2*i+1]; } void read() { cin >> n >> m >> que; long long last_add = 0; for (long long i = 1; i <= que; ++ i) { cin >> type; if(type == 1) { cin >> l >> r >> c >> k; for (long long j = l; j <= r; ++ j) { total[j] += k; q[j].push_back(make_pair(c, k)); long long last = 0; if(pref[j].size())last = pref[j][pref[j].size()-1]; pref[j].push_back(last + k); } //cout << "ended " << endl; } else if(type == 2) { cin >> l >> r >> k; for (long long j = l; j <= r; ++ j) { ql = j; qr = j; val = min(total[j], k); update(1, 1, n); total[j] -= val; } } else { cin >> a >> b; ql = a; qr = a; b += query(1, 1, n); if(total[a] < b) { cout << 0 << endl; continue; } // cout << "newb is " << b << endl; long long bl = 0, br = pref[a].size()-1, mid, bans = 0; while(bl <= br) { mid = (bl + br)/2; if(pref[a][mid] < b) { bl = mid + 1; bans = mid; } else { br = mid - 1; } } /*if(a == 3) { cout << b << endl; for (long long j = 0; j < pref[a].size(); ++ j) cout << pref[a][j] << " "; cout << endl; cout << bans << endl; }*/ cout << q[a][bans+1].first << endl; } } } int main() { speed(); read(); return 0; }

Compilation message (stderr)

foodcourt.cpp: In function 'void read()':
foodcourt.cpp:58:15: warning: unused variable 'last_add' [-Wunused-variable]
   58 |     long long last_add = 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...