Submission #1046451

#TimeUsernameProblemLanguageResultExecution timeMemory
1046451qrnoMeteors (POI11_met)C++14
100 / 100
1311 ms65536 KiB
#include <bits/stdc++.h> using namespace std; #define int long long //{{{ FenwickTree struct FenwickTree { int N; vector<int> data; FenwickTree(int N) : N(N), data(N) {} void add(int idx, int delta) { for (; idx < N; idx |= idx+1) data[idx] += delta; } int sum(int r) { int ret = 0; for (; r >= 0; r &= r+1, r--) ret += data[r]; return ret; } int sum(int l, int r) { return sum(r) - sum(l-1); } }; //}}} // Range Fenwick {{{ struct RangeFenwick { FenwickTree FT; RangeFenwick(int N) : FT(N+1) {} void update(int l, int r, int x) { FT.add(l, x); FT.add(r+1, -x); } int query(int idx) { return FT.sum(idx); } }; //}}} const int LOG = 20; // Debug {{{ #define var(x) "[", #x, " ", x, "] " template<typename ...A> void db(A const&... a) { ((cout << (a)), ...); cout << endl; } //}}} signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector<int32_t> O(M), P(N); for (auto &x : O) cin >> x, x--; for (auto &x : P) cin >> x; vector<vector<int32_t>> S(N); for (int i = 0; i < M; i++) S[O[i]].push_back(i); int K; cin >> K; vector<array<int32_t, 3>> Q(K); for (auto &[l, r, a] : Q) { cin >> l >> r >> a; l--, r--; } vector<vector<int32_t>> who(K+1); vector<int32_t> L(N, 0), R(N, K-1); vector<int32_t> ans(N, -1); for (int step = 0; step < LOG; step++) { for (int i = 0; i < N; i++) { if (L[i] > R[i]) continue; int mid = (L[i]+R[i])/2; who[mid].push_back(i); } RangeFenwick FT(M); for (int mid = 0; mid < K; mid++) { auto [l, r, x] = Q[mid]; if (l <= r) { FT.update(l, r, x); } else { FT.update(l, M-1, x); FT.update(0, r, x); } for (auto v : who[mid]) { int sum = 0; for (auto s : S[v]) { sum += FT.query(s); if (sum >= P[v]) break; } if (sum >= P[v]) { ans[v] = mid; R[v] = mid-1; } else { L[v] = mid+1; } } who[mid].clear(); } } for (auto x : ans) { if (x == -1) cout << "NIE" << endl; else cout << x+1 << endl; } }

Compilation message (stderr)

met.cpp: In function 'void db(const A& ...)':
met.cpp:51:66: warning: fold-expressions only available with '-std=c++17' or '-std=gnu++17'
   51 | template<typename ...A> void db(A const&... a) { ((cout << (a)), ...); cout << endl; }
      |                                                                  ^~~
met.cpp: In function 'int main()':
met.cpp:72:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |   for (auto &[l, r, a] : Q) {
      |              ^
met.cpp:90:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   90 |       auto [l, r, x] = Q[mid];
      |            ^
#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...