Submission #1013046

#TimeUsernameProblemLanguageResultExecution timeMemory
1013046octaneMeteors (POI11_met)C++17
74 / 100
2862 ms57768 KiB
#pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include<stdio.h> #include<algorithm> #include<vector> using namespace std; typedef long long ll; typedef pair<int, int> pi; typedef pair<pi, vector<int>> pii; int n, k, q, x; ll goal[300005]; int l[300005]; int r[300005]; ll a[300005]; ll tree[1200005]; vector<int> num[300005]; int res[300005]; vector<pii> vec[100]; void update(int node, int s, int e, int l, ll v){ if(e<l||l<s) return; if(s==e){ tree[node] += v; return; } int m = (s+e)>>1; update(node<<1, s, m, l, v); update(node<<1|1, m+1, e, l, v); tree[node] = tree[node<<1]+tree[node<<1|1]; } ll query(int node, int s, int e, int l, int r){ if(e<l||r<s) return 0; if(l<=s&&e<=r) return tree[node]; int m = (s+e)>>1; return query(node<<1, s, m, l, r)+query(node<<1|1, m+1, e, l, r); } int main(){ scanf("%d %d", &n, &k); for(int i=1;i<=k;i++){ scanf("%d", &x); num[x].push_back(i); } for(int i=1;i<=n;i++) scanf("%lld", &goal[i]); scanf("%d", &q); vector<int> emp; for(int i=1;i<=n;i++) emp.push_back(i); vec[0].push_back(pii(pi(0, q-1), emp)); for(int i=0;i<q;i++) scanf("%d %d %lld", &l[i], &r[i], &a[i]); int idx = 0; while(!vec[idx].empty()){ for(int i=1;i<=4*k;i++) tree[i] = 0; int prv = 0; for(auto p: vec[idx]){ int s = p.first.first; int e = p.first.second; int m = (s+e)>>1; for(int i=prv;i<=m;i++){ if(l[i]<=r[i]){ update(1, 1, k+1, l[i], a[i]); update(1, 1, k+1, r[i]+1, -a[i]); } else{ update(1, 1, k+1, l[i], a[i]); update(1, 1, k+1, k+1, -a[i]); update(1, 1, k+1, 1, a[i]); update(1, 1, k+1, r[i]+1, -a[i]); } } prv = m+1; if(s==e){ for(auto u: p.second){ ll sm = 0; for(auto w: num[u]) sm += query(1, 1, k+1, 1, w); if(sm>=goal[u]) res[u] = s; else res[u] = -1; } continue; } vector<int> vec1; vector<int> vec2; for(auto u: p.second){ ll sm = 0; for(auto w: num[u]) sm += query(1, 1, k+1, 1, w); if(sm>=goal[u]) vec1.push_back(u); else vec2.push_back(u); } vec[idx+1].push_back(pii(pi(s, m), vec1)); vec[idx+1].push_back(pii(pi(m+1, e), vec2)); } idx++; } for(int i=1;i<=n;i++){ if(res[i]==-1) printf("NIE\n"); else printf("%d\n", res[i]+1); } }

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
met.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
met.cpp:47:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     for(int i=1;i<=n;i++) scanf("%lld", &goal[i]);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~
met.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
met.cpp:52:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     for(int i=0;i<q;i++) scanf("%d %d %lld", &l[i], &r[i], &a[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...