Submission #41309

#TimeUsernameProblemLanguageResultExecution timeMemory
41309wzyMeteors (POI11_met)C++14
74 / 100
1597 ms34560 KiB
#include <bits/stdc++.h> using namespace std; #define F first #define S second #define pii pair<int,int> #define pb push_back int n ,m , k , ans[300005] , qt[300005] , l[300005] , r[300005] ; long long bit[300005]; vector<int> own[300005]; vector<int> sweep[300005]; pair<pii , unsigned int> querys[300005]; void upd(int x , int v){ for(int i = x ; i < 300005; i += (i&-i)){ bit[i] += v; } return; } long long gt(int x){ int s = 0; for(int i = x ; i > 0 ; i -=(i&-i)){ s+= bit[i]; } return s; } void update(int l , int r , int v){ if(l <= r){ upd(l , v); upd(r + 1 , -v); } else{ upd(l , v); upd(1 , v); upd(r + 1 , -v); } return; } long long query(int x){ return gt(x); } int main(){ scanf("%d%d" , &n , &m); for(int i = 1 ; i <= m;i++){ int x; scanf("%d" , &x); own[x].pb(i); } for(int i = 1 ; i <= n;i++) scanf("%d" , &qt[i]); scanf("%d" , &k); for(int i = 1 ; i <= k ; i++){ scanf("%d%d%d" , &querys[i].F.F , &querys[i].F.S , &querys[i].S); } for(int i = 1 ; i <= n;i++) l[i] = 1 , r[i] = k , ans[i] = -1; while(true){ bool cabou = true; for(int i = 1 ; i <= n; i++){ if(l[i] <= r[i]){ sweep[(l[i] + r[i])/2].pb(i); cabou = false; } } if(cabou) break; for(int i = 1 ; i <= m + 1 ; i++) bit[i] = 0; for(int i = 1 ; i <= k ; i++){ update(querys[i].F.F , querys[i].F.S , querys[i].S); while(sweep[i].size()){ int u = sweep[i].back(); sweep[i].pop_back(); long long sj = 0; bool deu = false; for(int w = 0 ; w < own[u].size() ; w++){ int v = own[u][w]; sj += query(v); sj = min(sj , 1000000009LL); if(sj >= qt[u]){ deu = true; break; } } if(deu){ if(l[u] == r[u]) ans[u] = i , r[u] = -1; else r[u] = i; } else{ if(l[u] == r[u]) r[u] = -1; else l[u] = i + 1; } } } } for(int i = 1 ; i <= n; i++){ if(ans[i] == -1) puts("NIE"); else printf("%d\n" , ans[i] ); } }

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:77:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int w = 0 ;  w < own[u].size() ; w++){
                            ^
met.cpp:48:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d%d" , &n , &m);
                             ^
met.cpp:51:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d" , &x);
                       ^
met.cpp:54:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      for(int i = 1 ; i  <= n;i++) scanf("%d" , &qt[i]);
                                                       ^
met.cpp:55:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d" , &k);
                      ^
met.cpp:57:71: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d%d" , &querys[i].F.F , &querys[i].F.S , &querys[i].S);
                                                                       ^
#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...