Submission #546368

#	Time	Username	Problem	Language	Result	Execution time	Memory
546368		ACE_	Jousting tournament (IOI12_tournament)	C++14	0 / 100	69 ms	5444 KiB

tournament

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn], id[4 * maxn], val[4 * maxn], tree[4 * maxn];
// ID 
void upd(int u,int st, int en, int l,int r,int val) {
	if(l > en || r < st) return;
	if(st <= l && r <= en) {
		id[u] += val;
		return;
	}
	int mid = (l + r) / 2;
	upd(2 * u, st, en, l, mid, val);
	upd(2 * u + 1, st, en, mid + 1, r, val);
	
}
int get(int u,int idx, int l, int r) {
	if(l > idx || r < idx) return 0;
	if(l == r) return id[u];
	int mid = (l + r) / 2;
	return id[u] + get(2 * u, idx, l, mid) + get(2 * u + 1, idx, mid + 1, r);
}


/// MAX ELEMENT ON A SEGMENT
void build(int u,int l, int r) {
	if(l == r) {
		tree[u] = a[l];
		return;
	}
	int mid = (l + r) / 2;
	build(2 * u, l, mid); build(2 * u + 1, mid + 1, r);
	tree[u] = max(tree[2 * u], tree[2 * u + 1]);
}
int mx(int u,int st,int en, int l,int r) {
	if(l > en || r < st) return 0;
	if(st <= l && r <= en) return tree[u];
	int mid = (l + r) / 2;
	return max(mx(2 * u, st, en, l, mid), mx(2 * u + 1, st ,en ,mid + 1, r));
}


void upd(int u,int st, int en, int l, int r) {
	if(l > en || r < st) return;
	if(st <= l && r <= en) {
		val[u] ++;
		return;
	}
	int mid = (l + r) / 2;
	upd(2 * u, st, en ,l, mid); upd(2 * u + 1, st, en ,mid + 1, r);
}
int get_mx(int u,int id, int l,int r) {
	if(l > id || r < id) return 0;
	if(l == r) return val[u];
	int mid = (l + r) / 2;
	return val[u] + get_mx(2 * u, id, l, mid) + get_mx(2 * u + 1,id, mid + 1, r);
}
int GetBestPosition(int n, int C, int R, int *K, int *s, int *e) {
	set<int> ok;
	for(int i = 0; i < n - 1; i++) a[i] = K[i];
	for(int i = 1; i < n ;i++) {
		upd(1, i, n - 1, 0, n - 1, 1);
		ok.insert(i);
	}
	build(1, 0, n - 2);
	pair<int,int> ans; ans = {0, 0};
	for(int i = 0; i < C; i++) {
		int l = get(1, s[i], 0, n - 1), r = get(1, e[i], 0, n - 1);
		upd(1, s[i] + 1, n - 1, 0, n - 1, get(1, e[i] + 1, 0, n - 1) - get(1, s[i] + 1, 0, n - 1));
		if(mx(1, l, r - 1, 0, n - 2) > R) { 
			while(ok.upper_bound(l - 1) != ok.end() && *ok.upper_bound(l - 1) < r) {
				int id = *ok.upper_bound(l - 1);
				ans = max(ans, {get_mx(1, id, 0, n - 1), -id});
				ok.erase(*ok.upper_bound(l - 1));
			}
		} else upd(1, l, r, 0, n - 1);
	}
	while(ok.upper_bound(0 - 1) != ok.end()) {
		int id = *ok.upper_bound(0 - 1);
		ans = max(ans, {get_mx(1, id, 0, n - 1), -id});
		ok.erase(*ok.upper_bound(0 - 1));
	}
	return -ans.second;
}
/*
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define inbuf_len 1 << 16
#define outbuf_len 1 << 16

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E);

int main() {
  int tmp;

  /* Set input and output buffering 
  char *inbuf, *outbuf;
  inbuf = (char*) malloc(inbuf_len * sizeof(char));
  outbuf = (char*) malloc(outbuf_len * sizeof(char));
  tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
  assert(tmp == 0);
  tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
  assert(tmp == 0);

  int N, C, R;
  int *K, *S, *E;
  tmp = scanf("%d %d %d", &N, &C, &R);
  assert(tmp == 3);
  K = (int*) malloc((N-1) * sizeof(int));
  S = (int*) malloc(C * sizeof(int));
  E = (int*) malloc(C * sizeof(int));
  int i;
  for (i = 0; i < N-1; i++) {
    tmp = scanf("%d", &K[i]);
    assert(tmp == 1);
  }
  for (i = 0; i < C; i++) {
    tmp = scanf("%d %d", &S[i], &E[i]);
    assert(tmp == 2);
  }

  printf("%d\n", GetBestPosition(N, C, R, K, S, E));

  return 0;

}*/

Compilation message (stderr)

tournament.cpp:98:3: warning: "/*" within comment [-Wcomment]
   98 |   /* Set input and output buffering
      |

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