Submission #1022823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022823		Mr_Husanboy	Jousting tournament (IOI12_tournament)	C++17	100 / 100	76 ms	8548 KiB

tournament

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()

template<typename T>
int len(T &a){return a.size();}

struct fenwick{
	vector<int> t;
	int n;
	fenwick(){	}
	fenwick(int _n){
		init(_n);
	}
	void init(int _n){
		n = _n;
		t.assign(n,0);
	}
	
	void init(vector<int> &a){
		init(size(a));
		for(int i = 0; i < n; i ++){
			inc(i,a[i]);
		}
	}

	void inc(int i, int val = 1){
		for(; i < n; i = i | (i + 1)){
			t[i] += val;
		}
	}
	int get(int i){
		int sum = 0;
		for(; i >= 0; i = (i & (i + 1)) - 1){
			sum += t[i];
		}
		return sum;
	}
	
	int get(int l, int r){
		return get(r) - get(l - 1);
	}

	int findkthone(int k){
		int l = -2, r = n;
		while(r - l > 1){
			int m = (l + r) / 2;
			if(get(m) < k){
				l = m;
			}else r = m;
		}
		return r;
	}

	void out(){
		for(int i = 0; i < n; i ++){
			cout << get(i) - get(i - 1);
		}cout << endl;
	}
};

struct DSU{
	int n;
	vector<int> p, sz;
	DSU (){}
	DSU (int n) : n(n), p(n), sz(n){
		for(int i = 0; i < n; i++){
			p[i] = i, sz[i] = 1;
		}
	}

	int get(int a){
		return a == p[a] ? a : p[a] = get(p[a]);
	}

	void unite(int a, int b){
		a = get(a), b = get(b);
		if(a == b) return;
		if(sz[a] < sz[b]) swap(a, b);
		sz[a] += sz[b];
		p[b] = a;
	}
	void link(int a, int b){
		a = get(a), b = get(b);
		if(a == b) return;
		p[a] = b;
		sz[b] += sz[a];
	}

};

template<typename T>
void out(T a){
	cout << "{";
	for(auto u : a) cout << u << ' ';
	cout << "}" << endl;
}

struct Segtree{
	int n;
	vector<int> t;
	int merge(int a, int b){
		return max(a, b);
	}

	Segtree (){}
	Segtree (int n) : n(n), t(2 * n){}

	void build(vector<int> &a, int _n){
		n = _n;
		t.resize(2 * n);
		for(int i = 0; i < n; i ++){
			t[i + n] = a[i];
		}
		for(int i = n - 1; i > 0; i --){
			t[i] = merge(t[i * 2], t[i * 2 + 1]);
		}
	}

	void upd(int i, int val){
		i += n;
		t[i] = val;
		for(i /= 2; i > 0; i /= 2) t[i] = merge(t[i * 2], t[i * 2 + 1]);
	}
	
	int get(int l, int r){
		l += n; r += n;
		int res = 0;
		while(l <= r){
			if(l & 1){
				res = merge(res, t[l ++]);
			}
			if(!(r & 1)){
				res = merge(res, t[r --]);
			}
			r /= 2;
			l /= 2;
		}
		return res;
	}
};


int GetBestPosition(int n, int c, int r, int *k, int *s, int *e){
	fenwick f(n);
	DSU ds(n + 1);
	for(int i = 0; i < n; i ++) f.inc(i, 1);

	for(int j = 0; j < c; j ++){
		int l = f.findkthone(s[j] + 1);
		vector<int> p = {l};
		int sz = e[j] - s[j];
		s[j] = f.findkthone(s[j]) + 1;
		while(len(p) < sz){
			l = ds.get(l + 1);
			p.push_back(l);
		}
		e[j] = ds.get(l + 1);
		for(auto u : p){
			f.inc(u, -1);
			ds.link(u, u + 1);
		}
	}
	vector<vector<int>> lef(n);
	for(int i = 0; i < c; i ++) lef[s[i]].push_back(e[i]);
	int last = 0;
	vector<int> pref(n + 1);
	for(int i = 0; i < n - 1; i ++){
		if(k[i] > r){
			if(i == last){
				last = i + 1; continue;
			}
			for(int j = last; j <= i; j ++){
				for(auto r : lef[j]){
					if(r > i) continue;
					pref[j] ++;
					pref[r + 1] --;
				}
			}
			last = i + 1;
		}
	}
	if(last != n - 1){
		for(int j = last; j < n; j ++){
			for(auto r : lef[j]){
				if(r > n) continue;
				pref[j] ++;
				pref[r + 1] --;
			}
		}
	}
	int mx = -1;
	int ans = 0;
	int wins = 0;
	for(int i = 0; i < n; i ++){
		wins += pref[i];
		//cout << wins << endl;
		if(mx < wins){
			mx = wins;
			ans = i;
		}
	}
	return ans;
}

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