| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 328891 |
2020-11-18T11:42:43 Z |
htc001 |
Tram (CEOI13_tram) |
C++14 |
|
98 ms |
12780 KB |
#include<bits/stdc++.h>
using namespace std;
int readint(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int ntmp;
int ctmp[15];
void printint(int x){
ntmp=0;
while(x){
ctmp[++ntmp]=x%10;
x/=10;
}
while(ntmp) putchar(ctmp[ntmp--]+'0');
}
typedef pair<int,int> pii;
typedef pair<long long,pii> plii;
typedef pair<int,pii> piii;
const int N=150005;
int n,q,m,cs;
int used[N][2],lft[N];
pii ap[N];
set<int> st,one;
set<piii> bt[3][3];
inline int Status(int x){
if(used[x][0]==1&&used[x][1]==1) return 2;
if(used[x][0]) return 0;
if(used[x][1]) return 1;
return -1;
}
void iinsert(int x,int y){
if(Status(x)!=Status(y)) bt[Status(x)][Status(y)].insert(make_pair(x-y,make_pair(x,y)));
else bt[Status(x)][Status(y)].insert(make_pair(-((y-x)/2),make_pair(x,y)));
}
void eerase(int x,int y){
if(Status(x)!=Status(y)) bt[Status(x)][Status(y)].erase(make_pair(x-y,make_pair(x,y)));
else bt[Status(x)][Status(y)].erase(make_pair(-((y-x)/2),make_pair(x,y)));
}
void Dec(int x){
int pre=-1,suf=-1;
set<int>::iterator it=st.find(x);
if(it!=st.begin()){
it--;
pre=*it;
it++;
}
it++;
if(it!=st.end()) suf=*it;
it--;
if(pre!=-1) eerase(pre,x);
if(suf!=-1) eerase(x,suf);
if(pre!=-1&&suf!=-1) iinsert(pre,suf);
st.erase(x);
}
void Inc(int x){
st.insert(x);
int pre=-1,suf=-1;
set<int>::iterator it=st.find(x);
if(it!=st.begin()){
it--;
pre=*it;
it++;
}
it++;
if(it!=st.end()) suf=*it;
it--;
if(pre!=-1) iinsert(pre,x);
if(suf!=-1) iinsert(x,suf);
if(pre!=-1&&suf!=-1) eerase(pre,suf);
}
void Insert(int x,int y){
if(Status(x)!=-1) Dec(x);
m++;
used[x][y]=1;
lft[x]--;
if(!lft[x]) one.erase(x);
ap[cs]=make_pair(x,y);
printint(x);
putchar(' ');
printint(y+1);
putchar('\n');
Inc(x);
}
void Erase(int x,int y){
Dec(x);
m--;
used[x][y]=0;
if(!lft[x]) one.insert(x);
lft[x]++;
if(Status(x)!=-1) Inc(x);
}
plii MAX(plii x,plii y){
if(x.first>y.first) return x;
if(x.first<y.first) return y;
if(x.second<y.second) return x;
return y;
}
int main(){
n=readint();
q=readint();
for(int i=1;i<=n;i++){
lft[i]=2;
one.insert(i);
}
while(++cs<=q){
char ch=getchar();
while(ch!='E'&&ch!='L') ch=getchar();
if(ch=='E'){
if(m==0) Insert(1,0);
else{
plii ans=make_pair(0ll,pii(0,0));
for(int i=0;i<3;i++) for(int j=0;j<3;j++) if(!bt[i][j].empty()){
int x=bt[i][j].begin()->second.first,y=bt[i][j].begin()->second.second;
int mid=(x+y)/2;
for(int ii=mid;ii<=min(mid+1,y);ii++) for(int jj=0;jj<2;jj++) if(!used[ii][jj]){
long long dis=1000000000000000000ll;
for(int k=0;k<2;k++){
if(used[x][k]) dis=min(dis,1ll*(x-ii)*(x-ii)+1ll*(k-jj)*(k-jj));
if(used[y][k]) dis=min(dis,1ll*(y-ii)*(y-ii)+1ll*(k-jj)*(k-jj));
}
ans=MAX(ans,make_pair(dis,pii(ii,jj)));
}
}
set<int>::iterator it=st.begin();
int x=*it;
int ii=1;
for(int jj=0;jj<2;jj++) if(!used[ii][jj]){
long long dis=1000000000000000000ll;
for(int k=0;k<2;k++) if(used[x][k]) dis=min(dis,1ll*(x-ii)*(x-ii)+1ll*(k-jj)*(k-jj));
ans=MAX(ans,make_pair(dis,pii(ii,jj)));
}
it=st.end();it--;x=*it;
ii=n;
for(int jj=0;jj<2;jj++) if(!used[ii][jj]){
long long dis=1000000000000000000ll;
for(int k=0;k<2;k++) if(used[x][k]) dis=min(dis,1ll*(x-ii)*(x-ii)+1ll*(k-jj)*(k-jj));
ans=MAX(ans,make_pair(dis,pii(ii,jj)));
}
if(ans.first==1ll){
int x=*one.begin();
ans.second.first=x;
if(!used[x][0]) ans.second.second=0;
else ans.second.second=1;
}
Insert(ans.second.first,ans.second.second);
}
}else{
int qr,x,y;
qr=readint();
x=ap[qr].first;y=ap[qr].second;
Erase(x,y);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
620 KB |
Output is correct |
| 2 |
Correct |
2 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
620 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
9452 KB |
Output is correct |
| 2 |
Correct |
2 ms |
364 KB |
Output is correct |
| 3 |
Correct |
34 ms |
9196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
9324 KB |
Output is correct |
| 2 |
Correct |
2 ms |
364 KB |
Output is correct |
| 3 |
Correct |
44 ms |
9196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
3052 KB |
Output is correct |
| 2 |
Correct |
33 ms |
844 KB |
Output is correct |
| 3 |
Correct |
37 ms |
2688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
12780 KB |
Output is correct |
| 2 |
Correct |
32 ms |
748 KB |
Output is correct |
| 3 |
Correct |
61 ms |
10496 KB |
Output is correct |
