Submission #796503

#	Time	Username	Problem	Language	Result	Execution time	Memory
796503		esomer	Jousting tournament (IOI12_tournament)	C++17	100 / 100	205 ms	19072 KiB

tournament

#include<bits/stdc++.h>
//~ #include "tournament.h"

using namespace std;

struct segTree{
	vector<int> sum, mn, mx;
	int sz, siz;
	void init(int n){
		sz = 1;
		while(sz < n) sz *= 2;
		siz = sz;
		sum.assign(2 * sz, 0);
		mn.assign(2 * sz, 1e9);
		mx.assign(2 * sz, -1);
	}
	
	void set(int i, int val, int x, int lx, int rx){
		if(rx - lx == 1){
			sum[x] = val;
			return;
		}
		int m = (lx + rx) / 2;
		if(i < m) set(i, val, 2 * x + 1, lx, m);
		else set(i, val, 2 * x + 2, m, rx);
		sum[x] = sum[2 * x + 1] + sum[2 * x + 2];
	}
	
	void set(int i, int val){
		set(i, val, 0, 0, siz);
	}
	
	void set_mn(int i, int val, int x, int lx, int rx, bool obl){
		if(rx - lx == 1){
			if(obl == 0) mn[x] = min(val, mn[x]);
			else mn[x] = val;
			return;
		}
		int m = (lx + rx) / 2;
		if(i < m) set_mn(i, val, 2 * x + 1, lx, m, obl);
		else set_mn(i, val, 2 * x + 2, m, rx, obl);
		mn[x] = min(mn[2 * x + 1], mn[2 * x + 2]);
	}
	
	void set_mn(int i, int val, bool obl = 0){
		set_mn(i, val, 0, 0, siz, obl);
	}
	
	void set_mx(int i, int val, int x, int lx, int rx, bool obl){
		if(rx - lx == 1){
			if(obl == 0) mx[x] = max(val, mx[x]);
			else mx[x] = val;
			return;
		}
		int m = (lx + rx) / 2;
		if(i < m) set_mx(i, val, 2 * x + 1, lx, m, obl);
		else set_mx(i, val, 2 * x + 2, m, rx, obl);
		mx[x] = max(mx[2 * x + 1], mx[2 * x + 2]);
	}
	
	void set_mx(int i, int val, bool obl = 0){
		set_mx(i, val, 0, 0, siz, obl);
	}
	
	int walk(int val, int x, int lx, int rx, int curr){
		if(rx - lx == 1){
			//~ cout << "lx " << lx << " rx " << rx << " val " << val << " curr " << curr << " sum " << sum[x] << endl; 
			assert(curr + sum[x] == val);
			return lx;
		}
		int m = (lx + rx) / 2;
		if(sum[2 * x + 1] + curr >= val) return walk(val, 2 * x + 1, lx, m, curr);
		else return walk(val, 2 * x + 2, m, rx, curr + sum[2 * x + 1]);
	}
	
	int walk(int val){
		return walk(val, 0, 0, siz, 0);
	}
	
	int calc_mn(int l, int r, int x, int lx, int rx){
		if(lx >= l && rx <= r){
			return mn[x];
		}else if(lx >= r || rx <= l) return 1e9;
		int m = (lx + rx) / 2;
		int c1 = calc_mn(l, r, 2 * x + 1, lx, m);
		int c2 = calc_mn(l, r, 2 * x + 2, m, rx);
		return min(c1, c2);
	}
	
	int calc_mn(int l, int r){
		return calc_mn(l, r, 0, 0, siz);
	}
	
	int calc_mx(int l, int r, int x, int lx, int rx){
		if(lx >= l && rx <= r){
			return mx[x];
		}else if(lx >= r || rx <= l) return -1e9;
		int m = (lx + rx) / 2;
		int c1 = calc_mx(l, r, 2 * x + 1, lx, m);
		int c2 = calc_mx(l, r, 2 * x + 2, m, rx);
		return max(c1, c2);
	}
	
	int calc_mx(int l, int r){
		return calc_mx(l, r, 0, 0, siz);
	}
	
	int get_mn(int i){
		return calc_mn(i, i + 1);
	}
	
