Submission #497047

#TimeUsernameProblemLanguageResultExecution timeMemory
497047IerusMeteors (POI11_met)C++17
0 / 100
250 ms38328 KiB
#include<bits/stdc++.h> using namespace std; #define F first #define S second #define sz size() #define pb push_back #define int long long #define all(x) (x).begin(),(x).end() #define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ; const int N = 1e5+2; int n, m, que, t[N<<2], md[N<<2]; void P(int v, int l, int r){ if(md[v] != 0){ if(l != r){ md[v<<1|1] += md[v]; md[v<<1] += md[v]; t[v<<1|1] += md[v]; t[v<<1] += md[v]; } } md[v] = 0; } void U(int l, int r, int val, int v, int tl, int tr){ P(v,tl,tr); // cerr << "l: " << l << " r: " << r << " val: " << val << " tl: " << tl << " tr: " << tr << '\n'; if(tl > r || tr < l || tr < tl) return; if(l <= tl && tr <= r){ md[v] += val; t[v] += val; P(v,tl,tr); return; } int tm = (tl + tr) >> 1; U(l,r,val,v<<1,tl,tm); U(l,r,val,v<<1|1,tm+1,tr); t[v] = t[v<<1] + t[v<<1|1]; } int G(int pos, int v, int l, int r){ P(v,l,r); if(l == r) return t[v]; int m = (l + r) >> 1; if(pos <= m) return G(pos,v<<1,l,m); else return G(pos,v<<1|1,m+1,r); } vector<int> g[N], ans(N, -1); int p[N], Q[N], L[N], R[N]; struct{int l, r, a;}q[N]; signed main(){ cin >> n >> m; for(int i = 1; i <= m; ++i){ int x; cin >> x; g[x].pb(i); } for(int i = 1; i <= n; ++i){ cin >> p[i]; } cin >> que; for(int i = 1; i <= n; ++i){ cin >> q[i].l >> q[i].r >> q[i].a; } for(int i = 1; i <= n; ++i){ L[i] = 1, R[i] = que+1; } bool ok = 1; while(ok){ ok = false; memset(t, 0, sizeof(t)); vector<int> tocheck[N]; for(int i = 1; i <= n; ++i){ if(L[i] < R[i]){ tocheck[(L[i]+R[i])/2].pb(i); } } // for(int i = 1; i <= n; ++i){ // if(tocheck[i].size()){ // cerr << i << ": "; // for(auto x: tocheck[i]) cerr << x << ' '; // cerr << '\n'; // } // } for(int i = 1; i <= que; ++i){ if(q[i].l > q[i].r){ U(q[i].l, m, q[i].a, 1, 1, m); // exit(false); U(1, q[i].r, q[i].a, 1, 1, m); }else{ U(q[i].l, q[i].r, q[i].a, 1, 1, m); } // cerr << "L: " << q[i].l << " R: " << q[i].r << " a: " << q[i].a << '\n'; // for(int i = 1; i <= m; ++i){ // cerr << G(i,1,1,m) << ' '; // }cerr << '\n'; // exit(false); // cerr << "norm\n"; // cerr << "i: " << i << '\n'; for(auto id: tocheck[i]){ // cerr << "id: " << id << '\n'; ok = true; long long sum = 0; for(auto x : g[id]){ // cerr << x << ' '; sum += G(x, 1, 1, m); if(sum >= p[id]){ break; } } // cerr << '\n'; // cerr << "sum: " << sum << '\n'; if(sum >= p[id]){ ans[id] = i; R[id] = i; }else L[id] = i + 1; } } } for(int i = 1; i <= n; ++i){ if(ans[i] == -1) cout << "NIE\n"; else cout << ans[i] << '\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...