Submission #991860

#TimeUsernameProblemLanguageResultExecution timeMemory
991860n3rm1nFood Court (JOI21_foodcourt)C++17
7 / 100
537 ms524288 KiB
#include<bits/stdc++.h> #define endl '\n' #define ll long long using namespace std; const long long MAXN = 7e4+10; void speed() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } long long n, m, q; vector < pair < long long/**number*/, long long/**colour*/> > g[MAXN]; vector < pair < long long, long long > > pref[MAXN]; long long cutted[MAXN]; vector < pair < long long, long long > > lazy[MAXN * 4]; long long ql, qr, val; long long find_pref(long long ttime, long long shop) { long long l = 0, r = pref[shop].size()-1, mid, ans = 0; while(l <= r) { mid = (l + r)/2; if(pref[shop][mid].second <= ttime) { ans = mid; l = mid + 1; } else r = mid - 1; } return pref[shop][ans].first; } void push_lazy(long long i, long long l, long long r) { if(lazy[i].size() != 0 && l == r) { long long vall, timerr; for (long long j = 0; j < lazy[i].size(); ++ j) { vall = lazy[i][j].first; timerr = lazy[i][j].second; cutted[l] += min(find_pref(timerr, l) - cutted[l], vall); } } if(l != r) { for (long long j = 0; j < lazy[i].size(); ++ j) { lazy[2*i].push_back(lazy[i][j]); lazy[2*i+1].push_back(lazy[i][j]); } } lazy[i].clear(); } long long tt; void update(long long i, long long l, long long r) { push_lazy(i, l, r); if(ql <= l && r <= qr) { lazy[i].push_back({val, tt}); push_lazy(i, l, r); return; } if(qr < l || ql > r)return; long long mid = (l + r)/2; update(2*i, l, mid); update(2*i+1, mid+1, r); } long long x; long long query(long long i, long long l, long long r) { push_lazy(i, l, r); if(l == r) { push_lazy(i, l, r); return cutted[l]; } long long mid = (l + r)/2; if(x <= mid)return query(2*i, l, mid); else return query(2*i+1, mid+1, r); } void solve() { cin >> n >> m >> q; long long type, l, r, k, c; for (long long i = 1; i <= n; ++ i) { pref[i].push_back({0, 0}); g[i].push_back({0, 0}); } long long aa, bb; for (long long i = 1; i <= q; ++ i) { cin >> type; if(type == 1) { cin >> l >> r >> c >> k; for (long long j = l; j <= r; ++ j) { g[j].push_back(make_pair(k, c)); pref[j].push_back(make_pair(pref[j].back().first+k, i)); } } else if(type == 2) { cin >> l >> r >> k; ql = l; qr = r; val = k; tt = i; update(1, 1, n); } else { cin >> aa >> bb; x = aa; long long loose = query(1, 1, n); // cout << loose << endl; /// cout << "* " << cutted[aa] << " " << endl; long long l = 0, r = pref[aa].size()-1, mid, ans = 0; while(l <= r) { mid = (l + r)/2; if(pref[aa][mid].first < bb + loose) { l = mid + 1; } else { ans = mid; r = mid - 1; } } cout << g[aa][ans].second << endl; } } } int main() { speed(); solve(); return 0; }

Compilation message (stderr)

foodcourt.cpp: In function 'void push_lazy(long long int, long long int, long long int)':
foodcourt.cpp:40:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (long long j = 0; j < lazy[i].size(); ++ j)
      |                               ~~^~~~~~~~~~~~~~~~
foodcourt.cpp:49:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (long long j = 0; j < lazy[i].size(); ++ j)
      |                               ~~^~~~~~~~~~~~~~~~
#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...