	int get_mx(int i){
		return calc_mx(i, i + 1);
	}
};

struct segTree2{
	vector<int> sums;
	int sz, siz;
	void init(int n){
		sz = 1;
		while(sz < n) sz *= 2;
		siz = sz;
		sums.assign(2 * sz, 0);
	}
	
	void set(int i, int val, int x, int lx, int rx){
		if(rx - lx == 1){
			sums[x] = val;
			return;
		}
		int m = (lx + rx) / 2;
		if(i < m) set(i, val, 2 * x + 1, lx, m);
		else set(i, val, 2 * x + 2, m, rx);
		sums[x] = sums[2 * x + 1] + sums[2 * x + 2];
	}
	
	void set(int i, int val){
		set(i, val, 0, 0, siz);
	}
	
	int sum(int l, int r, int x, int lx, int rx){
		if(lx >= l && rx <= r) return sums[x];
		else if(lx >= r || rx <= l) return 0;
		int m = (lx + rx) / 2;
		int s1 = sum(l, r, 2 * x + 1, lx, m);
		int s2 = sum(l, r, 2 * x + 2, m, rx);
		return s1 + s2;
	}
	
	int sum(int l, int r){
		return sum(l, r, 0, 0, siz);
	}
};

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
	vector<pair<int, int>> queries(C);
	segTree st; st.init(N);
	for(int i = 0; i < N; i++){
		st.set_mn(i, i);
		st.set_mx(i, i);
		st.set(i, 1);
	}
	for(int i = 0; i < C; i++){
		S[i]++; E[i]++;
		//~ cout << "i " << i << " s[i] " << S[i] << endl;
		int mn = 1e9;
		int mx = -1e9;
		int total = 0;
		int first = -1;
		while(total < E[i] - S[i] + 1){
			total++;
			int ind = st.walk(S[i]);
			if(first == -1) first = ind;
			st.set(ind, 0);
			mn = min(mn, st.get_mn(ind));
			mx = max(mx, st.get_mx(ind));
		}
		st.set(first, 1);
		st.set_mn(first, mn);
		st.set_mx(first, mx);
		queries[i] = {mn, mx};
	}
	for(int i = 0; i < N; i++){
		st.set_mx(i, K[i], 1);
	}
	vector<vector<pair<int, int>>> start(N);
	vector<vector<pair<int, int>>> ends(N);
	for(int i = 0; i < C; i++){
		start[queries[i].first].push_back({queries[i].second, i});
	}
	segTree2 stq; stq.init(C);
	int mx_wins = 0;
	int ans = 0;
	set<int> bad;
	for(int i = 0; i < N; i++){
		for(pair<int, int> p : start[i]){
			ends[p.first].push_back({i, p.second});
			int mx = st.calc_mx(i, p.first);
			if(mx < R) stq.set(p.second, 1);
			else bad.insert(p.second);
		}
		for(pair<int, int> p : ends[i]){
			int l = p.first;
			int mx = st.calc_mx(l, i);
			if(mx < R) stq.set(p.second, 0);
			else bad.erase(p.second);
		}
		int hi = C;
		if((int)bad.size() > 0) hi = *bad.begin();
		int wins = stq.sum(0, hi);
		if(wins > mx_wins){
			mx_wins = wins;
			ans = i;
		}
	}
	return ans;
}

//~ int main() {
  //~ int tmp;

  //~ int N, C, R;
  //~ int *K, *S, *E;
  //~ tmp = scanf("%d %d %d", &N, &C, &R);
  //~ assert(tmp == 3);
  //~ K = (int*) malloc((N-1) * sizeof(int));
  //~ S = (int*) malloc(C * sizeof(int));
  //~ E = (int*) malloc(C * sizeof(int));
  //~ int i;
  //~ for (i = 0; i < N-1; i++) {
    //~ tmp = scanf("%d", &K[i]);
    //~ assert(tmp == 1);
  //~ }
  //~ for (i = 0; i < C; i++) {
    //~ tmp = scanf("%d %d", &S[i], &E[i]);
    //~ assert(tmp == 2);
  //~ }

  //~ printf("%d\n", GetBestPosition(N, C, R, K, S, E));

  //~ return 0;

//~ }

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