Submission #29312

#TimeUsernameProblemLanguageResultExecution timeMemory
29312tlwpdusMeteors (POI11_met)C++11
100 / 100
3383 ms38588 KiB
#include <bits/stdc++.h> #define s first #define e second using namespace std; typedef long long ll; typedef pair<int,int> pii; int n, m, k; struct query { int l, r; ll a; query(){} query(int l, int r, ll a):l(l),r(r),a(a){} }; struct idxtree { ll tree[1050000]; int key = 524288; void init() { for (int i=0;i<key*2;i++) tree[i] = 0; } void updr(int s, int e, ll val) { s+=key;e+=key; while(s<=e) { if (s&1) tree[s] += val; if (~e&1) tree[e] += val; s = (s+1)>>1; e = (e-1)>>1; } } ll getv(int idx) { ll res = 0; idx += key; while(idx>0) { res += tree[idx]; idx>>=1; } return res; } void upd(int s, int e, ll val) { if (s<=e) updr(s,e,val); else { updr(s,m-1,val); updr(0,e,val); } } } it; int own[300100]; vector<int> lis[300100]; ll p[300100]; query arr[300100]; pii loc[300100]; pii yan[300100]; int res[300100]; void init(int s, int e) { if (s>e) return; int m = (s+e)>>1; yan[m] = pii(s,e); init(s,m-1); init(m+1,e); } void pb() { int i, j, pp = 0; for (i=0;i<n;i++) loc[i] = pii((k+1)/2,i); init(1,k); while(pp<n) { bool flag = 1; it.init(); j = 0; int cn = n-pp; for (i=1;i<=k;i++) { it.upd(arr[i-1].l,arr[i-1].r,arr[i-1].a); while(j<cn&&loc[j].first==i) { int v = loc[j].second; flag = 0; ll sum = 0; for (int l : lis[v]) { sum += it.getv(l); sum = min(sum,1000000100LL); } if (sum>=p[v]) { if (i==yan[i].s) { res[v] = i; loc[j].first = k+10; pp++; } else loc[j].first = (yan[i].s+i-1)/2; } else { if (i==yan[i].e) { res[v] = i+1; loc[j].first = k+10; pp++; } else loc[j].first = (yan[i].e+i+1)/2; } j++; } } if (flag) break; sort(loc,loc+cn); } } int main() { int i; scanf("%d%d",&n,&m); for (i=0;i<m;i++) { scanf("%d",&own[i]); own[i]--; lis[own[i]].push_back(i); } for (i=0;i<n;i++) scanf("%lld",&p[i]); scanf("%d",&k); for (i=0;i<k;i++) { int l, r; ll a; scanf("%d%d%lld",&l,&r,&a); l--; r--; arr[i] = query(l,r,a); } pb(); for (i=0;i<n;i++) { if (res[i]>=k+1) printf("NIE\n"); else printf("%d\n",res[i]); } return 0; }

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:110:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
met.cpp:112:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&own[i]); own[i]--;
                      ^
met.cpp:115:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i=0;i<n;i++) scanf("%lld",&p[i]);
                                       ^
met.cpp:116:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&k);
                ^
met.cpp:119:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld",&l,&r,&a); l--; r--;
                             ^
#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...