oj.uz

답안 #25078

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25078 2017-06-20T06:08:52 Z noobprogrammer 전차 (CEOI13_tram) C++14
100 / 100
 60 ms 18412 KB 
#include<bits/stdc++.h>
using namespace std ;
#define ii pair<int,int> 
#define ll long long
#define fi first 
#define se second 

int n , q , l[2][600010] , r[2][600010] , chk[2][100010] ;
pair<ll ,ii> st[600010] ;
ii pos[100010] ;

ll distcal(ii x , ii y){
	return 1LL * (x.fi - y.fi) * (x.fi - y.fi) + 1LL * (x.se - y.se) * (x.se - y.se) ;
}

void updval(int node , int fs,  int la){
	int le = node<<1 , ri = le+1 ;
	// printf("%d : %d %d\n", node , le ,ri );
	st[node] = ( ( st[le].fi == st[ri].fi ) ? st[le] : max(st[le] , st[ri] ) )  ;
	for(int i=0;i<2;i++){
		r[i][node] = ( (r[i][ri] == 0) ? r[i][le] : r[i][ri] ) ;
		l[i][node] = ( (l[i][le] == 0) ? l[i][ri] : l[i][le] ) ;
		// printf("%d : %d %d\n", node , l[i][node] ,r[i][node] ) ;
	}
	int liml = 0 , limr = 1e9 ;
	for(int i=0;i<2;i++){
		if(r[i][le])liml = max(r[i][le] , liml) ;
		if(l[i][ri])limr = min(l[i][ri] , limr) ;
	}
	if(liml == 0 || limr == 1e9) return  ;
	int mid = (liml + limr)>>1 ;
	ii tmp; 
	ll dist ;
	for(int k = -1 ; k<2;k++){
		if(mid + k < liml) continue ;
		for(int i=0;i<2;i++){
			tmp = {mid+k , i} ;
			dist = 1e18 ;
			for(int j=0;j<2;j++){
				if(r[j][le]) dist = min(dist , distcal(tmp , ii(r[j][le] , j) ) ) ;
				if(l[j][ri]) dist = min(dist , distcal(tmp , ii(l[j][ri] , j) ) ) ;
			}
			if(st[node].fi < dist) st[node] = {dist , tmp} ; 
			else if(st[node].fi <= dist && tmp < st[node].se) st[node] = {dist , tmp} ; 
		}
	}
}

void update(int node , int fs ,int la , int x ,int y , int t){
	if(fs>x || x>la) return ;
	// printf("%d %d\n" , fs ,la) ;
	if(fs == la){
		if(t == 1){
			l[y][node] = r[y][node] = x ;
		}
		else{
			l[y][node] = r[y][node] = 0 ;
		}
		return ;
	}
	update(node<<1 , fs , (fs+la)>>1 , x , y , t ) ;
	update( (node<<1) + 1 , ((fs+la)>>1) + 1 , la , x ,y , t ) ;
	updval(node , fs, la) ;
}

int main(){
	// freopen( "in.txt" , "r" , stdin ) ;
	// freopen( "out.txt", "w" , stdout) ;
	scanf("%d%d",&n,&q) ;
	for(int i=0;i<=4*n;i++) st[i] = {0 ,{0,0}} ;
	char c ;
	int a , x , y , cnt = 0;
	ll dist1  , dist2 , res ;
	for(int i=1;i<=q;i++){
		scanf(" %c",&c) ;
		// printf("\n") ;
		if(c == 'E'){
			res = st[1].fi ; x = st[1].se.fi , y = st[1].se.se ;
			pos[i] = {x,y} ;
			// printf("%d : %lld %d %d\n" , i , res , x ,y) ; 
			if(x == 0 && cnt == 0) pos[i] = {1,0} ;
			else{
				// front
				dist1 = dist2 = 1e18 ;
				for(int j=0;j<2;j++){
					// printf("%d ",l[j][1]) ;
					if(l[j][1]){
						dist1 = min(dist1 , distcal( ii(1,0) , ii(l[j][1] , j) ) ) ;
						dist2 = min(dist2 , distcal( ii(1,1) , ii(l[j][1] , j) ) ) ;
					}
				}
				// cout << endl ;
				if(dist2 >= res){
					res = dist2 ;
					pos[i] = {1,1} ;
				}
				if(dist1 >= res){
					res = dist1 ;
					pos[i] = {1,0} ;
				}
				// printf("front d1 %lld , d2 %lld\n" ,dist1 , dist2) ;
				//back 
				dist1 = dist2 = 1e18 ;
				for(int j=0;j<2;j++){
					// printf("%d ",r[j][1]) ;
					if(r[j][1]){
						dist1 = min(dist1 , distcal(ii(n,0) , ii(r[j][1] , j) ) ) ;
						dist2 = min(dist2 , distcal(ii(n,1) , ii(r[j][1] , j) ) ) ;
					}
				}
				// cout << endl ;
				if(dist1 > res){
					res = dist1 ;
					pos[i] = {n,0} ;
				}
				if(dist2 > res){
					res = dist2 ;
					pos[i] = {n,1} ;
				}
				// printf("back d1 %lld , d2 %lld\n" ,dist1 , dist2) ;
			}
			cnt++ ;
			printf("%d %d\n" , pos[i].fi , pos[i].se + 1 ) ;
			update(1 , 1 , n , pos[i].fi , pos[i].se , 1 ) ;
		} 
		else{
			scanf("%d" , &a) ;
			x = pos[a].fi , y = pos[a].se ;
			update(1 , 1 , n , x , y , 0) ;
 			cnt-- ;
 		}
	}
}

Compilation message

tram.cpp: In function 'int main()':
tram.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |  scanf("%d%d",&n,&q) ;
      |  ~~~~~^~~~~~~~~~~~~~
tram.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |   scanf(" %c",&c) ;
      |   ~~~~~^~~~~~~~~~
tram.cpp:127:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  127 |    scanf("%d" , &a) ;
      |    ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 492 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 492 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

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 13932 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 11 ms 13804 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 13932 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 13 ms 13804 KB Output is correct

Subtask #7
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 2244 KB Output is correct
2 Correct 38 ms 896 KB Output is correct
3 Correct 33 ms 2156 KB Output is correct

Subtask #8
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 18412 KB Output is correct
2 Correct 26 ms 748 KB Output is correct
3 Correct 52 ms 18284 KB Output is correct