oj.uz

Submission #382735

# Submission time Handle Problem Language Result Execution time Memory
382735 2021-03-28T06:20:17 Z alireza_kaviani Jousting tournament (IOI12_tournament) C++11
100 / 100
 85 ms 23268 KB 
#include <bits/stdc++.h>
using namespace std;

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

#define X				first
#define Y				second
#define sep				' '

const int MAXN = (1 << 18);
const int LOG = 18;

int n , m , r , ans[MAXN] , fen[MAXN] , nxt[MAXN] , val[MAXN] , dpl[MAXN] , dpr[MAXN],fen2[MAXN];
vector<int> vec[MAXN];
vector<pair<pii , pii>> Q[MAXN];

void add(int x , int val){
	for(x++ ; x < MAXN ; x += x & -x)	fen[x] += val;
}

int get(int x){
	int ans = 0;
	for(int i = (1 << (LOG - 1)) ; i ; i >>= 1){
		if(fen[ans + i] <= x){
			ans += i;
			x -= fen[ans];
		}
	}
	return ans;
}

void update(int x , int val){
	for(x += 2 ; x < MAXN ; x += x & -x)	fen2[x] += val;
}

int query(int x){
	int ans = 0;
	for(x += 2 ; x ; x -= x & -x)	ans += fen2[x];
	return ans;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
	n = N; m = C; r = R;
	for(int i = 0 ; i < n - 1 ; i++){
		val[i] = K[i];
		nxt[i] = i + 1;
		add(i , 1);
	}
	add(n - 1 , 1);
	nxt[n - 1] = n;
	for(int i = 0 ; i < m ; i++){
		int l = S[i] , r = E[i];
		int cur = get(l) , tmp = cur;
		for(int j = 0 ; j < r - l + 1 ; j++){
			add(cur , -1);
			cur = nxt[cur];
		}
		nxt[tmp] = cur;
		add(tmp , 1);
		vec[tmp].push_back(cur - 1);
//		cout << tmp << sep << cur - 1 << endl;
	}
	//assert(fen[MAXN / 2] == 1);
	dpl[0] = -1;
	for(int i = 1 ; i < n ; i++){
		dpl[i] = dpl[i - 1];
		if(val[i - 1] > r)	dpl[i] = i - 1;
	}
	dpr[n - 1] = n - 1;
	for(int i = n - 2 ; i >= 0 ; i--){
		dpr[i] = dpr[i + 1];
		if(val[i] > r)	dpr[i] = i;
	}
	for(int i = 0 ; i < n ; i++){
		if(dpl[i] >= 0)	Q[dpl[i]].push_back({{i , -1} , {i - 1 , dpr[i]}});
		Q[i].push_back({{i , 1} , {i - 1 , dpr[i]}});
	}
	for(int i = 0 ; i < n ; i++){
//		cout << i << sep << dpl[i] << sep << dpr[i] << endl;
		for(int j : vec[i])	update(j , 1);
		for(auto &j : Q[i]){
			ans[j.X.X] += j.X.Y * (query(j.Y.Y) - query(j.Y.X));
		}
	}
	int res = 0;
	for(int i = 0 ; i < n ; i++){
		if(ans[i] > ans[res])	res = i;
	}
	return res;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12780 KB Output is correct
2 Correct 13 ms 13292 KB Output is correct
3 Correct 11 ms 13292 KB Output is correct
4 Correct 13 ms 13292 KB Output is correct
5 Correct 14 ms 13420 KB Output is correct
6 Correct 13 ms 13292 KB Output is correct
7 Correct 13 ms 13292 KB Output is correct
8 Correct 13 ms 13292 KB Output is correct
9 Correct 12 ms 13312 KB Output is correct
10 Correct 14 ms 13292 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 17772 KB Output is correct
2 Correct 85 ms 22756 KB Output is correct
3 Correct 47 ms 20444 KB Output is correct
4 Correct 83 ms 23268 KB Output is correct
5 Correct 83 ms 22756 KB Output is correct
6 Correct 80 ms 22932 KB Output is correct
7 Correct 80 ms 23140 KB Output is correct
8 Correct 82 ms 23140 KB Output is correct
9 Correct 44 ms 20844 KB Output is correct
10 Correct 51 ms 21612 KB Output is correct