제출 #850319

#제출 시각아이디문제언어결과실행 시간메모리
850319NemanjaSo2005추월 (IOI23_overtaking)C++17
19 / 100
8 ms1624 KiB
#include "overtaking.h" #include<bits/stdc++.h> #define ll long long using namespace std; ll N,M,L,X,niz[1005];; struct bus{ ll w,krece,stize; bool operator < (const bus &a) const{ return krece<a.krece; } } bpp; bool cmp(bus a,bus b){ return a.w>b.w; } struct slog{ ll l,r,ans; const bool operator < (const slog &a) const{ return l<a.l; } } pp; set<slog> S; set<bus> busevi[1005]; pair<set<bus>,vector<bus>> resi(vector<bus> V,ll d){ set<bus> A; vector<bus> B; if(V.size()==0) return {A,B}; bpp.krece=bpp.stize=-1; A.insert(bpp); sort(V.begin(),V.end(),cmp); for(int i=0;i<V.size();i++){ bpp.krece=V[i].krece; auto it=A.lower_bound(bpp); it--; V[i].stize=d*V[i].w+V[i].krece; if(V[i].stize<(*it).stize) V[i].stize=(*it).stize; else A.insert(V[i]); B.push_back(V[i]); } bpp.krece=bpp.stize=-1; A.erase(bpp); return {A,B}; } ll arrival_time(ll Y); void dodajint(slog x){ if(S.size()==0){ S.insert(x); return; } auto poc=S.upper_bound(x); poc--; vector<slog> B,D; D.push_back(x); for(auto it=poc;it!=S.end();it++){ slog tren=*it; if(tren.l>x.r) break; if(tren.r<x.l) continue; if(tren.l>=x.l and tren.r<=x.r){ B.push_back(tren); continue; } if(tren.l<x.l and tren.r>=x.l){ B.push_back(tren); tren.r=x.l-1; D.push_back(tren); } if(tren.l<=x.r and tren.r>x.r){ B.push_back(tren); tren.l=x.r+1; D.push_back(tren); } } for(int i=0;i<B.size();i++) S.erase(B[i]); for(int i=0;i<D.size();i++) S.insert(D[i]); } void init(int l,int n,vector<ll> t,vector<int> w,int x,int m,vector<int> s){ N=n; L=l; M=m; X=x; for(int i=0;i<M;i++) niz[i]=s[i]; vector<bus> V; for(int i=0;i<N;i++){ if(w[i]<=X) continue; bpp.w=w[i]; bpp.krece=t[i]; bpp.stize=t[i]; V.push_back(bpp); } for(int i=0;i+1<M;i++){ for(int j=0;j<V.size();j++) V[j].krece=V[j].stize; auto odg=resi(V,niz[i+1]-niz[i]); busevi[i]=odg.first; V=odg.second; // cout<<"BUSEVI "<<i<<endl; // for(auto it=busevi[i].begin();it!=busevi[i].end();it++) // cout<<(*it).krece<<" "<<(*it).stize<<" "<<(*it).w<<endl; } vector<slog> D; for(int i=M-2;i>=0;i--){ //cout<<i<<endl; ll d=(niz[i+1]-niz[i]); for(auto it=busevi[i].begin();it!=busevi[i].end();it++){ bpp=*it; slog tren; tren.l=bpp.krece+1; tren.r=bpp.stize-d*X; //cout<<tren.l<<" "<<tren.r<<" ans od "<<bpp.stize-niz[i+1]*X<<endl; tren.ans=arrival_time(bpp.stize-niz[i+1]*X); tren.l-=niz[i]*X; tren.r-=niz[i]*X; D.push_back(tren); //cout<<tren.l<<" "<<tren.r<<" "<<tren.ans<<endl; } for(int j=0;j<D.size();j++) dodajint(D[j]); //cout<<"SET:"<<endl; //for(auto it=S.begin();it!=S.end();it++) // cout<<(*it).l<<" "<<(*it).r<<" "<<(*it).ans<<endl; D.clear(); } } ll arrival_time(ll Y){ if(S.size()==0) return Y+X*L; pp.l=Y; slog x; x.ans=-1; auto it=S.upper_bound(pp); if(it!=S.begin()) it--; if((*it).l<=Y and (*it).r>=Y) return (*it).ans; return Y+X*L; }

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

overtaking.cpp: In function 'std::pair<std::set<bus>, std::vector<bus> > resi(std::vector<bus>, long long int)':
overtaking.cpp:31:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bus>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |    for(int i=0;i<V.size();i++){
      |                ~^~~~~~~~~
overtaking.cpp: In function 'void dodajint(slog)':
overtaking.cpp:77:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |    for(int i=0;i<B.size();i++)
      |                ~^~~~~~~~~
overtaking.cpp:79:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |    for(int i=0;i<D.size();i++)
      |                ~^~~~~~~~~
overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bus>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |       for(int j=0;j<V.size();j++)
      |                   ~^~~~~~~~~
overtaking.cpp:124:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |       for(int j=0;j<D.size();j++)
      |                   ~^~~~~~~~~
overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:136:10: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  136 |     slog x;
      |          ^
#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...