제출 #1126454

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126454		thelegendary08	마상시합 토너먼트 (IOI12_tournament)	C++17	49 / 100	293 ms	3328 KiB

tournament

#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define pb push_back
#define vi vector<int>
#define ll long long int
using namespace std;
const int mxn = 1e5 + 5;
int tree[mxn * 4];
int n;
void update(int k, int x){
	k += n;
	tree[k] = x;
	for(k/=2;k>=1;k/=2){
		tree[k] = max(tree[k*2], tree[k*2 + 1]);
	}
}
int quer(int l, int r){
	l += n;
	r += n;
	int ret = 0;
	while(l <= r){
		if(l % 2 == 1){
			ret = max(ret, tree[l++]);
		}
		if(r % 2 == 0){
			ret = max(ret, tree[r--]);
		}
		l/=2; r/=2;
	}
	return ret;
}
vi rupq(mxn * 4, 0);
void add(int k, int x){
	k += n + 1;
	rupq[k] += x;
	for(k/=2;k>=1;k/=2){
		rupq[k] = rupq[k * 2] + rupq[k * 2 + 1];
	}
}
int quer2(int l, int r){
	l += n + 1;
	r += n + 1;
	int ret = 0;
	while(l <= r){
		if(l % 2 == 1)ret += rupq[l++];
		if(r % 2 == 0)ret += rupq[r--];
		l/=2;
		r/=2;
	}
	return ret;
}
void rangeadd(int l, int r, int x){
	add(l, x);
	if(r != n){
		add(r + 1, -x);
	}
}
int GetBestPosition(int N, int C, int R, int *w, int *S, int *E) {
	n = N-1;
	vector<pair<int,int>>v;
	f0r(i, N){
		v.pb({i,i});
	}
	vector<pair<int,int>>quers;
	f0r(i, C){
		int st = v[S[i]].first;
		int en = v[E[i]].second;
		quers.pb({st,en});
		v[S[i]].second = en;
		v.erase(v.begin() + S[i] + 1, v.begin() + E[i] + 1);
		/*
		f0r(j,v.size()){
			//cout<<v[j].first<<' '<<v[j].second<<'\n';
		}
		//cout<<'\n';
		*/
	}
	if(N <= 5000){
		f0r(i, N-1){
			update(i, w[i]);
		}
		f0r(i, C){
			int l = quers[i].first;
			int r = quers[i].second - 1;
			
			
			if(quer(l, r) < R){
				//cout<<l<<' '<<r+1<<'\n';
				//cout<<quer(l,r)<<'\n';
				rangeadd(l, r+1, 1);
			}
		}
		int mx = 0;
		int ans = 0;
		vi diffarr;
		f0r(i,N){
			diffarr.pb(rupq[i + N]);
		}
		vi realarr;
		realarr.pb(diffarr[0]);
		for(int i=1;i<N;i++){
			realarr.pb(realarr[i-1] + diffarr[i]);
		}
		f0r(i, N){
			//cout<<quer2(0,i)<<' ';
			if(realarr[i] > mx){
				mx = realarr[i];
				ans = i;
			}
		}
		//cout<<'\n';
		return ans;
	}
	else return 0;
	

}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 0 / 51