Submission #1231201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231201		PVM_pvm	Naval battle (CEOI24_battle)	C++20	76 / 100	2754 ms	99116 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200'007
struct ship
{
    long long x,y;
    long long tp; ///N 0, E 1, S 2, W 3
    long long ind;
} sh[MAXN];
long long n;
long long kg[MAXN];
struct event
{
    long long vreme;
    long long k1,k2;
};
bool operator<(event a, event b)
{
    return a.vreme>b.vreme;
}
bool operator>(event a, event b)
{
    return a.vreme<b.vreme;
}
struct diagonal
{
    long long vl;
    long long ps;
    long long ind;
};
bool operator<(diagonal a, diagonal b)
{
    if (a.vl==b.vl) return a.ps<b.ps;
    return a.vl<b.vl;
}
set<diagonal> ndp,ndm,edp,edm,sdp,sdm,wdp,wdm;
set<diagonal> nch,nnc,ech,enc,sch,snc,wch,wnc;
set<diagonal>::iterator nxN,nxW,nxS,nxE;
void fillBuff()
{
    nch.insert({INT_MIN,INT_MIN,-1});
    nnc.insert({INT_MIN,INT_MIN,-1});
    ech.insert({INT_MIN,INT_MIN,-1});
    enc.insert({INT_MIN,INT_MIN,-1});
    sch.insert({INT_MIN,INT_MIN,-1});
    snc.insert({INT_MIN,INT_MIN,-1});
    wch.insert({INT_MIN,INT_MIN,-1});
    wnc.insert({INT_MIN,INT_MIN,-1});
    nch.insert({INT_MAX,INT_MAX,-1});
    nnc.insert({INT_MAX,INT_MAX,-1});
    ech.insert({INT_MAX,INT_MAX,-1});
    enc.insert({INT_MAX,INT_MAX,-1});
    sch.insert({INT_MAX,INT_MAX,-1});
    snc.insert({INT_MAX,INT_MAX,-1});
    wch.insert({INT_MAX,INT_MAX,-1});
    wnc.insert({INT_MAX,INT_MAX,-1});
    ndp.insert({INT_MIN,INT_MIN,-1});
    ndm.insert({INT_MIN,INT_MIN,-1});
    edp.insert({INT_MIN,INT_MIN,-1});
    edm.insert({INT_MIN,INT_MIN,-1});
    sdp.insert({INT_MIN,INT_MIN,-1});
    sdm.insert({INT_MIN,INT_MIN,-1});
    wdp.insert({INT_MIN,INT_MIN,-1});
    wdm.insert({INT_MIN,INT_MIN,-1});
    ndp.insert({INT_MAX,INT_MAX,-1});
    ndm.insert({INT_MAX,INT_MAX,-1});
    edp.insert({INT_MAX,INT_MAX,-1});
    edm.insert({INT_MAX,INT_MAX,-1});
    sdp.insert({INT_MAX,INT_MAX,-1});
    sdm.insert({INT_MAX,INT_MAX,-1});
    wdp.insert({INT_MAX,INT_MAX,-1});
    wdm.insert({INT_MAX,INT_MAX,-1});

}
void premahni(long long q)
{
        if (sh[q].tp==0) ///N
        {
            ndp.erase({sh[q].x+sh[q].y,sh[q].x,q});
            ndm.erase({sh[q].x-sh[q].y,sh[q].x,q});
            if (sh[q].y%2==0) nch.erase({sh[q].x,sh[q].y,q});
            else nnc.erase({sh[q].x,sh[q].y,q});
        }
        if (sh[q].tp==1) ///E
        {
            edp.erase({sh[q].x+sh[q].y,sh[q].x,q});
            edm.erase({sh[q].x-sh[q].y,sh[q].x,q});
            if (sh[q].x%2==0) ech.erase({sh[q].y,sh[q].x,q});
            else enc.erase({sh[q].y,sh[q].x,q});
        }
        if (sh[q].tp==2) ///S
        {
            sdp.erase({sh[q].x+sh[q].y,sh[q].x,q});
            sdm.erase({sh[q].x-sh[q].y,sh[q].x,q});
            if (sh[q].y%2==0) sch.erase({sh[q].x,sh[q].y,q});
            else snc.erase({sh[q].x,sh[q].y,q});
        }
        if (sh[q].tp==3) ///W
        {
            wdp.erase({sh[q].x+sh[q].y,sh[q].x,q});
            wdm.erase({sh[q].x-sh[q].y,sh[q].x,q});
            if (sh[q].x%2==0) wch.erase({sh[q].y,sh[q].x,q});
            else wnc.erase({sh[q].y,sh[q].x,q});
        }

}

