Submission #395808

#	Time	Username	Problem	Language	Result	Execution time	Memory
395808		peuch	Teams (IOI15_teams)	C++17	0 / 100	829 ms	141380 KiB

teams

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

const int MAXN = 5e5 + 10;

int n;
pair<int, int> v[MAXN];
int bank[MAXN];

int m;
int k[MAXN];

vector<int> seg, e, d;

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

void init(int N, int A[], int B[]) {
	n = N;
	create();
	bank[0] = create();
	for(int i = 0; i < n; i++)
		v[i + 1] = make_pair(A[i], B[i]);
	sort(v + 1, v + 1 + n);
	for(int i = 1; i <= n; i++)
		bank[i] = update(bank[i - 1], 1, n, v[i].second);
}

int can(int M, int K[]) {
	m = M;
	for(int i = 0; i < m; i++)
		k[i + 1] = K[i];
	sort(k + 1, k + 1 + m);
	
	stack<pair<int, pair<int, int> > > pilha;
	pilha.push(make_pair(n + 1, make_pair(0, 0)));
	
	
	for(int i = 1; i <= m; i++){
		int it = upper_bound(v + 1, v + 1 + n, make_pair(k[i], MAXN)) - v - 1;
		if(it < 0) return 0;
		int hmin = k[i];
		int hmax = k[i];
		int sum = 0;
		while(pilha.top().first < hmin) pilha.pop();
		
		while(!pilha.empty()){
			hmax = pilha.top().first;
			int it2 = pilha.top().second.first;
			sum += pilha.top().second.second;
			int diff = query(bank[it], 1, n, hmin + 1, hmax) - query(bank[it2], 1, n, hmin + 1, hmax);
			if(diff + sum >= k[i]){
				int ini = hmin, fim = hmax;
				while(ini != ini){
					int mid = (ini + fim) >> 1;
					int diff = query(bank[it], 1, n, hmin + 1, mid) - query(bank[it2], 1, n, hmin + 1, mid);
					if(ini == fim - 1) mid = fim;
					if(sum + diff >= k[i]) ini = mid;
					else fim = mid - 1;
				}
				pilha.push(make_pair(ini, make_pair(it, sum - k[i])));
				break;
			}
			else sum += diff, hmin = hmax, pilha.pop();
		}
		if(pilha.empty()) return 0;
	}
	
	return 1;
}

int create(){
	seg.push_back(0);
	e.push_back(0);
	d.push_back(0);
	return seg.size() - 1;
}

int copia(int pos){
	seg.push_back(seg[pos]);
	e.push_back(e[pos]);
	d.push_back(d[pos]);
	return seg.size() - 1;
}

int update(int pos, int ini, int fim, int id){
	if(ini > id || fim < id) return pos;
	int newNode = copia(pos);
	if(ini == fim){
		seg[newNode]++;
		return newNode;
	}
	int mid = (ini + fim) >> 1;
	int aux = update(e[pos], ini, mid, id);
	e[newNode] = aux;
	aux = update(d[pos], mid + 1, fim, id);
	d[newNode] = aux;
	seg[newNode] = seg[e[newNode]] + seg[d[newNode]];
	return newNode;
}

int query(int pos, int ini, int fim, int p, int q){
	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)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:43:69: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   43 |   int it = upper_bound(v + 1, v + 1 + n, make_pair(k[i], MAXN)) - v - 1;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:57:15: warning: self-comparison always evaluates to false [-Wtautological-compare]
   57 |     while(ini != ini){
      |           ~~~ ^~ ~~~
teams.cpp:59:10: warning: declaration of 'diff' shadows a previous local [-Wshadow]
   59 |      int diff = query(bank[it], 1, n, hmin + 1, mid) - query(bank[it2], 1, n, hmin + 1, mid);
      |          ^~~~
teams.cpp:54:8: note: shadowed declaration is here
   54 |    int diff = query(bank[it], 1, n, hmin + 1, hmax) - query(bank[it2], 1, n, hmin + 1, hmax);
      |        ^~~~
teams.cpp: In function 'int create()':
teams.cpp:79:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   79 |  return seg.size() - 1;
      |         ~~~~~~~~~~~^~~
teams.cpp: In function 'int copia(int)':
teams.cpp:86:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   86 |  return seg.size() - 1;
      |         ~~~~~~~~~~~^~~

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23