Submission #1069019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069019		huutuan	Naval battle (CEOI24_battle)	C++14	100 / 100	1850 ms	437780 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int inf=2e9;
const int N=2e5+10, dx[]={0, 0, 1, -1}, dy[]={-1, 1, 0, 0};
const string dir="NSEW";

struct DS{
   map<int, array<int, 3>> mp;
   set<array<int, 3>> st;
   set<pair<int, pair<array<int, 3>, array<int, 3>>>> d;
   void add(int x, int i, int t){
      mp[i]={x, i, t};
      st.insert({x, i, t});
   }
   void build(){
      for (auto it=st.begin(); it!=st.end() && next(it)!=st.end(); ++it){
         if (it->begin()[2]==0 && next(it)->begin()[2]==1){
            d.insert({next(it)->begin()[0]-it->begin()[0], {*it, *next(it)}});
         }
      }
   }
   void erase(pair<array<int, 3>, array<int, 3>> p){
      auto it=st.find(p.first);
      d.erase({p.second[0]-p.first[0], p});
      it=st.erase(it);
      it=st.erase(it);
      if (it!=st.begin() && it!=st.end() && prev(it)->begin()[2]==0 && it->begin()[2]==1){
         d.insert({it->begin()[0]-prev(it)->begin()[0], {*prev(it), *it}});
      }
   }
   void erase(int i){
      auto it=st.find(mp[i]);
      if (it==st.end()) return;
      if (it!=st.begin() && prev(it)->begin()[2]==0 && it->begin()[2]==1){
         d.erase({it->begin()[0]-prev(it)->begin()[0], {*prev(it), *it}});
      }
      if (it!=st.end() && it->begin()[2]==0 && next(it)->begin()[2]==1){
         d.erase({next(it)->begin()[0]-it->begin()[0], {*it, *next(it)}});
      }
      it=st.erase(it);
      if (it!=st.begin() && it!=st.end() && prev(it)->begin()[2]==0 && it->begin()[2]==1){
         d.insert({it->begin()[0]-prev(it)->begin()[0], {*prev(it), *it}});
      }
   }
   int get(){
      if (d.empty()) return inf;
      return d.begin()->first;
   }
};

int n, x[N], y[N], d[N], t[N], ans[N];
char c[N];

// 23, 10, 20, 13, 30, 12
map<int, DS> mp[4][4];
vector<DS> v;
vector<int> id[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n;
   for (int i=1; i<=n; ++i){
      cin >> x[i] >> y[i] >> c[i]; ans[i]=1;
      t[i]=2e9;
      d[i]=dir.find(c[i]);
   }
   for (int i=1; i<=n; ++i){
      if (d[i]==0){
         mp[1][0][x[i]].add(y[i]/2, i, 1);
         mp[2][0][x[i]-y[i]].add(y[i], i, 1);
         mp[3][0][x[i]+y[i]].add(y[i], i, 1);
      }
      if (d[i]==1){
         mp[1][0][x[i]].add(y[i]/2, i, 0);
         mp[1][3][x[i]-y[i]].add(y[i], i, 0);
         mp[1][2][x[i]+y[i]].add(y[i], i, 0);
      }
      if (d[i]==2){
         mp[2][3][y[i]].add(x[i]/2, i, 0);
         mp[2][0][x[i]-y[i]].add(y[i], i, 0);
         mp[1][2][x[i]+y[i]].add(y[i], i, 1);
      }
      if (d[i]==3){
         mp[2][3][y[i]].add(x[i]/2, i, 1);
         mp[1][3][x[i]-y[i]].add(y[i], i, 1);
         mp[3][0][x[i]+y[i]].add(y[i], i, 0);
      }
   }
   for (int i=0; i<4; ++i) for (int j=0; j<4; ++j){
      for (auto &k:mp[i][j]) v.push_back(k.second);
   }
   set<pair<int, int>> st;
   for (int i=0; i<(int)v.size(); ++i){
      for (auto &j:v[i].st) id[j[1]].push_back(i); 
      v[i].build();
      st.emplace(v[i].get(), i);
   }
   while (st.size()){
      int val=st.begin()->first;
      if (val==inf) break;
      vector<int> vv;
      for (auto it=st.begin(); it!=st.end(); ++it){
         if (it->first!=val) break;
         vv.push_back(it->second);
      }
      set<int> del;
      for (int i:vv){
         while (v[i].get()==val){
            st.erase({v[i].get(), i});
            auto p=v[i].d.begin()->second;
            v[i].erase(p);
            del.insert(p.first[1]); del.insert(p.second[1]);
            st.erase({v[i].get(), i});
         }
      }
      for (int i:del){
         ans[i]=0;
         for (int j:id[i]){
            st.erase({v[j].get(), j});
            v[j].erase(i);
            st.insert({v[j].get(), j});
         }
      }
   }
   for (int i=1; i<=n; ++i) if (ans[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