oj.uz

Submission #328888

# Submission time Handle Problem Language Result Execution time Memory
328888 2020-11-18T11:32:41 Z htc001 Tram (CEOI13_tram) C++14
100 / 100
 99 ms 12780 KB 
#include<bits/stdc++.h>
using namespace std;

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];
char ope[10];
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);
	printf("%d %d\n",x,y+1);
	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(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		lft[i]=2;
		one.insert(i);
	}
	while(++cs<=q){
		scanf("%s",ope);
		if(ope[0]=='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;
			scanf("%d",&qr);
			x=ap[qr].first;y=ap[qr].second;
			Erase(x,y);
		}
	}
	return 0;
}

Compilation message

tram.cpp: In function 'int main()':
tram.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   94 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
tram.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |   scanf("%s",ope);
      |   ~~~~~^~~~~~~~~~
tram.cpp:142:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  142 |    scanf("%d",&qr);
      |    ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.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

Subtask #2
15.0 / 15.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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 492 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 492 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9324 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 36 ms 9196 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9392 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 39 ms 9196 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3056 KB Output is correct
2 Correct 41 ms 748 KB Output is correct
3 Correct 36 ms 2540 KB Output is correct

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 12780 KB Output is correct
2 Correct 53 ms 876 KB Output is correct
3 Correct 69 ms 10476 KB Output is correct