Submission #561477

#	Time	Username	Problem	Language	Result	Execution time	Memory
561477		peuch	Jousting tournament (IOI12_tournament)	C++17	0 / 100	20 ms	3028 KiB

tournament

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 10;

int bit[MAXN];
int n, c, r;
int *k, *s, *e;

vector<int> ini, fim;

struct event{
	int l, r, id;
	event(int _l, int _r, int _id){
		l = _l;
		r = _r;
		id = _id;
	}
	bool operator < (event x) const{
		if(r != x.r) return r < x.r;
		return id < x.id;
	}
};
vector<event> line;

void upd(int id, int val);
int qry(int id);

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	n = N, c = C, r = R, k = K, s = S, e = E;
	ini = vector<int> (n), fim = vector<int>(n);
	// Reindex fights
	for(int i = 0; i < c; i++){
		int aux = e[i] - s[i];
		s[i] += qry(s[i] - 1);
		e[i] += qry(e[i]);
		upd(s[i], aux);
	}

	// Create intervals when fighter start at i
	for(int val = 0, i = 0; i < n; i++){
		ini[i] = val;
		if(i != n - 1 && k[i] > r) val = i + 1;
	}
	for(int val = n - 1, i = n - 1; i >= 0; i--){
		if(i != n - 1 && k[i] > r) val = i;
		fim[i] = val;
	}

	// Create LineSweep events
	for(int i = 0; i < c; i++)
		line.push_back(event(s[i], e[i], -1));
	for(int i = 0; i < n; i++)
		line.push_back(event(ini[i], fim[i], i));
	sort(line.begin(), line.end());
	
	memset(bit, 0, sizeof(bit));
	
	int ans = -1, idx = 0;
	for(int i = 0; i < line.size(); i++){
		int esq = line[i].l;
		int dir = line[i].r;
		int id = line[i].id;
		if(id == -1) upd(esq, 1);
		else{
			int auxAns = qry(id) - qry(esq - 1);
			if(auxAns > ans) idx = id, ans = auxAns;
			if(ans == auxAns) idx = min(id, idx);
		}
	}
	
  return idx;
}


void upd(int id, int val){
	id++;
	while(id < MAXN){
		bit[id] += val;
	 	id += (-id)&id;
	}
}

int qry(int id){
	id++;
	int ret = 0;
	while(id > 0){
		ret += bit[id];
		id -= (-id)&id;
	}
	return ret;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i = 0; i < line.size(); i++){
      |                 ~~^~~~~~~~~~~~~
tournament.cpp:63:7: warning: unused variable 'dir' [-Wunused-variable]
   63 |   int dir = line[i].r;
      |       ^~~

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