oj.uz

Submission #348401

# Submission time Handle Problem Language Result Execution time Memory
348401 2021-01-14T23:28:49 Z dennisstar Jousting tournament (IOI12_tournament) C++17
100 / 100
 112 ms 6764 KB 
#include <bits/stdc++.h>
using namespace std;


const int MX = 1e5 + 5, SMX = 1<<18;

int N, C, R;
int K[MX], S[MX], E[MX], A[MX];

struct {
	int st[SMX];
	void init(int i, int s, int e) {
		if (s==e) { st[i]=1; return ; }
		int m=(s+e)/2;
		init(i*2, s, m);
		init(i*2+1, m+1, e);
		st[i]=st[i*2]+st[i*2+1];
	}
	int find(int i, int s, int e, int t) {
		if (st[i]<t) return e+1;
		if (s==e) return s;
		int m=(s+e)/2;
		if (st[i*2]>=t) return find(i*2, s, m, t);
		else return find(i*2+1, m+1, e, t-st[i*2]);
	}
	void upd(int i, int s, int e, int l, int r) {
		if (e<l||r<s||!st[i]) return ;
		if (l<=s&&e<=r) { st[i]=0; return ; }
		int m=(s+e)/2;
		upd(i*2, s, m, l, r);
		upd(i*2+1, m+1, e, l, r);
		st[i]=st[i*2]+st[i*2+1];
	}
}S1;

struct {
	int st[SMX];
	void init(int i, int s, int e) {
		if (s==e) { st[i]=K[s]; return ; }
		int m=(s+e)/2;
		init(i*2, s, m);
		init(i*2+1, m+1, e);
		st[i]=max(st[i*2], st[i*2+1]);
	}
	int get(int i, int s, int e, int l, int r) {
		if (e<l||r<s) return 0;
		if (l<=s&&e<=r) return st[i];
		int m=(s+e)/2;
		return max(get(i*2, s, m, l, r), get(i*2+1, m+1, e, l, r));
	}
}S2;

int sol() {
	S1.init(1, 1, N);
	S2.init(1, 1, N-1);

	for (int i=1; i<=C; i++) {
		int l=S1.find(1, 1, N, S[i]), r=S1.find(1, 1, N, E[i]+1)-1;
		S1.upd(1, 1, N, l+1, r);
		if (S2.get(1, 1, N-1, l, r-1)<R) A[l]++, A[r+1]--;
	}

	int mx=0, r=1;
	for (int i=1; i<=N; i++) {
		A[i]+=A[i-1];
		if (A[i]>mx) mx=A[i], r=i;
	}
	return r-1;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	::N=N, ::C=C, ::R=R+1;
	for (int i=1; i<=N-1; i++) ::K[i]=K[i-1]+1;
	for (int i=1; i<=C; i++) ::S[i]=S[i-1]+1, ::E[i]=E[i-1]+1;
	return sol();
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 5 ms 620 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 5 ms 620 KB Output is correct
5 Correct 5 ms 620 KB Output is correct
6 Correct 4 ms 620 KB Output is correct
7 Correct 5 ms 620 KB Output is correct
8 Correct 5 ms 620 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 5 ms 620 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2412 KB Output is correct
2 Correct 112 ms 5100 KB Output is correct
3 Correct 22 ms 4332 KB Output is correct
4 Correct 107 ms 6764 KB Output is correct
5 Correct 106 ms 6636 KB Output is correct
6 Correct 78 ms 5740 KB Output is correct
7 Correct 111 ms 6764 KB Output is correct
8 Correct 109 ms 6764 KB Output is correct
9 Correct 16 ms 4204 KB Output is correct
10 Correct 22 ms 4204 KB Output is correct