Submission #1177369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177369		alexdd	Naval battle (CEOI24_battle)	C++20	100 / 100	1562 ms	144480 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n;
int x[200005],y[200005];
char tip[200005];
int scos[200005];
priority_queue<pair<int,pair<int,int>>> pq;///{timp,{id1,id2}}

map<int,set<pair<int,int>>> dE[3],dW[3],dN[3],dS[3];
void calc_vecini(int i)
{
    if(tip[i]=='E')
    {
        auto it = dW[0][y[i]].lower_bound({x[i],0});
        if(it != dW[0][y[i]].end())
            pq.push({-((*it).first - x[i])/2, {i, (*it).second}});

        it = dS[2][x[i]+y[i]].lower_bound({x[i],0});
        if(it != dS[2][x[i]+y[i]].end())
            pq.push({-((*it).first - x[i]), {i, (*it).second}});

        it = dN[1][x[i]-y[i]].lower_bound({x[i],0});
        if(it != dN[1][x[i]-y[i]].end())
            pq.push({-((*it).first - x[i]), {i, (*it).second}});
    }
    else if(tip[i]=='W')
    {
        auto it = dE[0][y[i]].lower_bound({x[i],INF});
        if(it != dE[0][y[i]].begin())
        {
            it--;
            pq.push({-(x[i] - (*it).first)/2, {i, (*it).second}});
        }

        it = dN[2][x[i]+y[i]].lower_bound({x[i],INF});
        if(it != dN[2][x[i]+y[i]].begin())
        {
            it--;
            pq.push({-(x[i] - (*it).first), {i, (*it).second}});
        }

        it = dS[1][x[i]-y[i]].lower_bound({x[i],INF});
        if(it != dS[1][x[i]-y[i]].begin())
        {
            it--;
            pq.push({-(x[i] - (*it).first), {i, (*it).second}});
        }
    }
    else if(tip[i]=='N')
    {
        auto it = dS[0][x[i]].lower_bound({y[i],INF});
        if(it != dS[0][x[i]].begin())
        {
            it--;
            pq.push({-(y[i] - (*it).first)/2, {i, (*it).second}});
        }

        it = dW[2][x[i]+y[i]].lower_bound({x[i],0});
        if(it != dW[2][x[i]+y[i]].end())
            pq.push({-((*it).first - x[i]), {i, (*it).second}});

        it = dE[1][x[i]-y[i]].lower_bound({x[i],INF});
        if(it != dE[1][x[i]-y[i]].begin())
        {
            it--;
            pq.push({-(x[i] - (*it).first), {i, (*it).second}});
        }
    }
    else
    {
        assert(tip[i]=='S');

        auto it = dN[0][x[i]].lower_bound({y[i],0});
        if(it != dN[0][x[i]].end())
            pq.push({-((*it).first - y[i])/2, {i, (*it).second}});

        it = dE[2][x[i]+y[i]].lower_bound({x[i],INF});
        if(it != dE[2][x[i]+y[i]].begin())
        {
            it--;
            pq.push({-(x[i] - (*it).first), {i, (*it).second}});
        }

        it = dW[1][x[i]-y[i]].lower_bound({x[i],0});
        if(it != dW[1][x[i]-y[i]].end())
            pq.push({-((*it).first - x[i]), {i, (*it).second}});
    }
}
void baga(int i)
{
    if(tip[i]=='E')
    {
        dE[0][y[i]].insert({x[i],i});
        dE[1][x[i] - y[i]].insert({x[i],i});
        dE[2][x[i] + y[i]].insert({x[i],i});
    }
    else if(tip[i]=='W')
    {
        dW[0][y[i]].insert({x[i],i});
        dW[1][x[i] - y[i]].insert({x[i],i});
        dW[2][x[i] + y[i]].insert({x[i],i});
    }
    else if(tip[i]=='N')
    {
        dN[0][x[i]].insert({y[i],i});
        dN[1][x[i] - y[i]].insert({x[i],i});
        dN[2][x[i] + y[i]].insert({x[i],i});
    }
    else
    {
        assert(tip[i]=='S');
        dS[0][x[i]].insert({y[i],i});
        dS[1][x[i] - y[i]].insert({x[i],i});
        dS[2][x[i] + y[i]].insert({x[i],i});
    }
}
void scoate(int i)
{
    if(tip[i]=='E')
    {
        dE[0][y[i]].erase({x[i],i});
        dE[1][x[i] - y[i]].erase({x[i],i});
        dE[2][x[i] + y[i]].erase({x[i],i});
    }
    else if(tip[i]=='W')
    {
        dW[0][y[i]].erase({x[i],i});
        dW[1][x[i] - y[i]].erase({x[i],i});
        dW[2][x[i] + y[i]].erase({x[i],i});
    }
    else if(tip[i]=='N')
    {
        dN[0][x[i]].erase({y[i],i});
        dN[1][x[i] - y[i]].erase({x[i],i});
        dN[2][x[i] + y[i]].erase({x[i],i});
    }
    else
    {
        assert(tip[i]=='S');
        dS[0][x[i]].erase({y[i],i});
        dS[1][x[i] - y[i]].erase({x[i],i});
        dS[2][x[i] + y[i]].erase({x[i],i});
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i]>>tip[i];
        baga(i);
    }
    for(int i=1;i<=n;i++)
    {
        calc_vecini(i);
    }
    while(!pq.empty())
    {
        int id1 = pq.top().second.first, id2 = pq.top().second.second;
        pq.pop();
        if(scos[id1] && scos[id2])
        {
            continue;
        }
        else if(!scos[id1] && scos[id2])
        {
            if(scos[id2] == pq.top().first)
            {
                scoate(id1);
                scos[id1] = pq.top().first;
            }
            else
                calc_vecini(id1);
        }
        else if(scos[id1] && !scos[id2])
        {
            if(scos[id1] == pq.top().first)
            {
                scoate(id2);
                scos[id2] = pq.top().first;
            }
            else
                calc_vecini(id2);
        }
        else
        {
            scoate(id1);
            scoate(id2);
            scos[id1] = scos[id2] = pq.top().first;
        }
    }
    for(int i=1;i<=n;i++)
        if(!scos[i])
            cout<<i<<"\n";
    return 0;
}

• 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: 24 / 24