Submission #624424

#	Time	Username	Problem	Language	Result	Execution time	Memory
624424		andrei_boaca	Tram (CEOI13_tram)	C++14	100 / 100	236 ms	24528 KiB

tram

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
ll n,m;
bool have[150005][3];
auto comp=[](pair<ll,pii> a, pair<ll, pii> b)
{
    if(a.first!=b.first)
        return a.first>b.first;
    int linA=a.second.first,linB=b.second.first;
    if(linA!=linB)
        return linA<linB;
    int colA=a.second.second,colB=b.second.second;
    return colA<colB;
};
multiset<pair<ll,pii>,decltype(comp)> s(comp);
set<int> poz;
pii where[30005],best[55];
ll dist(ll a, ll b, ll c, ll d)
{
    return (a-c)*(a-c)+(b-d)*(b-d);
}
int rgt[150005],lft[150005];
vector<int> v;
void putseg(int st,int dr)
{
    int mij=(st+dr)/2;
    for(int a=st;a<=st+1;a++)
        if(a>=st&&a<=dr&&a>=1&&a<=n)
            for(int j=1;j<=2;j++)
                if(!have[a][j])
                {
                    ll minim=1e18;
                    for(int k=1;k<=2;k++)
                    {
                        if(have[st][k]&&st>0)
                            minim=min(minim,dist(st,k,a,j));
                        if(have[dr][k]&&dr<=n)
                            minim=min(minim,dist(dr,k,a,j));
                    }
                    s.insert({minim,{a,j}});
                }
    for(int a=mij-1;a<=mij+1;a++)
        if(a>=st&&a<=dr&&a>=1&&a<=n)
            for(int j=1;j<=2;j++)
                if(!have[a][j])
                {
                    ll minim=1e18;
                    for(int k=1;k<=2;k++)
                    {
                        if(have[st][k]&&st>0)
                            minim=min(minim,dist(st,k,a,j));
                        if(have[dr][k]&&dr<=n)
                            minim=min(minim,dist(dr,k,a,j));
                    }
                    s.insert({minim,{a,j}});
                }
    for(int a=dr-1;a<=dr;a++)
        if(a>=st&&a<=dr&&a>=1&&a<=n)
            for(int j=1;j<=2;j++)
                if(!have[a][j])
                {
                    ll minim=1e18;
                    for(int k=1;k<=2;k++)
                    {
                        if(have[st][k]&&st>0)
                            minim=min(minim,dist(st,k,a,j));
                        if(have[dr][k]&&dr<=n)
                            minim=min(minim,dist(dr,k,a,j));
                    }
                    s.insert({minim,{a,j}});
                }
}
void eraseseg(int st,int dr)
{
    int mij=(st+dr)/2;
    for(int a=st;a<=st+1;a++)
        if(a>=st&&a<=dr&&a>=1&&a<=n)
            for(int j=1;j<=2;j++)
                if(!have[a][j])
                {
                    ll minim=1e18;
                    for(int k=1;k<=2;k++)
                    {
                        if(have[st][k]&&st>0)
                            minim=min(minim,dist(st,k,a,j));
                        if(have[dr][k]&&dr<=n)
                            minim=min(minim,dist(dr,k,a,j));
                    }
                    s.erase(s.find({minim,{a,j}}));
                }
    for(int a=mij-1;a<=mij+1;a++)
        if(a>=st&&a<=dr&&a>=1&&a<=n)
            for(int j=1;j<=2;j++)
                if(!have[a][j])
                {
                    ll minim=1e18;
                    for(int k=1;k<=2;k++)
                    {
                        if(have[st][k]&&st>0)
                            minim=min(minim,dist(st,k,a,j));
                        if(have[dr][k]&&dr<=n)
                            minim=min(minim,dist(dr,k,a,j));
                    }
                    s.erase(s.find({minim,{a,j}}));
                }
    for(int a=dr-1;a<=dr;a++)
        if(a>=st&&a<=dr&&a>=1&&a<=n)
            for(int j=1;j<=2;j++)
                if(!have[a][j])
                {
                    ll minim=1e18;
                    for(int k=1;k<=2;k++)
                    {
                        if(have[st][k]&&st>0)
                            minim=min(minim,dist(st,k,a,j));
                        if(have[dr][k]&&dr<=n)
                            minim=min(minim,dist(dr,k,a,j));
                    }
                    s.erase(s.find({minim,{a,j}}));
                }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    int cur=0;
    have[0][1]=have[0][2]=1;
    have[n+1][1]=have[n+1][2]=1;
    rgt[0]=n+1;
    putseg(0,n+1);
    poz.insert(0);
    poz.insert(n+1);
    while(m--)
    {
        cur++;
        char c;
        cin>>c;
        if(c=='E')
        {
            /*if(s.empty())
            {
                cout<<1<<' '<<1<<'\n';
                s.insert(1);
                have[1][1]=1;
                where[cur]={1,1};
                continue;
            }*/
            auto it=s.begin();
            int lin=(*it).second.first;
            int col=(*it).second.second;
            where[cur]={lin,col};
            cout<<lin<<' '<<col<<'\n';
            if(have[lin][1]+have[lin][2]==0)
            {
                int st=*prev(poz.lower_bound(lin));
                int dr=*poz.upper_bound(lin);
                eraseseg(st,dr);
                have[lin][col]=1;
                putseg(st,lin);
                putseg(lin,dr);
                poz.insert(lin);
            }
            else
            {
                int st=*prev(poz.lower_bound(lin));
                int dr=*poz.upper_bound(lin);
                eraseseg(st,lin);
                eraseseg(lin,dr);
                have[lin][col]=1;
                putseg(st,lin);
                putseg(lin,dr);
            }
        }
        else
        {
            int p;
            cin>>p;
            int lin=where[p].first,col=where[p].second;
            if(have[lin][1]+have[lin][2]==1)
            {
                poz.erase(lin);
                int st=*prev(poz.lower_bound(lin));
                int dr=*poz.upper_bound(lin);
                eraseseg(st,lin);
                eraseseg(lin,dr);
                have[lin][col]=0;
                putseg(st,dr);
            }
            else
            {
                int st=*prev(poz.lower_bound(lin));
                int dr=*poz.upper_bound(lin);
                eraseseg(st,lin);
                eraseseg(lin,dr);
                have[lin][col]=0;
                putseg(st,lin);
                putseg(lin,dr);
            }
        }
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 15 / 15
• Subtask 8: 20 / 20