Submission #561496

#	Time	Username	Problem	Language	Result	Execution time	Memory
561496		peuch	Jousting tournament (IOI12_tournament)	C++17	100 / 100	267 ms	32644 KiB

tournament

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int MAXN = 1e5 + 10;

int bit1[MAXN], bit2[MAXN];
int n, c, r;

vector<int> ini, fim;

void upd1(int id, int val);
int qry1(int id);
void upd2(int id, int val);
int qry2(int id);

vector<int> seg, e, d;
vector<int> bank;
 
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;

int copia(int node);
int update(int pos, int ini, int fim, int id, int val);
int query(int pos, int ini, int fim, int p, int q);

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	copia(-1);
	copia(-1);
	n = N, c = C, r = R;
	ini = fim = bank = vector<int> (n);
	
	// Reindex fights
	
	ordered_set fila1, fila2;
	for(int i = 0; i < n; i++)
		fila1.insert(i), fila2.insert(i);
	for(int i = 0; i < c; i++){
		int auxA = S[i], auxB = E[i];
		S[i] = *fila1.find_by_order(S[i]);
		E[i] = *fila2.find_by_order(E[i]);
		for(int j = auxB; j > auxA; j--)
			fila1.erase(fila1.find_by_order(j));
		for(int j = auxB - 1; j >= auxA; j--)
			fila2.erase(fila2.find_by_order(j));
	}
	
	// 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());
	
	// Answer linesweep queries
	bank[0] = 1;
	int ans = -1, idx = 0, last = 0;
	for(int i = 0; i < line.size(); i++){
		int esq = line[i].l;
		int dir = line[i].r;
		int id = line[i].id;
//		printf("Event: %d %d %d\n", esq, dir, id);
		while(last != dir){
			last++;
			bank[last] = bank[last - 1];
		}
		if(id == -1) bank[dir] = update(bank[dir], 0, n - 1, esq, 1);
		else{
			int auxAns = query(bank[dir], 0, n - 1, esq, id);
			if(id != 0) auxAns -= query(bank[id - 1], 0, n - 1, esq, id);
//			printf("Ans = %d at %d (%d %d %d)\n", auxAns, id, esq, id, dir);
			if(auxAns > ans) idx = id, ans = auxAns;
			if(ans == auxAns) idx = min(id, idx);
		}
//		printf("%d\n", bank[dir]);
//		for(int i = 0; i < n; i++)
//			printf("%d ", query(bank[dir], 0, n - 1, i, i));
//		printf("\n");
	}
	
//	printf("%d\n", ans);
  return idx;
}


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

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

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

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

int copia(int node){
	if(node == -1){
		seg.push_back(0);
		e.push_back(0);
		d.push_back(0);
	}
	else{
		seg.push_back(seg[node]);
		e.push_back(e[node]);
		d.push_back(d[node]);
	} 
	return seg.size() - 1;
}

int update(int pos, int ini, int fim, int id, int val){
	if(ini > id || fim < id) return pos;
	int newNode = copia(pos);
//	printf("Updating: (%d -> %d) %d %d %d %d\n", pos, newNode, ini, fim, id, val);
	if(ini == fim){
		seg[newNode] += val;
		return newNode;
	}
	int mid = (ini + fim) >> 1;
	int aux;
	aux = update(e[pos], ini, mid, id, val);
	e[newNode] = aux;
//	printf("(%d %d %d %d %d) Returned %d\n", e[pos], ini, mid, id, val, e[newNode]);
	aux = update(d[pos], mid + 1, fim, id, val);
	d[newNode] = aux;
//	printf("(%d %d %d %d %d) Returned %d\n", d[pos], mid + 1, fim, id, val, d[newNode]);
	seg[newNode] = seg[e[newNode]] + seg[d[newNode]];
//	printf("seg[%d -> (%d %d)] = %d\n", newNode, e[newNode], d[newNode], seg[newNode]);
	return newNode;
}

int query(int pos, int ini, int fim, int p, int q){
	if(pos <= 0) return 0;
	if(ini > q || fim < p) return 0;
	if(ini >= p && fim <= q) return seg[pos];
	int mid = (ini + fim) >> 1;
	return query(e[pos], ini, mid, p, q) + query(d[pos], mid + 1, fim, p, q);
}

Compilation message (stderr)

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

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