Submission #1197217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197217		Zbyszek99	Naval battle (CEOI24_battle)	C++20	36 / 100	3095 ms	321348 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 2e9+1;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

set<pii> total_gaps;

struct dim
{
    multiset<pair<int,pii>> gaps;
    set<int> T[2];
    int ind;
    unordered_map<int,int> real_map;
    pair<int,pii> best = {INF,{-1,-1}};
    void add(int v, int real_ind, int t)
    {
        real_map[v] = real_ind;
        total_gaps.erase(total_gaps.find({best.ff,ind}));
        int nxt0 = INF;
        auto it = T[0].lower_bound(v);
        if(it != T[0].end())
        {
            nxt0 = *it;
        }
        int prev0 = -INF;
        if(it != T[0].begin())
        {
            it--;
            prev0 = *it;
        }
        it = T[1].lower_bound(v);
        int nxt1 = INF;
        if(it != T[1].end())
        {
            nxt1 = *it;
        }
        int prev1 = -INF;
        if(it != T[1].begin())
        {
            it--;
            prev1 = *it;
        }
        if(t == 0)
        {
            if(nxt0 > nxt1)
            {
                gaps.insert({nxt1-v,{nxt1,v}});
                if(prev0 > prev1)
                {
                    gaps.erase(gaps.find({nxt1-prev0,{nxt1,prev0}}));
                }
            }
        }
        else
        {
            if(prev0 > prev1)
            {
                gaps.insert({v-prev0,{v,prev0}});
                if(nxt1 < nxt0)
                {
                    gaps.erase(gaps.find({nxt1-prev0,{nxt1,prev0}}));
                }
            }
        }
        T[t].insert(v);
        if(siz(gaps) > 0) best = *gaps.begin();
        else best = {INF,{-1,-1}};
        total_gaps.insert({best.ff,ind});
    }
    void del(int v, int t)
    {
        if(T[t].find(v) == T[t].end()) return;
        T[t].erase(T[t].find(v));
        total_gaps.erase(total_gaps.find({best.ff,ind}));
        int nxt0 = INF;
        auto it = T[0].lower_bound(v);
        if(it != T[0].end())
        {
            nxt0 = *it;
        }
        int prev0 = -INF;
        if(it != T[0].begin())
        {
            it--;
            prev0 = *it;
        }
        it = T[1].lower_bound(v);
        int nxt1 = INF;
        if(it != T[1].end())
        {
            nxt1 = *it;
        }
        int prev1 = -INF;
        if(it != T[1].begin())
        {
            it--;
            prev1 = *it;
        }
        if(t == 0)
        {
            if(nxt0 > nxt1)
            {
                gaps.erase(gaps.find({nxt1-v,{nxt1,v}}));
                if(prev0 > prev1)
                {
                    gaps.insert({nxt1-prev0,{nxt1,prev0}});
                }
            }
        }
        else
        {
            if(prev0 > prev1)
            {
                gaps.erase(gaps.find({v-prev0,{v,prev0}}));
                if(nxt1 < nxt0)
                {
                    gaps.insert({nxt1-prev0,{nxt1,prev0}});
                }
            }
        }
        if(siz(gaps) > 0) best = *gaps.begin();
        else best = {INF,{-1,-1}};
        total_gaps.insert({best.ff,ind});
    }
};

