제출 #1126448

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126448		thelegendary08	Jousting tournament (IOI12_tournament)	C++17	49 / 100	1096 ms	4720 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';
	}
	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;
	f0r(i, N){
		//cout<<quer2(0,i)<<' ';
		if(quer2(0, i) > mx){
			mx = quer2(0,i);
			ans = i;
		}
	}
	//cout<<'\n';
	return ans;

}

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