Submission #274691

#	Time	Username	Problem	Language	Result	Execution time	Memory
274691		shayan_p	Jousting tournament (IOI12_tournament)	C++14	100 / 100	82 ms	25464 KiB

tournament

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 2e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

int fn[maxn];
void add(int pos, int x){
    for(pos+=3; pos < maxn; pos+= (pos & -pos))
	fn[pos]+= x;   
}
int fnd(int k){
    int ans = 0;
    for(int i = 19; i >= 0; i--){
	if(ans + (1<<i) >= maxn)
	    continue;
	if(fn[ans+(1<<i)] <= k)
	    ans+= 1<<i, k-= fn[ans];
    }
    return ans+1-3;
}
int vert[maxn];
int dp1[maxn], dp3[maxn];
pii ans[maxn], dp2[maxn];

vector<int> v[maxn];
int a[maxn], n;

void dfs(int u){
    if(u < n){
	if(u == 0)
	    dp1[u] = 0;
	else
	    dp1[u] = a[u-1];
	if(u == n-1)
	    dp3[u] = 0;
	else
	    dp3[u] = a[u];
	ans[u] = dp2[u] = {0, -u};
	return;
    }
    dp1[u] = dp3[u] = 0;
    dp2[u] = ans[u] = {-1, -1};
    
    int L = -1, R = -1;
    for(int y : v[u]){// are sorted
	dfs(y);
	dp1[u]|= dp1[y];
	dp3[u]|= dp3[y];
	ans[u] = max(ans[u], ans[y]);

	if(dp3[y] && R == -1)
	    R = y;
	if(dp1[y])
	    L = y;
    }    
    bool start = (L == -1);
    for(int y : v[u]){
	start|= L == y;
	if(start && dp2[y].F != -1)
	    dp2[u] = max(dp2[u], (pii){dp2[y].F + 1, dp2[y].S} );
	if(R == y)
	    break;
    }
    ans[u] = max(ans[u], dp2[u]);
}

int ITER = 0;

int GetBestPosition(int n, int q, int r, int *a, int *L, int *R){
    assert(++ITER <= 1);
    
    memset(fn, 0, sizeof fn); // tl?
    
    ::n = n;
    for(int i = 0; i < n-1; i++){
	a[i] = r < a[i];
	::a[i] = a[i];
    }
    for(int i = 0; i < n; i++){
	vert[i] = i;
	add(i, 1);
    }
    for(int i = 0; i < n+q; i++){
	v[i].clear();
    }
    for(int i = 0; i < q; i++){
	int cnt = R[i] - L[i], l = fnd(L[i]);
	v[i+n].PB(vert[l]);
	vert[l] = i+n;
	for(int w = 0; w < cnt; w++){
	    int pos = fnd(L[i]+1);
	    v[i+n].PB(vert[pos]);
	    add(pos, -1);
	}
    }
    dfs(n+q-1);
    return -ans[n+q-1].S;
}

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