Submission #624936

#	Time	Username	Problem	Language	Result	Execution time	Memory
624936		penguinhacker	Jousting tournament (IOI12_tournament)	C++17	0 / 100	66 ms	19400 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5, INF=1e9;
int n, m, ft[mxN], prv[mxN], id[mxN], anc[2*mxN][17], st[mxN][17];
ar<int, 2> seg[2*mxN];

void upd(int i, int x) {
	for (++i; i<=n; i+=i&-i)
		ft[i]+=x;
}

int qry(int k) { // kth 1?
	int x=0;
	for (int i=16; ~i; --i)
		if (x+(1<<i)<=n&&ft[x+(1<<i)]<k)
			k-=ft[x+=1<<i];
	return x;
}

int find(int i) {
	return i^prv[i]?prv[i]=find(prv[i]):i;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	n=N, m=C;
	for (int i=0; i<n; ++i) {
		upd(i, 1);
		prv[i]=id[i]=i;
		seg[i]={i, i};
	}
	//for (int i=0; i<=n; ++i)
	//	cout << qry(i) << " ";
	memset(anc, -1, sizeof(anc));
	for (int i=0; i<m; ++i) {
		int x=qry(E[i]+1);
		cout << x << endl;
		assert(x==prv[x]);
		seg[i+n]={INF, -INF};
		for (int j=0; j<E[i]-S[i]; ++j) {
			anc[id[x]][0]=i+n;
			seg[i+n][0]=min(seg[i+n][0], seg[id[x]][0]);
			seg[i+n][1]=max(seg[i+n][1], seg[id[x]][1]);
			upd(x, -1);
			x=find(prv[x]=x-1);
		}
		anc[id[x]][0]=i+n;
		seg[i+n][0]=min(seg[i+n][0], seg[id[x]][0]);
		seg[i+n][1]=max(seg[i+n][1], seg[id[x]][1]);
		id[x]=i+n;
	}
	for (int i=n+m-2; ~i; --i)
		for (int j=1; ~anc[i][j-1]; ++j)
			anc[i][j]=anc[anc[i][j-1]][j-1];
	for (int i=0; i<n-1; ++i)
		st[i][0]=K[i];
	for (int j=1; (1<<j)<=n-1; ++j)
		for (int i=0; i+(1<<j)-1<n-1; ++i)
			st[i][j]=max(st[i][j-1], st[i+(1<<j-1)][j-1]);
	ar<int, 2> ans={-1, -1};
	for (int i=0; i<n; ++i) {
		int x=i;
		int cur=0;
		for (int j=16; ~j; --j) {
			int nxt=anc[x][j];
			if (nxt==-1)
				continue;
			int l=seg[nxt][0], r=seg[nxt][1]-1;
			int k=31-__builtin_clz(r-l+1);
			if (max(st[l][k], st[r-(1<<k)+1][k])<R) {
				x=nxt;
				cur+=1<<j;
			}
		}
		if (cur>ans[0])
			ans={cur, i};
	}
	return ans[1];
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:62:39: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   62 |    st[i][j]=max(st[i][j-1], st[i+(1<<j-1)][j-1]);
      |                                      ~^~

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