Submission #624424

#TimeUsernameProblemLanguageResultExecution timeMemory
624424andrei_boacaTram (CEOI13_tram)C++14
100 / 100
236 ms24528 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; ll n,m; bool have[150005][3]; auto comp=[](pair<ll,pii> a, pair<ll, pii> b) { if(a.first!=b.first) return a.first>b.first; int linA=a.second.first,linB=b.second.first; if(linA!=linB) return linA<linB; int colA=a.second.second,colB=b.second.second; return colA<colB; }; multiset<pair<ll,pii>,decltype(comp)> s(comp); set<int> poz; pii where[30005],best[55]; ll dist(ll a, ll b, ll c, ll d) { return (a-c)*(a-c)+(b-d)*(b-d); } int rgt[150005],lft[150005]; vector<int> v; void putseg(int st,int dr) { int mij=(st+dr)/2; for(int a=st;a<=st+1;a++) if(a>=st&&a<=dr&&a>=1&&a<=n) for(int j=1;j<=2;j++) if(!have[a][j]) { ll minim=1e18; for(int k=1;k<=2;k++) { if(have[st][k]&&st>0) minim=min(minim,dist(st,k,a,j)); if(have[dr][k]&&dr<=n) minim=min(minim,dist(dr,k,a,j)); } s.insert({minim,{a,j}}); } for(int a=mij-1;a<=mij+1;a++) if(a>=st&&a<=dr&&a>=1&&a<=n) for(int j=1;j<=2;j++) if(!have[a][j]) { ll minim=1e18; for(int k=1;k<=2;k++) { if(have[st][k]&&st>0) minim=min(minim,dist(st,k,a,j)); if(have[dr][k]&&dr<=n) minim=min(minim,dist(dr,k,a,j)); } s.insert({minim,{a,j}}); } for(int a=dr-1;a<=dr;a++) if(a>=st&&a<=dr&&a>=1&&a<=n) for(int j=1;j<=2;j++) if(!have[a][j]) { ll minim=1e18; for(int k=1;k<=2;k++) { if(have[st][k]&&st>0) minim=min(minim,dist(st,k,a,j)); if(have[dr][k]&&dr<=n) minim=min(minim,dist(dr,k,a,j)); } s.insert({minim,{a,j}}); } } void eraseseg(int st,int dr) { int mij=(st+dr)/2; for(int a=st;a<=st+1;a++) if(a>=st&&a<=dr&&a>=1&&a<=n) for(int j=1;j<=2;j++) if(!have[a][j]) { ll minim=1e18; for(int k=1;k<=2;k++) { if(have[st][k]&&st>0) minim=min(minim,dist(st,k,a,j)); if(have[dr][k]&&dr<=n) minim=min(minim,dist(dr,k,a,j)); } s.erase(s.find({minim,{a,j}})); } for(int a=mij-1;a<=mij+1;a++) if(a>=st&&a<=dr&&a>=1&&a<=n) for(int j=1;j<=2;j++) if(!have[a][j]) { ll minim=1e18; for(int k=1;k<=2;k++) { if(have[st][k]&&st>0) minim=min(minim,dist(st,k,a,j)); if(have[dr][k]&&dr<=n) minim=min(minim,dist(dr,k,a,j)); } s.erase(s.find({minim,{a,j}})); } for(int a=dr-1;a<=dr;a++) if(a>=st&&a<=dr&&a>=1&&a<=n) for(int j=1;j<=2;j++) if(!have[a][j]) { ll minim=1e18; for(int k=1;k<=2;k++) { if(have[st][k]&&st>0) minim=min(minim,dist(st,k,a,j)); if(have[dr][k]&&dr<=n) minim=min(minim,dist(dr,k,a,j)); } s.erase(s.find({minim,{a,j}})); } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>m; int cur=0; have[0][1]=have[0][2]=1; have[n+1][1]=have[n+1][2]=1; rgt[0]=n+1; putseg(0,n+1); poz.insert(0); poz.insert(n+1); while(m--) { cur++; char c; cin>>c; if(c=='E') { /*if(s.empty()) { cout<<1<<' '<<1<<'\n'; s.insert(1); have[1][1]=1; where[cur]={1,1}; continue; }*/ auto it=s.begin(); int lin=(*it).second.first; int col=(*it).second.second; where[cur]={lin,col}; cout<<lin<<' '<<col<<'\n'; if(have[lin][1]+have[lin][2]==0) { int st=*prev(poz.lower_bound(lin)); int dr=*poz.upper_bound(lin); eraseseg(st,dr); have[lin][col]=1; putseg(st,lin); putseg(lin,dr); poz.insert(lin); } else { int st=*prev(poz.lower_bound(lin)); int dr=*poz.upper_bound(lin); eraseseg(st,lin); eraseseg(lin,dr); have[lin][col]=1; putseg(st,lin); putseg(lin,dr); } } else { int p; cin>>p; int lin=where[p].first,col=where[p].second; if(have[lin][1]+have[lin][2]==1) { poz.erase(lin); int st=*prev(poz.lower_bound(lin)); int dr=*poz.upper_bound(lin); eraseseg(st,lin); eraseseg(lin,dr); have[lin][col]=0; putseg(st,dr); } else { int st=*prev(poz.lower_bound(lin)); int dr=*poz.upper_bound(lin); eraseseg(st,lin); eraseseg(lin,dr); have[lin][col]=0; putseg(st,lin); putseg(lin,dr); } } } return 0; }
#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...