Submission #382789

#	Time	Username	Problem	Language	Result	Execution time	Memory
382789		Keshi	Jousting tournament (IOI12_tournament)	C++17	100 / 100	181 ms	26988 KiB

tournament

//In the name of God
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll maxn = 3e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
#define lc (id << 1)
#define rc (lc | 1)

ll seg[maxn << 2];

void bld(ll id, ll s, ll e){
	seg[id] = e - s;
	if(e - s == 1) return;
	ll mid = (s + e) >> 1;
	bld(lc, s, mid);
	bld(rc, mid, e);
	return;
}
void upd(ll id, ll s, ll e, ll l, ll r){
	if(seg[id] == 0 || r <= s || e <= l) return;
	if(l <= s && e <= r){
		seg[id] = 0;
		return;
	}
	ll mid = (s + e) >> 1;
	upd(lc, s, mid, l, r);
	upd(rc, mid, e, l, r);
	seg[id] = seg[lc] + seg[rc];
	return;
}
ll get(ll id, ll s, ll e, ll x){
	if(seg[id] < x) return e;
	if(e - s == 1) return s;
	ll mid = (s + e) >> 1;
	if(seg[lc] < x) return get(rc, mid, e, x - seg[lc]);
	return get(lc, s, mid, x);
}
ll dp[maxn], ok[maxn], l[maxn], r[maxn], b[maxn];
vector<ll> g[maxn];
void dfs(ll v){
	dp[v] += ok[v];
	for(ll u : g[v]){
		dp[u] += dp[v];
		dfs(u);
	}
	return;
}

int GetBestPosition(int n, int c, int x, int *a, int *s, int *e){
	bld(1, 0, n);
	set<ll> st, ss;
	for(ll i = 0; i < n; i++){
		st.insert(i);
		b[i] = i;
	}
	for(ll i = 0; i < n - 1; i++){
		if(a[i] > x) ss.insert(i);
	}
	ss.insert(n);
	for(ll i = 0; i < c; i++){
		l[n + i] = get(1, 0, n, s[i] + 1);
		r[n + i] = get(1, 0, n, e[i] + 2);
		upd(1, 0, n, l[n + i] + 1, r[n + i]);
		auto it = st.lower_bound(l[n + i]);
		while(it != st.end() && *it < r[n + i]){
			g[n + i].pb(b[*it]);
			it = st.erase(it);
		}
		b[l[n + i]] = n + i;
		st.insert(l[n + i]);
		if(*ss.lower_bound(l[n + i]) >= r[n + i] - 1) ok[n + i] = 1;
	}
	dfs(n + c - 1);
	ll ans = 0;
	for(ll i = 0; i < n; i++){
		if(dp[i] > dp[ans]) ans = i;
	}
	return ans;
}

/*int main(){
    fast_io;
    
    int n, c, x, a[100], s[100], e[100];
    cin >> n >> c >> x;
    for(ll i = 0; i < n - 1; i++){
    	cin >> a[i];
	}
	for(ll i = 0; i < c; i++){
		cin >> s[i] >> e[i];
	}
	cout << GetBestPosition(n, c, x, a, s, e);
 
    return 0;
}*/

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