Submission #747587

#	Time	Username	Problem	Language	Result	Execution time	Memory
747587		bane	Teams (IOI15_teams)	C++17	0 / 100	406 ms	114524 KiB

teams

#include "teams.h"
 
#include "bits/stdc++.h"
using namespace std;
int n;
vector<pair<int,int>> intervals;
const int maxN = (int)5e5 + 1; 
 
class SegmentTree{
	
	public:
	pair<int,int> Seg[maxN * 3]; //{min A value in B range, its position}
	multiset<int>Left[maxN * 3];
	
	void init(){
		for (int i = 0; i < n * 3; i++){
			Seg[i] = {(int)1e9, -1};
		}
	}
	
	void upd(int pos, int val, int l = 1, int r = n, int k = 1){
		if (l == r){
			Left[k].insert(val);
			Seg[k] = {*Left[k].begin(), l};
			return;
		}
		int md = (l + r) / 2;
		if (pos <= md)upd(pos,val,l,md,k*2);
		else upd(pos,val,md+1,r,k*2+1);
		if (Seg[k * 2].first < Seg[k * 2 + 1].first){
			Seg[k] = Seg[k * 2];
		}else{
			Seg[k] = Seg[k * 2 + 1];
		}
	}
	
	pair<int,int>query(int a, int b, int l = 1, int r = n, int k = 1){
		if (l > b || r < a)return {(int)1e9,-1};
		if (l >= a && r <= b){
			return Seg[k];
		}
		auto left = query(a,b,l,(l+r)/2,k*2);
		auto right = query(a,b,(l+r)/2+1,r,k*2+1);
		if (left.first < right.first)return left;
		else return right;
	}
	
	void remove(int pos, int val, int l = 1, int r = n, int k = 1){
		if (l == r){
			Left[k].erase(Left[k].find(val));
			if (Left[k].size()){
				Seg[k] = {*Left[k].begin(),l};
			}else{
				Seg[k] = {(int)1e9, -1};
			}
			return;
		}
		int md = (l + r) / 2;
		if (pos <= md)remove(pos,val,l,md,k*2);
		else remove(pos,val,md+1,r,k*2+1);
		if (Seg[k * 2].first < Seg[k * 2 + 1].first){
			Seg[k] = Seg[k * 2];
		}else{
			Seg[k] = Seg[k * 2 + 1];
		}
	}
	
	
};
SegmentTree st;
void init(int N, int A[], int B[])
{
	n = N;
	intervals.resize(N);
	st.init();
	for (int i = 0; i < N; ++i){
		intervals[i] = {A[i], B[i]};
		st.upd(B[i], A[i]);
	}
	
}
 
int can(int M, int K[])
{
	sort(K, K + M);
	for (int i = 0; i < M; i++){
		int l = K[i], r = n;
		pair<int,int>ans = {(int)1e9, -1};
		while(l<=r){
			int md = (l + r) / 2;
			auto response = st.query(K[i], md);
			if (response.first <= K[i]){
				ans = response;
				r = md - 1;
			}else{
				l = md + 1;
			}
		}
		if (ans.first == (int)1e9){
			return 0;
		}
		st.remove(ans.second,ans.first);
	}
	return 1;
}

/*int main(){
	int N, M;
	cin >> N >> M;
	int A[N], B[N];
	for (int i = 0; i < N; i++){
		cin >> A[i] >> B[i];
	}
	init(N,A,B);
	int K[M];
	for(int i = 0; i < M; i++){
		cin >> K[i];
	}
	cout<<(can(M,K) ? "YES":"NO");
}*/

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23