Submission #958989

#TimeUsernameProblemLanguageResultExecution timeMemory
958989Spade1Food Court (JOI21_foodcourt)C++14
0 / 100
123 ms33484 KiB
#pragma once #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double db; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<ld, ld> pld; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ld> vld; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<pld> vpld; typedef vector<vi> vvi; template<typename T> using pq = priority_queue<T>; template<typename T> using pqg = priority_queue<T, vector<T>, greater<T>>; #define rep0(a) for (int i = 0; i < a; ++i) #define rep1(i, a) for (int i = 0; i < a; ++i) #define rep2(i, a, b) for (int i = a; i <= b; ++i) #define rep3(i, a, b, c) for (int i = a; i <= b; i+=c) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__) #define repd0(a) for (int i = a; i >= 1; --i) #define repd1(i, a) for (int i = a; i >= 1; --i) #define repd2(i, a, b) for (int i = b; i >= a; --i) #define repd3(i, a, b, c) for (int i = b; i >= a; i-=c) #define repd(...) overload4(__VA_ARGS__, repd3, repd2, repd1, repd0)(__VA_ARGS__) #define trav(a, x) for (auto& a : x) #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define st first #define nd second #define lb lower_bound #define ub upper_bound #define all(x) (x).begin(), (x).end() #define ins insert template<typename T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int MOD = 1e9 + 7; const int INF = 0x3fffffff; const ll LINF = 0x1fffffffffffffff; const char nl = '\n'; const int MX = 1e5 + 3; template<class T> struct fenwick { int n; vector<T> t; fenwick (int n=0){init(n);} void init(int _n) { n=_n; t.assign(n+1, T{}); } void update(int x, const T &v) { for(int i = x+1; i <= n; i+=i&-i) t[i] = t[i]+v; } void update(int l, int r, const T &v) { update(l, v); update(r+1, -v); } T query(int x) { T res{}; for (int i = x+1; i > 0; i-=i&-i) res = res+t[i]; return res; } T query(int l, int r) { return query(r) - query(l-1); } //find the first index that sums to >= k int find(const T &k) { int x = 0; T cur{}; for (int i = 1<<(31-__builtin_clz(n)); i > 0; i>>=1) if (x+i <= n && cur+t[x+i] < k) x+=i, cur+=t[i]; return x; } }; void solve() { int n, m, q; cin >> n >> m >> q; vll index(q+1), ans(q+1, -1); vpll ordI[n+2], ordD[n+2], ordQ[n+2]; fenwick<ll> cnt(q+1); index.pb(0); int T = 1; while (q--) { int t; cin >> t; if (t == 1) { ll l, r, c, k; cin >> l >> r >> c >> k; ordI[l].pb({T, k}); ordI[r+1].pb({T, -k}); index[T] = c; } if (t == 2) { ll l, r, k; cin >> l >> r >> k; } if (t == 3) { ll a, b; cin >> a >> b; ordQ[a].pb({T, b}); } T++; } int cur = 0; rep(i, 1, n) { for(auto [T, k] : ordI[i]) cnt.update(T, k); for (auto [T, b] : ordQ[i]) { int idx = cnt.find(b); ans[T] = (idx > T ? 0 : index[idx]); } } trav(a, ans) if (a != -1) cout << a << nl; } int main(int argc, char* argv[]) { ios_base::sync_with_stdio(0); cin.tie(NULL); int t = 1; // cin >> t; while (t--) { solve(); } return 0; }

Compilation message (stderr)

foodcourt.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
foodcourt.cpp: In function 'void solve()':
foodcourt.cpp:112:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  112 |     for(auto [T, k] : ordI[i]) cnt.update(T, k);
      |              ^
foodcourt.cpp:114:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  114 |     for (auto [T, b] : ordQ[i]) {
      |               ^
foodcourt.cpp:110:7: warning: unused variable 'cur' [-Wunused-variable]
  110 |   int cur = 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...