제출 #1052784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1052784		beaconmc	Naval battle (CEOI24_battle)	C++14	30 / 100	204 ms	26028 KiB

Main

#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)

using namespace std;
vector<vector<ll>> easts, souths;

int main(){
	ll n; cin >> n;

	FOR(i,0,n){
		ll x,y;
		cin >> x >> y;
		char s;
		cin >> s;
		if (s=='S'){
			souths.push_back({x, (x+y), i+1});
		}else{
			easts.push_back({x, (x+y), i+1});
		}
	}
	sort(souths.begin(), souths.end());
	sort(easts.begin(), easts.end());
	reverse(easts.begin(), easts.end());


	set<vector<ll>> stuff;
	vector<ll> left;


	for (auto&i : easts){

		
		while (souths.size() && souths[souths.size()-1][0] > i[0]){
			stuff.insert({souths[souths.size()-1][1], souths[souths.size()-1][0], souths[souths.size()-1][2]});
			souths.pop_back();
		}

		// for (auto&i : stuff){
		// 	cout << i[0] << " " << i[1] << " " << i[2] << endl;
		// }
		// cout << i[1] << " " << i[2] << endl;
		// cout << "FUCK" << endl;
		if (stuff.upper_bound({i[1], -1,-1}) == stuff.end()){

			left.push_back(i[2]);
			continue;
		}

		vector<ll> temp = *stuff.upper_bound({i[1], -1,-1});


		if (temp[0] == i[1]){
			stuff.erase(temp);
		}else{
			left.push_back(i[2]);
		}
	}




	for (auto&i : stuff){
		left.push_back(i[2]);
	}
	for (auto&i : souths){
		left.push_back(i[2]);
	}
	for (auto&i: left){
		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