제출 #969728

#제출 시각아이디문제언어결과실행 시간메모리
969728Warinchai휴가 (IOI14_holiday)C++14
7 / 100
5054 ms7004 KiB
#include"holiday.h" #include<bits/stdc++.h> using namespace std; long long rvid[100005]; struct segtree{ long long info[400005]; long long freq[400005]; void upd(int st,int en,int i,int pos,int val){ if(st>pos||en<pos)return; //cerr<<"range:"<<st<<" "<<en<<"\n"; if(st==en)return info[i]+=val,freq[i]++,void(); int m=(st+en)/2; upd(st,m,i*2,pos,val); upd(m+1,en,i*2+1,pos,val); info[i]=info[i*2]+info[i*2+1]; freq[i]=freq[i*2]+freq[i*2+1]; } void un_upd(int st,int en,int i,int pos,int val){ if(st>pos||en<pos)return; if(st==en)return info[i]-=val,freq[i]-=1,void(); int m=(st+en)/2; un_upd(st,m,i*2,pos,val); un_upd(m+1,en,i*2+1,pos,val); info[i]=info[i*2]+info[i*2+1]; freq[i]=freq[i*2]+freq[i*2+1]; } long long fans(int st,int en,int i,int pos){ //cerr<<"Range:"<<st<<" "<<en<<"\n"; if(st==en)return freq[i]*(rvid[st]); if(st==en)return freq[i]*(rvid[st]); int m=(st+en)/2; if(pos<=freq[i*2+1])return fans(m+1,en,i*2+1,pos); else return fans(st,m,i*2,pos-freq[i*2+1])+info[i*2+1]; } }tr; vector<long long>v; int id[100005]; map<int,int>mp; long long int findMaxAttraction(int n, int start, int d, int attraction[]) { for(int i=0;i<n;i++)if(!mp[attraction[i]])v.push_back(attraction[i]),mp[attraction[i]]++; sort(v.begin(),v.end()); for(int i=0;i<v.size();i++)rvid[i+1]=v[i]; for(int i=0;i<n;i++)id[i]=lower_bound(v.begin(),v.end(),attraction[i])-v.begin()+1; long long ans=0; vector<int>tinf; for(int i=0;i<n;i++){ //tinf.clear(); for(int j=i;j<n;j++){ //tinf.push_back(attraction[j]); //sort(tinf.begin(),tinf.end(),greater<int>()); //int tsum=0; //int x=d-min(abs(i-start),abs(j-start))*2-max(abs(i-start),abs(j-start)); //int y=tinf.size(); //for(int k=0;k<min(x,y);k++)tsum+=tinf[k]; //cerr<<i<<" "<<j<<"\n"; tr.upd(1,n,1,id[j],attraction[j]); //cerr<<tr.info[1]<<" "<<tr.freq[1]<<"\n"; //int temp=tr.fans(1,n,1,d-min(abs(i-start),abs(j-start))*2-max(abs(i-start),abs(j-start))); //assert(tsum==temp); if(start>=i&&start<=j&&min(abs(i-start),abs(j-start))*2+max(abs(i-start),abs(j-start))<=d)ans=max(ans,tr.fans(1,n,1,d-min(abs(i-start),abs(j-start))*2-max(abs(i-start),abs(j-start))))/*,cerr<<tr.fans(1,n,1,d-min(abs(i-start),abs(j-start))*2-max(abs(i-start),abs(j-start)))<<"\n"*/; //cerr<<"max:"<<ans<<"\n"; } //cerr<<tr.info[1]<<" "<<tr.freq[1]<<"\n"; for(int j=i;j<n;j++){ tr.un_upd(1,n,1,id[j],attraction[j]); } } return ans; }

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

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0;i<v.size();i++)rvid[i+1]=v[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...