Submission #1016130

#TimeUsernameProblemLanguageResultExecution timeMemory
1016130vjudge1Meteors (POI11_met)C++17
74 / 100
187 ms65540 KiB
#include<bits/stdc++.h> using namespace std; #ifdef ONPC #include"debug.h" #else #define debug(...) 42 #endif #define endl '\n' #define ll long long #define pii pair<int,int> #define F first #define S second #define pb push_back #define sz(a) (int)a.size() #define all(a) a.begin(),a.end() template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } const int mod = 1e9 + 7; const int MAXN = 3e5 + 2; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; const int off = (1 << 19); struct sgt{ int val[MAXN * 10], rs[MAXN * 10], ls[MAXN * 10], head = 1; int version[MAXN]; int my_new(int u = 0){ val[head] = val[u]; ls[head] = ls[u]; rs[head] = rs[u]; return head++; } int update(int l, int r, int v, int u, int lo = 0, int hi = off){ if (r <= lo || hi <= l) return u; u = my_new(u); if (l <= lo && hi <= r){ val[u] += v; //ckmin(val[u], int(1e9)); return u; } int mi = (lo + hi) >> 1; ls[u] = update(l, r, v, ls[u], lo, mi); rs[u] = update(l, r, v, rs[u], mi, hi); return u; } void query(int l, int r, int v, int cur){ if (l <= r){ version[cur] = update(l, r + 1, v, version[cur - 1]); } else { version[cur] = update(l, off, v, version[cur - 1]); version[cur] = update(0, r + 1, v, version[cur]); } } int get(int pos, int u, int lo = 0, int hi = off){ if (pos >= hi || pos < lo) return 0; if (!u) return 0; int mi = (lo + hi) >> 1; if (pos < mi) return val[u] + get(pos, ls[u], lo, mi); else return val[u] + get(pos, rs[u], mi, hi); } } seg; struct postions { int head[MAXN], next[MAXN], val[MAXN], tot = 1; void add(int num, int pos){ next[tot] = head[num]; val[tot] = pos; head[num] = tot; tot++; } } pos; int need[MAXN]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; for (int i = 1; i <= m; i++){ int x; cin >> x; pos.add(x, i); } for (int i = 1; i <= n; i++){ cin >> need[i]; } int q; cin >> q; for (int i = 1; i <= q; i++){ int l, r, v; cin >> l >> r >> v; seg.query(l, r, v, i); } for (int i = 1; i <= n; i++){ int lo = 0, hi = q + 1; while (hi - lo > 1){ int mi = (lo + hi) >> 1; int sum = 0; for (int idx = pos.head[i]; idx; idx = pos.next[idx]){ int cur = pos.val[idx]; sum += seg.get(cur, seg.version[mi]); ckmin(sum, int(1e9)); } if (sum >= need[i]) hi = mi; else lo = mi; } if (hi != q + 1) cout << hi << endl; else cout << "NIE\n"; } }
#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...