Submission #1119863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119863		Tenis0206	Naval battle (CEOI24_battle)	C++11	100 / 100	1495 ms	116204 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];

int sel[nmax + 5];

int cnt;

priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> h;

struct diag
{
    bool is_built;
    multiset<pair<int,pair<int,int>>> s;

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

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

        int last = 0;
        int last_x = 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 - last_x, {last, it->second.second}});
            }
            last = it->second.second;
            last_x = it->first;
            last_tip = it->second.first;
        }
    }

    void rem(int i, int x, int tip)
    {
        auto er = s.lower_bound({x, {tip, i}});
        auto u = s.upper_bound({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);
    }
};

diag dne[nmax + 5], dnv[nmax + 5], dse[nmax + 5], dsv[nmax + 5], dns[nmax + 5], dve[nmax + 5];

vector<int> d0, d1;
vector<int> dx, dy;

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, v[i].x, 1);
        dnv[diag1].add(i, v[i].x, 0);
    }
    else if(v[i].dir == 'S')
    {
        dsv[diag0].add(i, v[i].x, 0);
        dse[diag1].add(i, v[i].x, 1);
    }
    else if(v[i].dir == 'E')
    {
        dne[diag0].add(i, v[i].x, 0);
        dse[diag1].add(i, v[i].x, 0);
    }
    else if(v[i].dir == 'W')
    {
        dsv[diag0].add(i, v[i].x, 1);
        dnv[diag1].add(i, v[i].x, 1);
    }

    int px = get_val(dx, v[i].x);
    int py = get_val(dy, v[i].y);
    if(v[i].dir == 'N')
    {
        dns[px].add(i, v[i].y / 2, 1);
    }
    else if(v[i].dir == 'S')
    {
        dns[px].add(i, v[i].y / 2, 0);
    }
    else if(v[i].dir == 'E')
    {
        dve[py].add(i, v[i].x / 2, 0);
    }
    else if(v[i].dir == 'W')
    {
        dve[py].add(i, v[i].x / 2, 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();
    }
    else if(v[i].dir == 'S')
    {
        dsv[diag0].build();
        dse[diag1].build();
    }
    else if(v[i].dir == 'E')
    {
        dne[diag0].build();
        dse[diag1].build();
    }
    else if(v[i].dir == 'W')
    {
        dsv[diag0].build();
        dnv[diag1].build();
    }

    int px = get_val(dx, v[i].x);
    int py = get_val(dy, v[i].y);
    if(v[i].dir == 'N')
    {
        dns[px].build();
    }
    else if(v[i].dir == 'S')
    {
        dns[px].build();
    }
    else if(v[i].dir == 'E')
    {
        dve[py].build();
    }
    else if(v[i].dir == 'W')
    {
        dve[py].build();
    }
}

void Remove(int i)
{
    if(sel[i])
    {
        return;
    }
    sel[i] = cnt;
    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, v[i].x, 1);
        dnv[diag1].rem(i, v[i].x, 0);
    }
    else if(v[i].dir == 'S')
    {
        dsv[diag0].rem(i, v[i].x, 0);
        dse[diag1].rem(i, v[i].x, 1);
    }
    else if(v[i].dir == 'E')
    {
        dne[diag0].rem(i, v[i].x, 0);
        dse[diag1].rem(i, v[i].x, 0);
    }
    else if(v[i].dir == 'W')
    {
        dsv[diag0].rem(i, v[i].x, 1);
        dnv[diag1].rem(i, v[i].x, 1);
    }

    int px = get_val(dx, v[i].x);
    int py = get_val(dy, v[i].y);
    if(v[i].dir == 'N')
    {
        dns[px].rem(i, v[i].y / 2, 1);
    }
    else if(v[i].dir == 'S')
    {
        dns[px].rem(i, v[i].y / 2, 0);
    }
    else if(v[i].dir == 'E')
    {
        dve[py].rem(i, v[i].x / 2, 0);
    }
    else if(v[i].dir == 'W')
    {
        dve[py].rem(i, v[i].x / 2, 1);
    }
}

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

        dx.push_back(v[i].x);
        dy.push_back(v[i].y);
    }
    sort(d0.begin(),d0.end());
    sort(d1.begin(),d1.end());
    sort(dx.begin(),dx.end());
    sort(dy.begin(),dy.end());
    for(int i=1; i<=n; i++)
    {
        Add(i);
    }
    for(int i=1;i<=n;i++)
    {
        Build(i);
    }
    while(!h.empty())
    {
        ++cnt;
        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)
        {
            if(!sel[h.top().second.first] && !sel[h.top().second.second])
            {
                Remove(h.top().second.first);
                Remove(h.top().second.second);
            }
            else if(!sel[h.top().second.first] && sel[h.top().second.second] == cnt)
            {
                Remove(h.top().second.first);
            }
            else if(sel[h.top().second.first] == cnt && !sel[h.top().second.second])
            {
                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: 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