Submission #1119793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119793		Tenis0206	Naval battle (CEOI24_battle)	C++11	0 / 100	654 ms	106904 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int nmax = 2e5;

struct punct
{
    int x, y;
    char dir;
};

int n;
punct v[nmax + 5];

bool sel[nmax + 5];

struct diag
{
    bool is_built;
    priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> H;
    multiset<pair<int,pair<int,int>>> s;

    bool Empty()
    {
        return H.empty();
    }

    pair<int,pair<int,int>> Top()
    {
        return H.top();
    }

    void add(int i, int tip)
    {
        s.insert({v[i].x, {tip, i}});
    }

    void build()
    {
        if(is_built)
        {
            return;
        }
        is_built = true;

        int last = 0;
        int last_tip = -1;
        for(auto it=s.begin();it!=s.end();it++)
        {
            if(last_tip == 0 && it -> second.first == 1)
            {
                H.push({it->first - v[last].x, {last, it->second.second}});
            }
            last = it->second.second;
            last_tip = it->second.first;
        }
    }

    void rem(int i, int tip)
    {
        auto er = s.lower_bound({v[i].x, {tip, i}});
        auto u = s.upper_bound({v[i].x, {tip, i}});
        if(er != s.begin() && u != s.end())
        {
            auto p = er;
            p--;
            if(p -> second.first == 0 && u -> second.first == 1)
            {
                H.push({u->first - p->first, {p->second.second, u->second.second}});
            }
        }
        s.erase(er);
        while(!H.empty() && (sel[H.top().second.first] || sel[H.top().second.second]))
        {
            H.pop();
        }
    }
};

diag dne[nmax + 5], dnv[nmax + 5], dse[nmax + 5], dsv[nmax + 5];
priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> h;

vector<int> d0, d1;

int get_val(vector<int> &a, int val)
{
    int st = 1;
    int dr = a.size();
    int poz = 0;
    while(st <= dr)
    {
        int mij = (st + dr) >> 1;
        if(a[mij - 1] <= val)
        {
            poz = mij;
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }
    return poz;
}

void Add(int i)
{
    int diag0 = get_val(d0, v[i].x - v[i].y);
    int diag1 = get_val(d1, v[i].x + v[i].y);
    if(v[i].dir == 'N')
    {
        dne[diag0].add(i, 1);
        dnv[diag1].add(i, 0);
    }
    else if(v[i].dir == 'S')
    {
        dsv[diag0].add(i, 0);
        dse[diag1].add(i, 1);
    }
    else if(v[i].dir == 'E')
    {
        dne[diag0].add(i, 0);
        dse[diag1].add(i, 0);
    }
    else if(v[i].dir == 'V')
    {
        dsv[diag0].add(i, 1);
        dnv[diag1].add(i, 1);
    }
}

void Build(int i)
{
    int diag0 = get_val(d0, v[i].x - v[i].y);
    int diag1 = get_val(d1, v[i].x + v[i].y);
    if(v[i].dir == 'N')
    {
        dne[diag0].build();
        dnv[diag1].build();
        if(!dne[diag0].Empty())
        {
            h.push(dne[diag0].Top());
        }
        if(!dnv[diag1].Empty())
        {
            h.push(dnv[diag1].Top());
        }
    }
    else if(v[i].dir == 'S')
    {
        dsv[diag0].build();
        dse[diag1].build();
        if(!dsv[diag0].Empty())
        {
            h.push(dsv[diag0].Top());
        }
        if(!dse[diag1].Empty())
        {
            h.push(dse[diag1].Top());
        }
    }
    else if(v[i].dir == 'E')
    {
        dne[diag0].build();
        dse[diag1].build();
        if(!dne[diag0].Empty())
        {
            h.push(dne[diag0].Top());
        }
        if(!dse[diag1].Empty())
        {
            h.push(dse[diag1].Top());
        }
    }
    else if(v[i].dir == 'V')
    {
        dsv[diag0].build();
        dnv[diag1].build();
        if(!dsv[diag0].Empty())
        {
            h.push(dsv[diag0].Top());
        }
        if(!dnv[diag1].Empty())
        {
            h.push(dnv[diag1].Top());
        }
    }
}

void Remove(int i)
{
    if(sel[i])
    {
        return;
    }
    sel[i] = true;
    int diag0 = get_val(d0, v[i].x - v[i].y);
    int diag1 = get_val(d1, v[i].x + v[i].y);
    if(v[i].dir == 'N')
    {
        dne[diag0].rem(i, 1);
        dnv[diag1].rem(i, 0);
        if(!dne[diag0].Empty())
        {
            h.push(dne[diag0].Top());
        }
        if(!dnv[diag1].Empty())
        {
            h.push(dnv[diag1].Top());
        }
    }
    else if(v[i].dir == 'S')
    {
        dsv[diag0].rem(i, 0);
        dse[diag1].rem(i, 1);
        if(!dsv[diag0].Empty())
        {
            h.push(dsv[diag0].Top());
        }
        if(!dse[diag1].Empty())
        {
            h.push(dse[diag1].Top());
        }
    }
    else if(v[i].dir == 'E')
    {
        dne[diag0].rem(i, 0);
        dse[diag1].rem(i, 0);
        if(!dne[diag0].Empty())
        {
            h.push(dne[diag0].Top());
        }
        if(!dse[diag1].Empty())
        {
            h.push(dse[diag1].Top());
        }
    }
    else if(v[i].dir == 'V')
    {
        dsv[diag0].rem(i, 1);
        dnv[diag1].rem(i, 1);
        if(!dsv[diag0].Empty())
        {
            h.push(dsv[diag0].Top());
        }
        if(!dnv[diag1].Empty())
        {
            h.push(dnv[diag1].Top());
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
#endif // home
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i].x>>v[i].y>>v[i].dir;
        d0.push_back(v[i].x - v[i].y);
        d1.push_back(v[i].x + v[i].y);
    }
    sort(d0.begin(),d0.end());
    sort(d1.begin(),d1.end());
    for(int i=1; i<=n; i++)
    {
        Add(i);
    }
    for(int i=1;i<=n;i++)
    {
        Build(i);
    }
    while(!h.empty())
    {
        while(!h.empty() && (sel[h.top().second.first] || sel[h.top().second.second]))
        {
            h.pop();
        }
        if(h.empty())
        {
            break;
        }
        int val = h.top().first;
        while(!h.empty() && h.top().first == val)
        {
            Remove(h.top().second.first);
            Remove(h.top().second.second);
            h.pop();
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(!sel[i])
        {
            cout<<i<<'\n';
        }
    }
    return 0;
}

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