oj.uz

Submission #231187

# Submission time Handle Problem Language Result Execution time Memory
231187 2020-05-13T02:54:33 Z thebes Tram (CEOI13_tram) C++14
100 / 100
 71 ms 6252 KB 
#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);
      |             ~~~~~^~~~~~~~~

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory 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

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory 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