제출 #1091114

#제출 시각아이디문제언어결과실행 시간메모리
1091114ThylOne새로운 문제 (POI11_met)C++14
100 / 100
1222 ms44540 KiB
//#################### //Meteors //#################### #include<bits/stdc++.h> using namespace std; using ll = long long; #define pb push_back #define all(x) x.begin(), x.end() #define rall(x) x.begin(), x.end() int nbState,nbPlanet; const int maxiState = 300000; int attempt[maxiState]; vector<int> representant[maxiState]; int nbMeteor; const int maxiMeteor = 300000; struct meteor{ int l,r; ll a; }; meteor meteors[maxiMeteor]; #define LSONE(x) (x&(-x)) struct fenwick{ vector<ll> val; fenwick(int n){ val.resize(n+2); fill(all(val),0); } void update(int pos, ll v){ while(pos<val.size()){ val[pos] += v; pos += LSONE(pos); } } ll rsq(int i){ ll re = 0; while(i){ re += val[i]; i -= LSONE(i); } return re; } ll rsq(int i,int j){ return rsq(j) - rsq(i - 1); } void ruq(int i,int j, ll a){ update(i, a); update(j+1,-a); } }; int mid(pair<int,int> a){ return (a.first+a.second)/2; } void solve(){ pair<int,int> ranges[nbState]; fill(ranges,ranges+nbState,make_pair(1,nbMeteor+1)); const int LOG = 20; for(int l = 0; l < LOG; l++){ vector<int> req[nbMeteor+2]; for(int i=0;i<nbState;i++){ if(ranges[i].first!=ranges[i].second) req[mid(ranges[i])].pb(i); } fenwick ft(nbPlanet); for(int t = 1; t<= nbMeteor; t++){ meteor &met = meteors[t - 1]; //application de la météorite if(met.l<=met.r){ ft.ruq(met.l,met.r,met.a); }else{ ft.ruq(1,met.r,met.a); ft.ruq(met.l,nbPlanet,met.a); } for(int r:req[t]){ ll tot = 0; for(int repr:representant[r]){ tot+=ft.rsq(repr); if(tot>=attempt[r])break; } if(tot>=attempt[r]){ ranges[r].second=mid(ranges[r]); }else{ ranges[r].first = mid(ranges[r])+1; } } } } for(int i = 0; i < nbState ; i++){ if(ranges[i].first!=ranges[i].second){ cerr<<"errror system merde..."<<endl; }else{ cout<<(ranges[i].second==nbMeteor+1?"NIE":to_string(ranges[i].second))<<'\n'; } } } signed main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>nbState>>nbPlanet; for(int i = 0; i<nbPlanet;i++){ int v;cin>>v; v--; representant[v].pb(i+1); } for(int i= 0;i<nbState;i++) cin>>attempt[i]; cin>>nbMeteor; for(int i = 0; i< nbMeteor ; i++){ cin>>meteors[i].l>>meteors[i].r>>meteors[i].a; } solve(); return 0; };

컴파일 시 표준 에러 (stderr) 메시지

met.cpp: In member function 'void fenwick::update(int, ll)':
met.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             while(pos<val.size()){
      |                   ~~~^~~~~~~~~~~
#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...