Submission #1227205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227205		Malix	Naval battle (CEOI24_battle)	C++20	100 / 100	620 ms	96792 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

//0-N, 1-S, 2-E, 3-W

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
   int n;cin>>n;
   vii a(n,vi(3,0));
   REP(i,0,n){
    int x,y;cin>>x>>y;
    char z;cin>>z;
    swap(x,y);
    a[i][0]=x;
    a[i][1]=y;
    if(z=='S')a[i][2]=1;
    else if(z=='E')a[i][2]=2;
    else if(z=='W')a[i][2]=3;
   }
   unordered_map<int,set<pi>> P,Q,R,S,T,U;
   priority_queue<ti,vector<ti>,greater<ti>> pq;
   REP(i,0,n){
	int x=a[i][0],y=a[i][1],z=a[i][2];
	if(z==2||z==3)P[x].insert({y,i});
	if(z==0||z==1)Q[y].insert({x,i});
	if(z==2||z==1)R[x+y].insert({x,i});
	if(z==2||z==0)S[x-y].insert({x,i});
	if(z==3||z==1)T[x-y].insert({x,i});
	if(z==3||z==0)U[x+y].insert({x,i});
   }
   for(auto [u,v]:P){
	if(v.empty())continue;
	auto prev=v.begin();
	auto ps=next(prev);
	while(ps!=v.end()){
		int x=prev->S,y=ps->S;
		if(a[x][2]==2&&a[y][2]==3)pq.push({abs(a[x][1]-a[y][1])/2,x,y});
		prev=ps;
		ps=next(prev);
	}
   }
   for(auto [u,v]:Q){
	if(v.empty())continue;
	auto prev=v.begin();
	auto ps=next(prev);
	while(ps!=v.end()){
		int x=prev->S,y=ps->S;
		if(a[x][2]==1&&a[y][2]==0)pq.push({abs(a[x][0]-a[y][0])/2,x,y});
		prev=ps;
		ps=next(prev);
	}
   }
   for(auto [u,v]:R){
	if(v.empty())continue;
	auto prev=v.begin();
	auto ps=next(prev);
	while(ps!=v.end()){
		int x=prev->S,y=ps->S;
		if(a[x][2]==1&&a[y][2]==2)pq.push({abs(a[x][0]-a[y][0]),x,y});
		prev=ps;
		ps=next(prev);
	}
   }
   for(auto [u,v]:S){
	if(v.empty())continue;
	auto prev=v.begin();
	auto ps=next(prev);
	while(ps!=v.end()){
		int x=prev->S,y=ps->S;
		if(a[x][2]==2&&a[y][2]==0)pq.push({abs(a[x][0]-a[y][0]),x,y});
		prev=ps;
		ps=next(prev);
	}
   }
   for(auto [u,v]:T){
	if(v.empty())continue;
	auto prev=v.begin();
	auto ps=next(prev);
	while(ps!=v.end()){
		int x=prev->S,y=ps->S;
		if(a[x][2]==1&&a[y][2]==3)pq.push({abs(a[x][0]-a[y][0]),x,y});
		prev=ps;
		ps=next(prev);
	}
   }
   for(auto [u,v]:U){
	if(v.empty())continue;
	auto prev=v.begin();
	auto ps=next(prev);
	while(ps!=v.end()){
		int x=prev->S,y=ps->S;
		if(a[x][2]==3&&a[y][2]==0)pq.push({abs(a[x][0]-a[y][0]),x,y});
		prev=ps;
		ps=next(prev);
	}
   }
   vi b(n,inf);
   while(!pq.empty()){
		auto [z,x,y]=pq.top();
		pq.pop();
		if(b[x]<z||b[y]<z)continue;
		b[x]=z;b[y]=z;
		if(a[x][2]==0||a[x][2]==1){
			if(Q[a[x][1]].count({a[x][0],x})){
				auto it=Q[a[x][1]].find({a[x][0],x});
				auto nx=next(it);
				if(nx!=Q[a[x][1]].end()&&it!=Q[a[x][1]].begin()){
					auto pr=prev(it);
					int l=pr->S,r=nx->S;
					if(a[l][2]==1&&a[r][2]==0)pq.push({abs(a[l][0]-a[r][0])/2,l,r});
				}
				Q[a[x][1]].erase(it);
			}
		}
		if(a[x][2]==2||a[x][2]==3){
			if(P[a[x][0]].count({a[x][1],x})){
				auto it=P[a[x][0]].find({a[x][1],x});
				auto nx=next(it);
				if(nx!=P[a[x][0]].end()&&it!=P[a[x][0]].begin()){
					auto pr=prev(it);
					int l=pr->S,r=nx->S;
					if(a[l][2]==2&&a[r][2]==3)pq.push({abs(a[l][1]-a[r][1])/2,l,r});
				}
				P[a[x][0]].erase(it);
			}
		}
		int k=a[x][0]+a[x][1],k2=a[x][0]-a[x][1];
		if(a[x][2]==1||a[x][2]==2){
			if(R[k].count({a[x][0],x})){
				auto it=R[k].find({a[x][0],x});
				auto nx=next(it);
				if(nx!=R[k].end()&&it!=R[k].begin()){
					auto pr=prev(it);
					int l=pr->S,r=nx->S;
					if(a[l][2]==1&&a[r][2]==2)pq.push({abs(a[l][0]-a[r][0]),l,r});
				}
				R[k].erase(it);
			}
		}
		if(a[x][2]==0||a[x][2]==2){
			if(S[k2].count({a[x][0],x})){
				auto it=S[k2].find({a[x][0],x});
				auto nx=next(it);
				if(nx!=S[k2].end()&&it!=S[k2].begin()){
					auto pr=prev(it);
					int l=pr->S,r=nx->S;
					if(a[l][2]==2&&a[r][2]==0)pq.push({abs(a[l][0]-a[r][0]),l,r});
				}
				S[k2].erase(it);
			}
		}
		if(a[x][2]==1||a[x][2]==3){
			if(T[k2].count({a[x][0],x})){
				auto it=T[k2].find({a[x][0],x});
				auto nx=next(it);
				if(nx!=T[k2].end()&&it!=T[k2].begin()){
					auto pr=prev(it);
					int l=pr->S,r=nx->S;
					if(a[l][2]==1&&a[r][2]==3)pq.push({abs(a[l][0]-a[r][0]),l,r});
				}
				T[k2].erase(it);
			}
		}
		if(a[x][2]==0||a[x][2]==3){
			if(U[k].count({a[x][0],x})){
				auto it=U[k].find({a[x][0],x});
				auto nx=next(it);
				if(nx!=U[k].end()&&it!=U[k].begin()){
					auto pr=prev(it);
					int l=pr->S,r=nx->S;
					if(a[l][2]==3&&a[r][2]==0)pq.push({abs(a[l][0]-a[r][0]),l,r});
				}
				U[k].erase(it);
			}
		}
		swap(x,y);
		if(a[x][2]==0||a[x][2]==1){
			if(Q[a[x][1]].count({a[x][0],x})){
				auto it=Q[a[x][1]].find({a[x][0],x});
				auto nx=next(it);
				if(nx!=Q[a[x][1]].end()&&it!=Q[a[x][1]].begin()){
					auto pr=prev(it);
					int l=pr->S,r=nx->S;
					if(a[l][2]==1&&a[r][2]==0)pq.push({abs(a[l][0]-a[r][0])/2,l,r});
				}
				Q[a[x][1]].erase(it);
			}
		}
		if(a[x][2]==2||a[x][2]==3){
			if(P[a[x][0]].count({a[x][1],x})){
				auto it=P[a[x][0]].find({a[x][1],x});
				auto nx=next(it);
				if(nx!=P[a[x][0]].end()&&it!=P[a[x][0]].begin()){
					auto pr=prev(it);
					int l=pr->S,r=nx->S;
					if(a[l][2]==2&&a[r][2]==3)pq.push({abs(a[l][1]-a[r][1])/2,l,r});
				}
				P[a[x][0]].erase(it);
			}
		}
		k=a[x][0]+a[x][1],k2=a[x][0]-a[x][1];
		if(a[x][2]==1||a[x][2]==2){
			if(R[k].count({a[x][0],x})){
				auto it=R[k].find({a[x][0],x});
				auto nx=next(it);
				if(nx!=R[k].end()&&it!=R[k].begin()){
					auto pr=prev(it);
					int l=pr->S,r=nx->S;
					if(a[l][2]==1&&a[r][2]==2)pq.push({abs(a[l][0]-a[r][0]),l,r});
				}
				R[k].erase(it);
			}
		}
		if(a[x][2]==0||a[x][2]==2){
			if(S[k2].count({a[x][0],x})){
				auto it=S[k2].find({a[x][0],x});
				auto nx=next(it);
				if(nx!=S[k2].end()&&it!=S[k2].begin()){
					auto pr=prev(it);
					int l=pr->S,r=nx->S;
					if(a[l][2]==2&&a[r][2]==0)pq.push({abs(a[l][0]-a[r][0]),l,r});
				}
				S[k2].erase(it);
			}
		}
		if(a[x][2]==1||a[x][2]==3){
			if(T[k2].count({a[x][0],x})){
				auto it=T[k2].find({a[x][0],x});
				auto nx=next(it);
				if(nx!=T[k2].end()&&it!=T[k2].begin()){
					auto pr=prev(it);
					int l=pr->S,r=nx->S;
					if(a[l][2]==1&&a[r][2]==3)pq.push({abs(a[l][0]-a[r][0]),l,r});
				}
				T[k2].erase(it);
			}
		}
		if(a[x][2]==0||a[x][2]==3){
			if(U[k].count({a[x][0],x})){
				auto it=U[k].find({a[x][0],x});
				auto nx=next(it);
				if(nx!=U[k].end()&&it!=U[k].begin()){
					auto pr=prev(it);
					int l=pr->S,r=nx->S;
					if(a[l][2]==3&&a[r][2]==0)pq.push({abs(a[l][0]-a[r][0]),l,r});
				}
				U[k].erase(it);
			}
		}
	
   }
   REP(i,0,n)if(b[i]==inf)cout<<i+1<<"\n";
}

• 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