vector<dim> dims;
vector<pair<int,pii>> my_dims[200001];
int dim_num[200001][6];
pii poz[200001];
char type[200001];
bool is_dead[200001];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int n;
    cin >> n;
    map<int,int> dims_map[6];
    rep(i,n)
    {
        cin >> poz[i].ff >> poz[i].ss >> type[i];
        poz[i].ff *= 2;
        poz[i].ss *= 2;
        if(type[i] == 'N' || type[i] == 'E') dims_map[0][poz[i].ff-poz[i].ss] = 1;
        if(type[i] == 'N' || type[i] == 'W') dims_map[3][poz[i].ff+poz[i].ss] = 1;
        if(type[i] == 'S' || type[i] == 'E') dims_map[1][poz[i].ff+poz[i].ss] = 1;
        if(type[i] == 'S' || type[i] == 'W') dims_map[2][poz[i].ff-poz[i].ss] = 1;
        if(type[i] == 'N' || type[i] == 'S') dims_map[4][poz[i].ff] = 1;
        if(type[i] == 'W' || type[i] == 'E') dims_map[5][poz[i].ss] = 1;
    }
    int cur = 0;
    rep(d,6)
    {
        forall(it,dims_map[d])
        {
            dims.pb({{},{{},{}},cur});
            total_gaps.insert({INF,cur});
            dims_map[d][it.ff] = cur++;
        }
    }
    rep(i,n)
    {
        if(type[i] == 'N')
        {
            dims[dims_map[0][poz[i].ff-poz[i].ss]].add(poz[i].ff,i,1);
            dims[dims_map[3][poz[i].ff+poz[i].ss]].add(poz[i].ff,i,0);
            dims[dims_map[4][poz[i].ff]].add(poz[i].ff/2,i,1);
            my_dims[i].pb({dims_map[0][poz[i].ff-poz[i].ss],{poz[i].ff,1}});
            my_dims[i].pb({dims_map[3][poz[i].ff+poz[i].ss],{poz[i].ff,0}});
            my_dims[i].pb({dims_map[4][poz[i].ff],{poz[i].ff/2,1}});
            
        }
        if(type[i] == 'S')
        {
            dims[dims_map[1][poz[i].ff+poz[i].ss]].add(poz[i].ff,i,1);
            dims[dims_map[2][poz[i].ff-poz[i].ss]].add(poz[i].ff,i,0);
            dims[dims_map[4][poz[i].ff]].add(poz[i].ff/2,i,0);
            my_dims[i].pb({dims_map[1][poz[i].ff+poz[i].ss],{poz[i].ff,1}});
            my_dims[i].pb({dims_map[2][poz[i].ff-poz[i].ss],{poz[i].ff,0}});
            my_dims[i].pb({dims_map[4][poz[i].ff],{poz[i].ff/2,0}});
        }
        if(type[i] == 'E')
        {
            dims[dims_map[0][poz[i].ff-poz[i].ss]].add(poz[i].ff,i,0);
            dims[dims_map[1][poz[i].ff+poz[i].ss]].add(poz[i].ff,i,0);
            dims[dims_map[5][poz[i].ss]].add(poz[i].ss/2,i,0);
            my_dims[i].pb({dims_map[0][poz[i].ff-poz[i].ss],{poz[i].ff,0}});
            my_dims[i].pb({dims_map[1][poz[i].ff+poz[i].ss],{poz[i].ff,0}});
            my_dims[i].pb({dims_map[5][poz[i].ss],{poz[i].ss/2,0}});
        }
        if(type[i] == 'W')
        {
            dims[dims_map[2][poz[i].ff-poz[i].ss]].add(poz[i].ff,i,1);
            dims[dims_map[3][poz[i].ff+poz[i].ss]].add(poz[i].ff,i,1);
            dims[dims_map[5][poz[i].ss]].add(poz[i].ss/2,i,1);
            my_dims[i].pb({dims_map[2][poz[i].ff-poz[i].ss],{poz[i].ff,1}});
            my_dims[i].pb({dims_map[3][poz[i].ff+poz[i].ss],{poz[i].ff,1}});
            my_dims[i].pb({dims_map[5][poz[i].ss],{poz[i].ss/2,1}});
        }
    }
    while(!total_gaps.empty())
    {
        int time_ = (*total_gaps.begin()).ff;
        if(time_ == INF) break;
        vi verts_to_del;
        while((*total_gaps.begin()).ff == time_)
        {
            int comp = (*total_gaps.begin()).ss;
            while(dims[comp].best.ff == time_)
            {
                int v1 = dims[comp].real_map[dims[comp].best.ss.ff];
                int v2 = dims[comp].real_map[dims[comp].best.ss.ss];
                verts_to_del.pb(v1);
                verts_to_del.pb(v2);
                forall(it,my_dims[v1])
                {
                    if(it.ff != comp) continue;
                    dims[comp].del(it.ss.ff,it.ss.ss);
                }
                forall(it,my_dims[v2])
                {
                    if(it.ff != comp) continue;
                    dims[comp].del(it.ss.ff,it.ss.ss);
                }
            }
        }
        forall(it,verts_to_del)
        {
            is_dead[it] = 1;
            forall(it2,my_dims[it])
            {
                dims[it2.ff].del(it2.ss.ff,it2.ss.ss);
            }
        }
    }
    rep(i,n) if(!is_dead[i]) cout << i+1 << "\n";
}

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