Submission #973675

#TimeUsernameProblemLanguageResultExecution timeMemory
973675RaresFelixFood Court (JOI21_foodcourt)C++17
68 / 100
1033 ms25912 KiB
#include <bits/stdc++.h> using namespace std; #define int ll using ll = long long; using vi = vector<int>; using vll = vector<ll>; using ii = pair<ll, ll>; struct ura1 { int n; vll V; ura1(int N) : n(N), V(N, 0) {} void update(int p, int v) { ///update pe pozitie V[p] = v; } int query(int p) { if(p == -1) return 0; /// va returna suma maxima pt (i...p) int re = V[p], s = V[p]; for(int i = p - 1; i >= 0; --i) { s += V[i]; re = max(re, s); } return re; } }; struct ura2 { ll n, sumtot = 0; vll V; ura2(int N) : n(N), V(N) {} void update(int p, int v) { ///update pe pozitie sumtot -= V[p]; V[p] = v; sumtot += V[p]; } int sum(int p) { int re = 0; for(int i = 0; i <= p; ++i) re += V[i]; return re; } int query(int nr) { /// va returna pozitia celul a al nr-lea element ll s = 0; for(int i = 0; i < n; ++i) { s += V[i]; if(s >= nr) return i; } assert(0); } }; signed main() { int n, m, q; cin >> n >> m >> q; vi V1, V2, C2; vector<ii> UpV1, UpV2; /// toggle-uri pe timp struct query { int poz, id, ultV1, ultV2; }; vector<vector<query> > Q(n); int nr3 = 0; for (int i = 0; i < q; ++i) { int tip; cin >> tip; if (tip == 1) { int l, r, c, k; cin >> l >> r >> c >> k; --l; --r; UpV1.push_back({l, V1.size()}); UpV1.push_back({r + 1, V1.size()}); UpV2.push_back({l, V2.size()}); UpV2.push_back({r + 1, V2.size()}); V1.push_back(k); V2.push_back(k); C2.push_back(c); } else if (tip == 2) { int l, r, k; cin >> l >> r >> k; --l; --r; UpV1.push_back({l, V1.size()}); UpV1.push_back({r + 1, V1.size()}); V1.push_back(-k); } else { int a, b; cin >> a >> b; --a; Q[a].push_back({b, nr3, int(V1.size()) - 1, int(V2.size()) - 1}); ++nr3; } } sort(UpV1.begin(), UpV1.end()); sort(UpV2.begin(), UpV2.end()); int p1 = 0, p2 = 0; vi Re(nr3); ura1 Sol1(V1.size()); vi on1(V1.size(), 0); ura2 Sol2(V2.size()); vi on2(V2.size(), 0); for(int i = 0; i < n; ++i) { while(p1 < UpV1.size() && UpV1[p1].first <= i) { //toggle it int v = UpV1[p1].second; if(!on1[v]) Sol1.update(v, V1[v]); else Sol1.update(v, 0); on1[v] ^= 1; ++p1; } while(p2 < UpV2.size() && UpV2[p2].first <= i) { //toggle it int v = UpV2[p2].second; if(!on2[v]) Sol2.update(v, V2[v]); else Sol2.update(v, 0); on2[v] ^= 1; ++p2; } for(auto q : Q[i]) { ll nrsuf = Sol1.query(q.ultV1), nrtot = Sol2.sum(q.ultV2); ll b = q.poz + nrtot - nrsuf; if(b > nrtot) { Re[q.id] = 0; } else { Re[q.id] = C2[Sol2.query(b)]; } } } for(auto it : Re) cout << it << "\n"; return 0; }

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:111:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         while(p1 < UpV1.size() && UpV1[p1].first <= i) {
      |               ~~~^~~~~~~~~~~~~
foodcourt.cpp:120:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         while(p2 < UpV2.size() && UpV2[p2].first <= i) {
      |               ~~~^~~~~~~~~~~~~
#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...