Submission #25078

#TimeUsernameProblemLanguageResultExecution timeMemory
25078noobprogrammerTram (CEOI13_tram)C++14
100 / 100
60 ms18412 KiB
#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 (stderr)

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 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...