Submission #1044373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044373		SamAnd	Naval battle (CEOI24_battle)	C++17	100 / 100	1559 ms	124068 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 200005;

int n;
int x[N], y[N];
char ty[N];

int f(const pair<int, int>& t1, const pair<int, int>& t2)
{
    return (abs(t1.fi - t2.fi) + abs(t1.se - t2.se)) / 2;
}

set<pair<int, pair<pair<int, int>, pair<int, int> > > > orz;

void ave(set<pair<pair<int, int>, bool> >& s, int x, int y, bool z, int ttt)
{
    if (ttt == +1)
    {
        if (!s.empty())
        {
            auto it = s.lower_bound(m_p(m_p(x, y), z));
            if (it != s.end() && it != s.begin())
            {
                if (it->se == true)
                {
                    pair<int, int> r = it->fi;
                    --it;
                    if (it->se == false)
                    {
                        pair<int, int> l = it->fi;
                        orz.erase(m_p(f(l, r), m_p(l, r)));
                    }
                }
            }
        }
        s.insert(m_p(m_p(x, y), z));
        auto it = s.find(m_p(m_p(x, y), z));
        if (z == false)
        {
            pair<int, int> l = m_p(x, y);
            ++it;
            if (it != s.end())
            {
                if (it->se == true)
                {
                    pair<int, int> r = it->fi;
                    orz.insert(m_p(f(l, r), m_p(l, r)));
                }
            }
        }
        else
        {
            pair<int, int> r = m_p(x, y);
            if (it != s.begin())
            {
                --it;
                if (it->se == false)
                {
                    pair<int, int> l = it->fi;
                    orz.insert(m_p(f(l, r), m_p(l, r)));
                }
            }
        }
    }
    else if (ttt == -1)
    {
        auto it = s.find(m_p(m_p(x, y), z));
        if (z == false)
        {
            pair<int, int> l = m_p(x, y);
            ++it;
            if (it != s.end())
            {
                if (it->se == true)
                {
                    pair<int, int> r = it->fi;
                    orz.erase(m_p(f(l, r), m_p(l, r)));
                }
            }
        }
        else
        {
            pair<int, int> r = m_p(x, y);
            if (it != s.begin())
            {
                --it;
                if (it->se == false)
                {
                    pair<int, int> l = it->fi;
                    orz.erase(m_p(f(l, r), m_p(l, r)));
                }
            }
        }
        s.erase(m_p(m_p(x, y), z));
        if (!s.empty())
        {
            auto it = s.lower_bound(m_p(m_p(x, y), z));
            if (it != s.end() && it != s.begin())
            {
                if (it->se == true)
                {
                    pair<int, int> r = it->fi;
                    --it;
                    if (it->se == false)
                    {
                        pair<int, int> l = it->fi;
                        orz.insert(m_p(f(l, r), m_p(l, r)));
                    }
                }
            }
        }
    }
    else
        assert(false);
}

vector<int> s, d, xx, yy;
set<pair<pair<int, int>, bool> > ew[N], sn[N], es[N], nw[N], en[N], sw[N];
void ave(int x, int y, char ty, int ttt)
{
    // EW
    if (ty == 'E')
    {
        int i = lower_bound(all(yy), y) - yy.begin();
        ave(ew[i], x, y, false, ttt);
    }
    if (ty == 'W')
    {
        int i = lower_bound(all(yy), y) - yy.begin();
        ave(ew[i], x, y, true, ttt);
    }
    // SN
    if (ty == 'S')
    {
        int i = lower_bound(all(xx), x) - xx.begin();
        ave(sn[i], x, y, false, ttt);
    }
    if (ty == 'N')
    {
        int i = lower_bound(all(xx), x) - xx.begin();
        ave(sn[i], x, y, true, ttt);
    }
    // ES
    if (ty == 'E')
    {
        int i = lower_bound(all(s), x + y) - s.begin();
        ave(es[i], x, y, false, ttt);
    }
    if (ty == 'S')
    {
        int i = lower_bound(all(s), x + y) - s.begin();
        ave(es[i], x, y, true, ttt);
    }
    // NW
    if (ty == 'N')
    {
        int i = lower_bound(all(s), x + y) - s.begin();
        ave(nw[i], x, y, false, ttt);
    }
    if (ty == 'W')
    {
        int i = lower_bound(all(s), x + y) - s.begin();
        ave(nw[i], x, y, true, ttt);
    }
    // EN
    if (ty == 'E')
    {
        int i = lower_bound(all(d), x - y) - d.begin();
        ave(en[i], x, y, false, ttt);
    }
    if (ty == 'N')
    {
        int i = lower_bound(all(d), x - y) - d.begin();
        ave(en[i], x, y, true, ttt);
    }
    // SW
    if (ty == 'S')
    {
        int i = lower_bound(all(d), x - y) - d.begin();
        ave(sw[i], x, y, false, ttt);
    }
    if (ty == 'W')
    {
        int i = lower_bound(all(d), x - y) - d.begin();
        ave(sw[i], x, y, true, ttt);
    }
}

bool c[N];

void solv()
{
    cin >> n;
    map<pair<int, int>, int> mp;
    for (int i = 1; i <= n; ++i)
    {
        cin >> x[i] >> y[i] >> ty[i];
        mp[m_p(x[i], y[i])] = i;
    }

    for (int i = 1; i <= n; ++i)
    {
        s.push_back(x[i] + y[i]);
        d.push_back(x[i] - y[i]);
        xx.push_back(x[i]);
        yy.push_back(y[i]);
    }

    sort(all(s));
    sort(all(d));
    sort(all(xx));
    sort(all(yy));

    for (int i = 1; i <= n; ++i)
    {
        ave(x[i], y[i], ty[i], 1);
    }

    while (!orz.empty())
    {
        int d = orz.begin()->fi;
        vector<int> t;
        while (!orz.empty())
        {
            auto it = orz.begin();
            if (it->fi != d)
                break;
            int i = mp[it->se.fi];
            int j = mp[it->se.se];
            if (c[i] || c[j])
            {
                orz.erase(it);
                continue;
            }
            t.push_back(i);
            t.push_back(j);
            orz.erase(it);
        }
        for (int i = 0; i < sz(t); ++i)
        {
            if (c[t[i]])
                continue;
            c[t[i]] = true;
            ave(x[t[i]], y[t[i]], ty[t[i]], -1);
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        if (!c[i])
            cout << i << "\n";
    }
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    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