Submission #752252

#TimeUsernameProblemLanguageResultExecution timeMemory
752252salmonMeteors (POI11_met)C++14
74 / 100
2268 ms52696 KiB
//meteors #include <bits/stdc++.h> using namespace std; long long int st[1200100]; vector<int> place[300100]; int N,M,h; int k; int g[300100]; vector<int> m[300100]; int s[300100]; int e[300100]; vector<vector<int>> days; int ans[300100]; void build(int i, int s, int e){ if(s == e){ st[i] = 0; return; } st[i] = 0; build(i * 2,s,(s+e)/2); build(i*2+1,(s+e)/2+1, e); } void update(int i, int s, int e, int S, int E, int k){ if(S <= s && e <= E){ st[i] = st[i] + k; return; } int m = (s + e)/2; if(S <= m){ update(i * 2, s, m,S,E,k); } if(m < E){ update(i*2+1,m+1,e,S,E,k); } } long long int query(int i, int s, int e, int in){ if(s == e){ return st[i]; } int m = (s + e)/2; if(in <= m){ return st[i] + query(i*2, s, m, in); } else{ return st[i] + query(i * 2+1,m + 1, e, in); } } int main(){ scanf(" %d",&N); scanf(" %d",&M); for(int i = 1; i <= M; i++){ scanf(" %d",&h); place[h].push_back(i); } for(int i = 1; i <= N; i++){ scanf(" %d",&g[i]); } scanf(" %d",&k); for(int i = 1; i <= N; i++){ s[i] = 1; e[i] = k + 1; m[(k + 2)/2].push_back(i); } for(int i = 1; i <= k ; i++){ int s,e,a; scanf(" %d",&s); scanf(" %d",&e); scanf(" %d",&a); vector<int> v = {s,e,a}; days.push_back(v); } bool flag = true; while(flag){ flag = false; build(1,1,M); for(int i = 1; i <= k; i++){ if(days[i-1][1] < days[i-1][0]){ update(1,1,M,1,days[i-1][1],days[i-1][2]); update(1,1,M,days[i-1][0],M,days[i-1][2]); } else{ update(1,1,M,days[i-1][0],days[i-1][1],days[i-1][2]); } /*for(int i = 1; i <= M; i++){ printf("%lld ",query(1,1,M,i)); } printf("\n");*/ for(int j : m[i]){ flag = true; long long int some = 0; for(int k : place[j]){ some = some + query(1,1,M,k); } if(some >= g[j]){ e[j] = (s[j] + e[j])/2; } else{ s[j] = (s[j] + e[j])/2 + 1; } if(e[j] != s[j]){ m[(s[j] + e[j])/2].push_back(j); } else{ ans[j] = s[j]; } } m[i].clear(); } } for(int i = 1; i <= N; i++){ if(ans[i] == k + 1){ printf("NIE\n"); } else{ printf("%d\n",ans[i]); } } }

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
met.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf(" %d",&M);
      |     ~~~~~^~~~~~~~~~
met.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         scanf(" %d",&h);
      |         ~~~~~^~~~~~~~~~
met.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         scanf(" %d",&g[i]);
      |         ~~~~~^~~~~~~~~~~~~
met.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf(" %d",&k);
      |     ~~~~~^~~~~~~~~~
met.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         scanf(" %d",&s);
      |         ~~~~~^~~~~~~~~~
met.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         scanf(" %d",&e);
      |         ~~~~~^~~~~~~~~~
met.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf(" %d",&a);
      |         ~~~~~^~~~~~~~~~
#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...