Submission #491298

#TimeUsernameProblemLanguageResultExecution timeMemory
491298Wayne_YanMeteors (POI11_met)C++17
100 / 100
1168 ms52604 KiB
#include <bits/extc++.h> using namespace std; using namespace __gnu_pbds; typedef int64_t ll; typedef long double ld; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define pb emplace_back #define mp make_pair #define mt make_tuple #define pii pair<int,int> #define F(n) Fi(i,n) #define Fi(i,n) Fl(i,0,n) #define Fl(i,l,n) for(int i=l;i<n;i++) #define RF(n) RFi(i,n) #define RFi(i,n) RFl(i,0,n) #define RFl(i,l,n) for(int i=n-1;i>=l;i--) #define all(v) begin(v),end(v) #define siz(v) (ll(v.size())) #define get_pos(v,x) (lower_bound(all(v),x)-begin(v)) #define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v)) #define mem(v,x) memset(v,x,sizeof v) #define ff first #define ss second #define mid ((l+r)>>1) #define RAN(a,b) uniform_int_distribution<int> (a, b)(rng) #define debug(x) (cerr << (#x) << " = " << x << "\n") template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >; template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >; template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; const int maxN = 3e5+10; const int maxC = 1e9; struct BIT{ long long arr[maxN]; void modify(int c, int diff){ if(c == 0) return; assert(c > 0); while(c < maxN){ arr[c] += diff; c += (c&-c); } } int query(int c){ assert(c > 0); long long ans = 0; while(c){ ans += arr[c]; c -= (c&-c); } if(ans > maxC) ans = maxC; return ans; } void modify(int ql, int qr, int diff){ modify(qr+1, -diff); modify(ql, diff); } BIT () {fill(arr, arr+maxN, 0);} } bit; int got[maxN]; int N,M,K; int O[maxN]; int L[maxN], R[maxN], C[maxN]; int T[maxN]; int ans[maxN]; bool flag[maxN]; void solve(vector<int> lands, int ql, int qr){ if(ql + 1 == qr){ for(int i : lands){ ans[O[i]] = ql; } return; } int qm = (ql+qr) >> 1; Fl(i, ql, qm){ if(L[i] <= R[i]){ bit.modify(L[i], R[i], C[i]); }else{ bit.modify(L[i], M, C[i]); bit.modify(1, R[i], C[i]); } } vector<int> llands, rlands; for(int i : lands){ got[O[i]] += bit.query(i); if(got[O[i]] >= maxC) got[O[i]] = maxC; } for(int i : lands){ if(got[O[i]] >= T[O[i]] && (!flag[O[i]])){ llands.pb(i); }else{ rlands.pb(i); if(!flag[O[i]]){ flag[O[i]] = true; T[O[i]] -= got[O[i]]; } } } Fl(i, ql, qm){ if(L[i] <= R[i]){ bit.modify(L[i], R[i], -C[i]); }else{ bit.modify(L[i], M, -C[i]); bit.modify(1, R[i], -C[i]); } } for(int i : lands){ got[O[i]] = 0; flag[O[i]] = 0; } solve(llands, ql, qm); solve(rlands, qm, qr); } signed main(){ cin >> N >> M; bool covered[maxN] = {}; F(M){ cin >> O[i+1]; covered[O[i+1]] = true; } F(N){ cin >> T[i+1]; } cin >> K; F(K){ cin >> L[i+1] >> R[i+1] >> C[i+1]; } L[0] = 1; R[0] = M; C[0] = 0; L[K+1] = 1; R[K+1] = M; C[K+1] = 1e9; vector<int> orig; Fl(i, 1, M+1){ orig.pb(i); } solve(orig, 0, K+2); Fl(i, 1, N+1){ if(covered[i] == false && T[i]){ printf("NIE\n"); }else if(ans[i] == K+1){ printf("NIE\n"); }else{ printf("%d\n", ans[i]); } } return 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...