Submission #1140703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140703		adiyer	Naval battle (CEOI24_battle)	C++20	30 / 100	663 ms	53460 KiB

Main

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define F first
#define S second

using namespace std;

typedef long long ll;

const int N = 2e5 + 11;
const int mod = 1e9 + 7;
const ll inf = 1e12 + 11;

ll n;

pair < pair < ll, ll >, ll > a[N];

vector < pair < ll, ll > > v[4];

map < ll, set < pair < ll, ll > > > sp, np, xp, yp;

map < pair < pair < ll, ll >, ll >, bool > del;

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  for(ll i = 1; i <= n; i++){
    char d;
    ll x, y, tp;
    cin >> x >> y >> d;
    if(d == 'E') tp = 0;
    if(d == 'S') tp = 1;
    if(d == 'W') tp = 2;
    if(d == 'N') tp = 3;
    a[i] = {{x, y}, tp};
    v[tp].push_back({x, y});
  }
  /***********/
  sp.clear(), np.clear(), yp.clear(), xp.clear();
  for(ll i = 1; i <= n; i++){
    ll x = a[i].F.F, y = a[i].F.S;
    if(a[i].S == 1) sp[x + y].insert({x, y});
    if(a[i].S == 3) np[x - y].insert({x, y});
    if(a[i].S == 2) yp[y].insert({x, y});
  }
  sort(all(v[0])), reverse(all(v[0]));
  for(auto [x, y] : v[0]){
    pair < ll, ll > it1, it2, it3, it4;
    it1 = it2 = it3 = it4 = {inf, inf};
    if(sp[x + y].upper_bound({x, y}) != sp[x + y].end()){
      it1 = (*sp[x + y].upper_bound({x, y}));
    }
    if(np[x - y].upper_bound({x, y}) != np[x - y].end()){
      it2 = (*np[x - y].upper_bound({x, y}));
    }
    if(yp[y].upper_bound({x, y}) != yp[y].end()){
      it3 = (*yp[y].upper_bound({x, y}));
    }
    if(it1 == it4 && it2 == it4 && it3 == it4) continue;
    ll vx = it1.F - x, vy = it2.F - x, vz = (it3.F - x) / 2, mn = min({vx, vy, vz});
    del[{{x, y}, 0}] = 1;
    if(vx == mn) del[{it1, 1}] = 1, sp[x + y].erase(it1);
    if(vy == mn) del[{it2, 3}] = 1, np[x - y].erase(it2);
    if(vz == mn) del[{it3, 2}] = 1, yp[y].erase(it3);
  }
  /***********/
  sp.clear(), np.clear(), yp.clear(), xp.clear();
  for(ll i = 1; i <= n; i++){
    if(del[a[i]]) continue;
    ll x = a[i].F.F, y = a[i].F.S;
    if(a[i].S == 3) sp[x + y].insert({x, y});
    if(a[i].S == 1) np[x - y].insert({x, y});
  }
  sort(all(v[2]));
  for(auto [x, y] : v[2]){
    if(del[{{x, y}, 2}]) continue;
    pair < ll, ll > it1, it2, it3;
    it1 = it2 = it3 = {inf, inf};
    if(sp[x + y].upper_bound({x, y}) != sp[x + y].begin()){
      it1 = *(--sp[x + y].upper_bound({x, y}));
    }
    if(np[x - y].upper_bound({x, y}) != np[x - y].begin()){
      it2 = *(--np[x - y].upper_bound({x, y}));
    }
    if(it1 == it3 && it2 == it3) continue;
    ll vx = x - it1.F, vy = x - it2.F, mn = min(vx, vy);
    del[{{x, y}, 2}] = 1;
    if(vx == mn) del[{it1, 3}] = 1, sp[x + y].erase(it1);
    if(vy == mn) del[{it2, 1}] = 1, np[x - y].erase(it2);
  }
  /***********/
  sp.clear(), np.clear(), yp.clear(), xp.clear();
  for(ll i = 1; i <= n; i++){
    if(del[a[i]]) continue;
    ll x = a[i].F.F, y = a[i].F.S;
    if(a[i].S == 3) xp[x].insert({x, y});
  }
  for(auto &it : v[1]) swap(it.F, it.S);
  sort(all(v[1])), reverse(all(v[1]));
  for(auto &it : v[1]) swap(it.F, it.S);
  for(auto [x, y] : v[1]){
    if(del[{{x, y}, 1}]) continue;
    pair < ll, ll > it1, it2;

    it1 = it2 = {inf, inf};
    if(xp[x].upper_bound({x, y}) != xp[x].end()){
      it1 = *(xp[x].upper_bound({x, y}));
    }
    if(it1 == it2) continue;
    del[{{x, y}, 1}] = 1;
    del[{it1, 3}] = 1, xp[x].erase(it1);
  }
  for(ll i = 1; i <= n; i++){
    if(del[a[i]]) continue;
    cout << i << '\n';
  }
}

• 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: 30 / 30
• Subtask 7: 0 / 24