#include <bits/stdc++.h>
#define DEBUG 1
using namespace std;
namespace output{
void __(short x){cout<<x;}
void __(unsigned x){cout<<x;}
void __(int x){cout<<x;}
void __(long long x){cout<<x;}
void __(unsigned long long x){cout<<x;}
void __(double x){cout<<x;}
void __(long double x){cout<<x;}
void __(char x){cout<<x;}
void __(const char*x){cout<<x;}
void __(const string&x){cout<<x;}
void __(bool x){cout<<(x?"true":"false");}
template<class S,class T>
void __(const pair<S,T>&x){__(DEBUG?"(":""),__(x.first),__(DEBUG?", ":" "),__(x.second),__(DEBUG?")":"");}
template<class T>
void __(const vector<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
template<class T>
void __(const set<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
template<class T>
void __(const multiset<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
template<class S,class T>
void __(const map<S,T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
void pr(){cout<<"\n";}
template<class S,class... T>
void pr(const S&a,const T&...b){__(a);if(sizeof...(b))__(' ');pr(b...);}
}
using namespace output;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,char> pic;
typedef pair<double,double> pdd;
typedef pair<ld,ld> pld;
typedef vector<int> vi;
typedef vector<ll> vl;
#define pb push_back
#define fox(i,x,y) for(int i=(x);i<=(y);i++)
#define foxr(i,x,y) for(int i=(y);i>=(x);i--)
#define F first
#define S second
const int MN = 2e5+5;
int N, M, i, x, y; char ch; pii pos[MN]; double _;
struct cmp{bool operator()(const pair<double,ll>&i,const pair<double,ll>&j){return i.F==j.F?i.S<j.S:i.F>j.F;}};
set<pair<double,ll>,cmp> seg; map<ll,ll> st; map<ll,double> dist;
inline double dis(pll i,pll j){return sqrt((i.F-j.F)*(i.F-j.F)+(i.S-j.S)*(i.S-j.S));}
inline void go(pll &old,double &cur,pll nw,ll x,ll y,ll m1,ll m2){
double mindist=1e9;
for(int i=0;i<2;i++){
if((1<<i)&m1)
mindist=min(mindist,dis(nw,make_pair(x,i+1)));
if((1<<i)&m2)
mindist=min(mindist,dis(nw,make_pair(y,i+1)));
}
if(mindist>cur){
cur=mindist;
old=nw;
}
}
inline pll opt(ll x,ll y,ll m1,ll m2){
assert(y>=1);
ll mid=(x+y)>>1; double d=0;
mid=max(mid,1LL);
mid=min(mid,(ll)N);
pll ret(mid,1);
go(ret,d,make_pair(mid,1),x,y,m1,m2);
go(ret,d,make_pair(mid,2),x,y,m1,m2);
if(mid+1<=min(y,(ll)N)){
go(ret,d,make_pair(mid+1,1),x,y,m1,m2);
go(ret,d,make_pair(mid+1,2),x,y,m1,m2);
}
_ = d;
return ret;
}
int main(){
scanf("%d%d",&N,&M);
st[1-3*N]=st[1+3*N]=3;
pll tmp=opt(1-3*N,1+3*N,3,3);
dist[1-3*N]=_;
seg.insert({_,1-3*N});
for(i=1;i<=M;i++){
/*for(auto v : seg)
printf("(%lf, %lld) ",v.F,v.S);
pr();*/
scanf(" %c",&ch);
if(ch=='E'){
ll lef=seg.begin()->S;
auto rit = st.upper_bound(lef);
pos[i]=opt(lef,rit->F,st[lef],rit->S);
seg.erase(seg.begin());
int flag=0;
if(st[pos[i].F]) flag=1;
st[pos[i].F]|=(1<<(pos[i].S-1));
auto it = st.lower_bound(pos[i].F); it--;
rit = st.upper_bound(pos[i].F);
if(flag){
seg.erase({dist[it->F],it->F});
seg.erase({dist[pos[i].F],pos[i].F});
}
opt(it->F,pos[i].F,it->S,st[pos[i].F]);
dist[it->F]=_;
seg.insert({_,it->F});
opt(pos[i].F,rit->F,st[pos[i].F],rit->S);
dist[pos[i].F]=_;
seg.insert({_,pos[i].F});
printf("%d %d\n",pos[i].F,pos[i].S);
}
else{
scanf("%d",&x);
pll cur=pos[x];
auto lef=st.lower_bound(cur.F); lef--;
auto rit=st.upper_bound(cur.F);
seg.erase({dist[lef->F],lef->F});
seg.erase({dist[cur.F],cur.F});
st[cur.F]^=(1<<(cur.S-1));
if(!st[cur.F]){
st.erase(cur.F);
opt(lef->F,rit->F,lef->S,rit->S);
dist[lef->F]=_;
seg.insert({_,lef->F});
}
else{
opt(lef->F,cur.F,lef->S,st[cur.F]);
dist[lef->F]=_;
seg.insert({_,lef->F});
opt(cur.F,rit->F,st[cur.F],rit->S);
dist[cur.F]=_;
seg.insert({_,cur.F});
}
}
}
return 0;
}
Compilation message
tram.cpp: In function 'int main()':
tram.cpp:88:9: warning: variable 'tmp' set but not used [-Wunused-but-set-variable]
88 | pll tmp=opt(1-3*N,1+3*N,3,3);
| ^~~
tram.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
86 | scanf("%d%d",&N,&M);
| ~~~~~^~~~~~~~~~~~~~
tram.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
95 | scanf(" %c",&ch);
| ~~~~~^~~~~~~~~~~
tram.cpp:119:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
119 | scanf("%d",&x);
| ~~~~~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
620 KB |
Output is correct |
| 2 |
Correct |
3 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
620 KB |
Output is correct |
| 2 |
Correct |
3 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
620 KB |
Output is correct |
| 2 |
Correct |
3 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
644 KB |
Output is correct |
| 2 |
Correct |
3 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
71 ms |
3528 KB |
Output is correct |
| 2 |
Correct |
58 ms |
880 KB |
Output is correct |
| 3 |
Correct |
48 ms |
2284 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
59 ms |
6252 KB |
Output is correct |
| 2 |
Correct |
47 ms |
876 KB |
Output is correct |
| 3 |
Correct |
51 ms |
2484 KB |
Output is correct |
