제출 #1132883

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

tournament

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;
const int LOGN = 20;

struct Binary_Lifting{
	int pai[2*N][LOGN];
	int maxval;
	void build(){
		maxval = 1;
		for(int i = 0;i < 2*N;i++){
			pai[i][0] = i;
		}
	}
	void add(int a, int b){
		pai[a][0] = b;
		maxval = max(maxval, b);
	}
	void construct(){
		for(int bit = 1;bit < LOGN;bit++){
			for(int i = 1;i <= maxval;i++){
				pai[i][bit] = pai[pai[i][bit-1]][bit-1];
			}
		}
	}
	int query(int pos, int qtd){
		for(int i = 0;i < LOGN;i++){
			if(((1<<i)&qtd)){
				pos = pai[pos][i];
			}
		}
		return pos;
	}
} bin;

struct Segtree{
	int tree[4*N], lazy[4*N];
	void build(int node, int l, int r){
		lazy[node] = -1;
		if(l == r){
			tree[node] = 1;
			return;
		}
		int mid = (l+r)/2;
		build(2*node, l, mid);
		build(2*node+1, mid+1, r);
		tree[node] = tree[2*node]+tree[2*node+1];
		return;
	}
	void unlazy(int node, int l, int r){
		if(lazy[node] == -1) return;
		tree[node] = lazy[node]*(r-l+1);
		if(l != r){
			lazy[2*node] = lazy[node];
			lazy[2*node+1] = lazy[node];
		}
		lazy[node] = -1;
	}
	void update(int node, int l, int r, int tl, int tr, int val){
		unlazy(node, tl, tr);
		if(l > tr or tl > r) return;
		if(l <= tl and tr <= r){
			lazy[node] = val;
			unlazy(node, tl, tr);
			return;
		}
		int mid = (tl+tr)/2;
		update(2*node, l, r, tl, mid, val);
		update(2*node+1, l, r, mid+1, tr, val);
		tree[node] = tree[2*node]+tree[2*node+1];
		return;
	}
	int query(int node, int l, int r, int tl, int tr){
		unlazy(node, tl, tr);
		if(l > tr or tl > r) return 0;
		if(l <= tl and tr <= r) return tree[node];
		int mid = (tl+tr)/2;
		return query(2*node, l, r, tl, mid)+query(2*node+1, l, r, mid+1, tr);
	}
	int search(int node, int l, int r, int val){
		if(l == r) return l;
		int mid = (l+r)/2;
		if(tree[2*node] >= val) return search(2*node, l, mid, val);
		else return search(2*node+1, mid+1, r, val-tree[2*node]);
	}
} seg;

struct DSU{
	int pai[N], val[N];
	void build(){
		for(int i = 0;i < N;i++){
			pai[i] = i;
			val[i] = i;
		}
	}
	pair <int, int> find(int x){
		if(x == pai[x]) return {x, val[x]};
		auto [p, v] = find(pai[x]);
		pai[x] = p;
		val[x] = v;
		return {p, v};
	}
	void join(int a, int b, int v){
		a = find(a).first;
		b = find(b).first;
		if(a == b) {
			val[a] = v;
			return;
		}
		if(a > b) swap(a, b);
		pai[a] = b;
		val[b] = v;
	}
	void query(int l, int r, int valor){
		vector <pair <int, int>> juntar;
		while(l <= r){
			auto [rr, v] = find(l);
			l = rr+1;
			juntar.push_back({rr, v});
		}
		for(auto [x, v] : juntar){
			join(x, r, valor);
			bin.add(v, valor);
		}
	}
} dsu;

vector <array <int, 3>> intervalos;
pair <int, int> inter[2*N];

int GetBestPosition(int n, int c, int r, int *k, int *s, int *e) {
	seg.build(1, 1, n);
	for(int i = 0;i < c;i++){
		int l = (s[i] == 0 ? 1 : seg.search(1, 1, n, s[i])+1);
		int r = seg.search(1, 1, n, e[i]+1);
		intervalos.push_back({l, r, i+1+n});
		seg.update(1,l, r-1, 1, n, 0);
	}
	dsu.build();
	bin.build();
	for(auto [l, r, v] : intervalos){
		dsu.query(l, r, v);
		inter[v] = {l, r};
	}
	for(int i = 1;i <= n;i++){
		inter[i] = {i, i};
	}
	/*for(int i = 1;i <= bin.maxval;i++){
		cout << inter[i].first << ' ' << inter[i].second << endl;
	}*/
	bin.construct();
  	seg.update(1, 1, 1, 1, n, 0);
  	for(int i = 2;i <= n;i++){
  		int valor = k[i-2];
  		if(k[i-2] < r) seg.update(1, i, i, 1, n, 0);
  		else seg.update(1, i, i, 1, n, 1);
  	}
  	int res = 0, qtd = -1;
  	for(int i = 1;i <= n;i++){
  		int l = 0, r = bin.maxval;
  		int ans = 0;
  		while(l <= r){
  			int mid = (l+r)/2;
  			int valor = bin.query(i, mid);
  			int valor2 = bin.query(i, mid-1);
  			if(valor == valor2) r = mid-1;
  			else{
  				int v = seg.query(1, inter[valor].first, inter[valor].second, 1, n);
  				if(i == 4 and mid == 1){
  					//cout << valor << ' ' << inter[valor].first << ' ' << inter[valor].second << endl;
  				}
  				if(v == 0){
  					ans = mid;
  					l = mid+1;
  				}
  				else{
  					r = mid-1;
  				}
  			}
  		}
  		//cout << ans << ' ';
  		if(ans > qtd){
  			res = i-1;
  			qtd = ans;
  		}
  		if(i == n) break;
  		int t = seg.query(1, i+1, i+1, 1, n);
  		seg.update(1, i, i, 1, n, t);
  		seg.update(1, i+1,i+1, 1, n, 0);
  	}
  	return res;
}

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