pair<long long,long long> find_nx(long long q)
{
    //cout<<"probvam "<<" "<<q<<"\n";
    long long dst=-1,koi=-1;
    if (sh[q].tp==0) ///N
    {
        ///da namerim S
        if (sh[q].y%2==0)
        {
            nxS=sch.upper_bound({sh[q].x,sh[q].y,q});
            nxS--;
        }
        else
        {
            nxS=snc.upper_bound({sh[q].x,sh[q].y,q});
            nxS--;
        }
        if ((nxS->vl)==sh[q].x)
        {
            long long cdst=(sh[q].y-nxS->ps)/2;
            if (dst==-1 || cdst<dst)
            {
                dst=cdst;
                koi=nxS->ind;
            }
        }
        ///da namerim E
        nxE=edm.upper_bound({sh[q].x-sh[q].y,sh[q].x,q});
        nxE--;
        if ((nxE->vl)==(sh[q].x-sh[q].y))
        {
            long long cdst=sh[q].x-nxE->ps;
            assert(cdst>0);
            if (dst==-1 || cdst<dst)
            {
                dst=cdst;
                koi=nxE->ind;
            }
        }
        ///da namerim W
        nxW=wdp.upper_bound({sh[q].x+sh[q].y,sh[q].x,q});
        if ((nxW->vl)==(sh[q].x+sh[q].y))
        {
            long long cdst=nxW->ps-sh[q].x;
            if (dst==-1 || cdst<dst)
            {
                dst=cdst;
                koi=nxW->ind;
            }
        }
    }
    if (sh[q].tp==1) ///E
    {
        ///da namerim W
        if (sh[q].x%2==0)
        {
            nxW=wch.upper_bound({sh[q].y,sh[q].x,q});
        }
        else
        {
            nxW=wnc.upper_bound({sh[q].y,sh[q].x,q});
        }
        if ((nxW->vl)==sh[q].y)
        {
            long long cdst=(nxW->ps-sh[q].x)/2;
            if (dst==-1 || cdst<dst)
            {
                dst=cdst;
                koi=nxW->ind;
            }
        }
        ///da namerim N
        nxN=ndm.upper_bound({sh[q].x-sh[q].y,sh[q].x,q});
        if ((nxN->vl)==(sh[q].x-sh[q].y))
        {
            long long cdst=nxN->ps-sh[q].x;
            if (dst==-1 || cdst<dst)
            {
                dst=cdst;
                koi=nxN->ind;
            }
        }
        ///da namerim S
        nxS=sdp.upper_bound({sh[q].x+sh[q].y,sh[q].x,q});
        if ((nxS->vl)==(sh[q].x+sh[q].y))
        {
            long long cdst=nxS->ps-sh[q].x;
            if (dst==-1 || cdst<dst)
            {
                dst=cdst;
                koi=nxS->ind;
            }
        }
    }
    if (sh[q].tp==2) ///S
    {
        ///da namerim N
        if (sh[q].y%2==0)
        {
            nxN=nch.upper_bound({sh[q].x,sh[q].y,q});
        }
        else
        {
            nxN=nnc.upper_bound({sh[q].x,sh[q].y,q});
        }
        if ((nxN->vl)==sh[q].x)
        {
            long long cdst=(nxN->ps-sh[q].y)/2;
            if (dst==-1 || cdst<dst)
            {
                dst=cdst;
                koi=nxN->ind;
            }
        }
        ///da namerim W
        nxW=wdm.upper_bound({sh[q].x-sh[q].y,sh[q].x,q});
        if ((nxW->vl)==(sh[q].x-sh[q].y))
        {
            long long cdst=nxW->ps-sh[q].x;
            if (dst==-1 || cdst<dst)
            {
                dst=cdst;
                koi=nxW->ind;
            }
        }
        ///da namerim E
        nxE=edp.upper_bound({sh[q].x+sh[q].y,sh[q].x,q});
        nxE--;
        if ((nxE->vl)==(sh[q].x+sh[q].y))
        {
            long long cdst=sh[q].x-nxE->ps;
            if (dst==-1 || cdst<dst)
            {
                dst=cdst;
                koi=nxE->ind;
            }
        }
    }
    if (sh[q].tp==3) ///W
    {
        ///da namerim E
        if (sh[q].x%2==0)
        {
            nxE=ech.upper_bound({sh[q].y,sh[q].x,q});
            nxE--;
        }
        else
        {
            nxE=enc.upper_bound({sh[q].y,sh[q].x,q});
            nxE--;
        }
        if ((nxE->vl)==sh[q].y)
        {
            long long cdst=(sh[q].x-nxE->ps)/2;
            if (dst==-1 || cdst<dst)
            {
                dst=cdst;
                koi=nxE->ind;
            }
        }
        ///da namerim S
        nxS=sdm.upper_bound({sh[q].x-sh[q].y,sh[q].x,q});
        nxS--;
        if ((nxS->vl)==(sh[q].x-sh[q].y))
        {
            long long cdst=sh[q].x-nxS->ps;
            if (dst==-1 || cdst<dst)
            {
                dst=cdst;
                koi=nxS->ind;
            }
        }
        ///da namerim N
        nxN=ndp.upper_bound({sh[q].x+sh[q].y,sh[q].x,q});
        nxN--;
        if ((nxN->vl)==(sh[q].x+sh[q].y))
        {
            long long cdst=sh[q].x-nxN->ps;
            if (dst==-1 || cdst<dst)
            {
                dst=cdst;
                koi=nxN->ind;
            }
        }
    }
    return {koi,dst};
}
int main()
{
    cin>>n;
    for (long long q=1;q<=n;q++) kg[q]=0;
    for (long long q=1;q<=n;q++)
    {
        sh[q].ind=q;
        cin>>sh[q].x>>sh[q].y;
        char c;
        cin>>c;
        if (c=='N') sh[q].tp=0;
        else if (c=='E') sh[q].tp=1;
        else if (c=='S') sh[q].tp=2;
        else if (c=='W') sh[q].tp=3;
    }
    if (n>5000)
    {
        fillBuff();
        for (long long q=1;q<=n;q++)
        {
            if (sh[q].tp==0) ///N
            {
                ndp.insert({sh[q].x+sh[q].y,sh[q].x,q});
                ndm.insert({sh[q].x-sh[q].y,sh[q].x,q});
                if (sh[q].y%2==0) nch.insert({sh[q].x,sh[q].y,q});
                else nnc.insert({sh[q].x,sh[q].y,q});
            }
            if (sh[q].tp==1) ///E
            {
                edp.insert({sh[q].x+sh[q].y,sh[q].x,q});
                edm.insert({sh[q].x-sh[q].y,sh[q].x,q});
                if (sh[q].x%2==0) ech.insert({sh[q].y,sh[q].x,q});
                else enc.insert({sh[q].y,sh[q].x,q});
            }
            if (sh[q].tp==2) ///S
            {
                sdp.insert({sh[q].x+sh[q].y,sh[q].x,q});
                sdm.insert({sh[q].x-sh[q].y,sh[q].x,q});
                if (sh[q].y%2==0) sch.insert({sh[q].x,sh[q].y,q});
                else snc.insert({sh[q].x,sh[q].y,q});
            }
            if (sh[q].tp==3) ///W
            {
                wdp.insert({sh[q].x+sh[q].y,sh[q].x,q});
                wdm.insert({sh[q].x-sh[q].y,sh[q].x,q});
                if (sh[q].x%2==0) wch.insert({sh[q].y,sh[q].x,q});
                else wnc.insert({sh[q].y,sh[q].x,q});
            }
        }

        priority_queue<event> qu;
        for (long long q=1;q<=n;q++)
        {
            pair<long long,long long> sl=find_nx(q);
            if (sl.second!=-1) qu.push({sl.second,q,sl.first});
        }
        long long lst=1;
        while (!qu.empty())
        {
            //for (long long q=1;q<=n;q++) cout<<kg[q]<<" ";
            //cout<<"\n";
            event tp=qu.top();
            qu.pop();
            //cout<<tp.k1<<" "<<tp.k2<<" "<<tp.vreme<<"\n";
            assert(tp.vreme>=lst);
            lst=tp.vreme;
            if (kg[ tp.k1 ]!=0 && kg[tp.k2]!=0) continue;
            if (kg[tp.k1]!=0)
            {
                if (tp.vreme==kg[tp.k1])
                {
                    kg[tp.k2]=tp.vreme;
                    premahni(tp.k2);
                }
                else
                {
                    pair<long long,long long> sl=find_nx(tp.k2);
                    if (sl.second!=-1) qu.push({sl.second,tp.k2,sl.first});
                }
                continue;
            }
            if (kg[tp.k2]!=0)
            {
                if (tp.vreme==kg[tp.k2])
                {
                    kg[tp.k1]=tp.vreme;
                    premahni(tp.k1);
                }
                else
                {
                    pair<long long,long long> sl=find_nx(tp.k1);
                    if (sl.second!=-1) qu.push({sl.second,tp.k1,sl.first});
                }
                continue;
            }
            kg[tp.k1]=tp.vreme;
            kg[tp.k2]=tp.vreme;
            premahni(tp.k1);
            premahni(tp.k2);
        }
        for (long long q=1;q<=n;q++)
        {
            if (kg[q]==0) cout<<q<<"\n";
        }
    }
    else
    {
        priority_queue<event> qu;
        for (long long q=1;q<=n;q++)
        {
            for (long long w=1;w<=n;w++)
            {
                if (q==w) continue;
                if (sh[q].tp==sh[w].tp) continue;
                if (sh[q].tp==0)
                {
                    if (sh[w].tp==2)
                    {
                        if (sh[q].x!=sh[w].x) continue;
                        if ((sh[q].y%2)!=(sh[w].y%2)) continue;
                        if (sh[w].y>sh[q].y) continue;
                        long long dff=sh[q].y-sh[w].y;
                        if (dff<0) dff*=-1;
                        dff/=2;
                        qu.push({dff,q,w});
                    }
                    if (sh[w].tp==1)
                    {
                        if ((sh[q].x-sh[q].y)!=(sh[w].x-sh[w].y)) continue;
                        if (sh[w].y>sh[q].y) continue;
                        long long dff=sh[q].y-sh[w].y;
                        if (dff<0) dff*=-1;
                        qu.push({dff,q,w});
                    }
                    if (sh[w].tp==3)
                    {
                        if ((sh[q].x+sh[q].y)!=(sh[w].x+sh[w].y)) continue;
                        if (sh[w].y>sh[q].y) continue;
                        long long dff=sh[q].y-sh[w].y;
                        if (dff<0) dff*=-1;
                        qu.push({dff,q,w});
                    }
                }
                if (sh[q].tp==2)
                {
                    if (sh[w].tp==0)
                    {
                        if (sh[q].x!=sh[w].x) continue;
                        if ((sh[q].y%2)!=(sh[w].y%2)) continue;
                        if (sh[w].y<sh[q].y) continue;
                        long long dff=sh[q].y-sh[w].y;
                        if (dff<0) dff*=-1;
                        dff/=2;
                        qu.push({dff,q,w});
                    }
                    if (sh[w].tp==1)
                    {
                        if ((sh[q].x+sh[q].y)!=(sh[w].x+sh[w].y)) continue;
                        if (sh[w].y<sh[q].y) continue;
                        long long dff=sh[q].y-sh[w].y;
                        if (dff<0) dff*=-1;
                        qu.push({dff,q,w});
                    }
                    if (sh[w].tp==3)
                    {
                        if ((sh[q].x-sh[q].y)!=(sh[w].x-sh[w].y)) continue;
                        if (sh[w].y<sh[q].y) continue;
                        long long dff=sh[q].y-sh[w].y;
                        if (dff<0) dff*=-1;
                        qu.push({dff,q,w});
                    }
                }
                if (sh[q].tp==1)
                {
                    if (sh[w].tp==3)
                    {
                        if (sh[q].y!=sh[w].y) continue;
                        if ((sh[q].x%2)!=(sh[w].x%2)) continue;
                        if (sh[w].x<sh[q].x) continue;
                        long long dff=sh[q].x-sh[w].x;
                        if (dff<0) dff*=-1;
                        dff/=2;
                        qu.push({dff,q,w});
                    }
                    if (sh[w].tp==0)
                    {
                        if ((sh[q].x-sh[q].y)!=(sh[w].x-sh[w].y)) continue;
                        if (sh[w].x<sh[q].x) continue;
                        long long dff=sh[q].y-sh[w].y;
                        if (dff<0) dff*=-1;
                        qu.push({dff,q,w});
                    }
                    if (sh[w].tp==2)
                    {
                        if ((sh[q].x+sh[q].y)!=(sh[w].x+sh[w].y)) continue;
                        if (sh[w].x<sh[q].x) continue;
                        long long dff=sh[q].y-sh[w].y;
                        if (dff<0) dff*=-1;
                        qu.push({dff,q,w});
                    }
                }
                if (sh[q].tp==3)
                {
                    if (sh[w].tp==1)
                    {
                        if (sh[q].y!=sh[w].y) continue;
                        if ((sh[q].x%2)!=(sh[w].x%2)) continue;
                        if (sh[w].x>sh[q].x) continue;
                        long long dff=sh[q].x-sh[w].x;
                        if (dff<0) dff*=-1;
                        dff/=2;
                        qu.push({dff,q,w});
                    }
                    if (sh[w].tp==2)
                    {
                        if ((sh[q].x-sh[q].y)!=(sh[w].x-sh[w].y)) continue;
                        if (sh[w].x>sh[q].x) continue;
                        long long dff=sh[q].y-sh[w].y;
                        if (dff<0) dff*=-1;
                        qu.push({dff,q,w});
                    }
                    if (sh[w].tp==0)
                    {
                        if ((sh[q].x+sh[q].y)!=(sh[w].x+sh[w].y)) continue;
                        if (sh[w].x>sh[q].x) continue;
                        long long dff=sh[q].y-sh[w].y;
                        if (dff<0) dff*=-1;
                        qu.push({dff,q,w});
                    }
                }
            }
        }
        while (!qu.empty())
        {
            //for (long long q=1;q<=n;q++) cout<<kg[q]<<" ";
            //cout<<"\n";
            event tp=qu.top();
            qu.pop();

            //cout<<tp.k1<<" "<<tp.k2<<" "<<tp.vreme<<"\n";
            if (kg[ tp.k1 ]!=0 && kg[tp.k2]!=0) continue;
            if (kg[tp.k1]!=0)
            {
                if (tp.vreme==kg[tp.k1])
                {
                    kg[tp.k2]=tp.vreme;
                }
                continue;
            }
            if (kg[tp.k2]!=0)
            {
                if (tp.vreme==kg[tp.k2])
                {
                    kg[tp.k1]=tp.vreme;
                }
                continue;
            }
            kg[tp.k1]=tp.vreme;
            kg[tp.k2]=tp.vreme;
        }
        for (long long q=1;q<=n;q++)
        {
            if (kg[q]==0) cout<<q<<"\n";
        }
    }
}
/*
6
4 0 W
0 2 E
2 2 S
4 4 N
6 6 W
4 2 W
*/

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 12 / 12
• Subtask 3: 8 / 8
• Subtask 4: 11 / 11
• Subtask 5: 9 / 9
• Subtask 6: 30 / 30
• Subtask 7: 0 / 24