Submission #41240

#TimeUsernameProblemLanguageResultExecution timeMemory
41240wzyMeteors (POI11_met)C++11
24 / 100
6068 ms23348 KiB
#include <bits/stdc++.h> #define F first #define S second using namespace std; inline int read_int() { register char c=0; int a=0; while (c<33) c=getchar(); while (c>33) { a=a*10+c-'0', c=getchar(); } return a; } int ans[300005],n , m , qt[300005] , k; vector<int> o[300005]; vector<pair< pair<int,int> , int > > querys; long long bit[300005]; void upd(int x , int vl){ for(int i = x; i < 300005 ; i+= (i&-i)){ bit[i] += vl; } } long long qr(int x){ if(x == 0) return 0; long long s = 0; for(int i = x ; i > 0 ; i-=(i&-i)){ if(s >= (int) 1e17){ if(bit[i] >= (int) 1e17) continue; else s += bit[i]; } else if(s <= -((int) 1e17)){ if(bit[i] <= -((int) 1e17)) continue; else s+= bit[i]; } else s+= bit[i]; } return s; } void update(int x , int y, int vl){ upd(x, vl); upd(y+1, -vl); } long long query(int x){ return qr(x); } void solve(int l , int r , const vector<int> & opt){ int mid = (l+r)/2; memset(bit, 0 , sizeof bit); for(int i = 0 ; i < mid ; i++){ pair< pair<int,int> , int> info = querys[i]; if(info.F.F > info.F.S){ update(info.F.F , m , info.S); update(1, info.F.S , info.S); } else{ update(info.F.F , info.F.S , info.S); } } vector<int> leftc , rightc; for(int j = 0 ; j < opt.size() ; j++){ int i = opt[j]; int sj = 0; for(int w = 0 ; w < o[i].size(); w++){ int c = o[i][w]; sj += query(c); if(sj >= qt[i]) break; } if(sj >= qt[i]) leftc.push_back(i); else rightc.push_back(i); } if(l == r){ for(int i = 0 ; i < leftc.size();i++) ans[leftc[i]] = l; for(int i = 0 ; i < rightc.size();i++) ans[rightc[i]] = -1; leftc.clear() , rightc.clear(); return; } else{ if(leftc.size()){ solve(l , mid , leftc); leftc.clear(); } if(rightc.size()){ solve(mid + 1 , r , rightc); rightc.clear(); } } } int main(){ n = read_int() , m = read_int(); vector<int> candidatos; for(int i = 1 ; i <= m;i++){ int x; x = read_int(); o[x].push_back(i); } for(int i = 1 ; i<= n ;i++){ qt[i] = read_int(); candidatos.push_back(i); } k = read_int(); for(int i = 0 ; i < k ;i ++){ int l , r ,v; l = read_int() , r = read_int() , v =read_int(); querys.push_back(pair<pair<int,int> , int>(pair<int,int>(l , r) , v)); } solve(1, k , candidatos); 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 'void solve(int, int, const std::vector<int>&)':
met.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0 ; j < opt.size() ; j++){
                    ^
met.cpp:73:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int w = 0 ; w < o[i].size(); w++){
                     ^
met.cpp:82:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < leftc.size();i++) ans[leftc[i]] = l;
                     ^
met.cpp:83:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < rightc.size();i++) ans[rightc[i]] = -1;
                     ^
#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...