#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) ;
| ~~~~~^~~~~~~~~~~
| # |
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 |
492 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 |
492 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 |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
