Submission #395802

#	Time	Username	Problem	Language	Result	Execution time	Memory
395802		bigg	Teams (IOI15_teams)	C++14	100 / 100	1741 ms	280472 KiB

teams

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

// #define esq(x) x << 1 
// #define dir(x) (x<<1) | 1
#define mid(x,y,t) ((x+y)>>1) + t
#define pb push_back
#define fi first
#define se second

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

const int MAXN = 5e5 + 10;

vector<int> seg, esq, dir;
int roots[MAXN];
pii ints[MAXN];
int tot;

int create(){
	seg.pb(0);
	esq.pb(0);
	dir.pb(0);
	return seg.size() - 1;
}

int copy(int node){
	seg.pb(seg[node]);
	esq.pb(esq[node]);
	dir.pb(dir[node]);
	return seg.size() - 1;
}

int update(int node, int x, int y, int id, int val){
	

	if(x > id || y < id) return node;
	int nn = copy(node);
	if(x == y){
		seg[nn] = seg[node] + val;
		return nn;
	}
	int aux = update(esq[node], x, mid(x,y,0), id, val);
	esq[nn] = aux;
	aux = update(dir[node], mid(x,y,1),  y, id, val);
	dir[nn] = aux;
	seg[nn] = seg[dir[nn]] + seg[esq[nn]];
	//("%d %d \n", nn,  seg[nn]);
	return nn;

}

int copyint(int node1, int node2, int x, int y, int l, int r){
	
	if(x > r || y < l) return node1;
	int nn = copy(node2);
	if(x >= l && y <= r) return node2;
	
	int aux = copyint(esq[node1], esq[node2], x, mid(x,y,0), l, r);
	esq[nn] = aux;
	aux = copyint(dir[node1], dir[node2], mid(x,y,1), y, l, r );
	dir[nn] = aux;
	seg[nn] = seg[esq[nn]] + seg[dir[nn]];
	return nn;
}

pii bb(int node1, int node2, int x, int y, int l, int r, int val){
	//("%d %d %d %d\n", l, r, x, y);
	if(x > r|| y  < l) return {y+1,0};
	if(x >= l && y <= r && seg[node1]-seg[node2] < val) return{y+1, seg[node1] - seg[node2]};
	if(x == y) return {x,0};
	pii aux = bb(esq[node1], esq[node2], x, mid(x,y,0), l, r, val);
	if(aux.fi <= mid(x,y,0)) return aux;
	pii aux2 = bb(dir[node1], dir[node2], mid(x,y,1), y, l, r, val-aux.second);
	return {aux2.first, aux2.second + aux.second};

}

int n;
void init(int N, int A[], int B[]) {
	n = N;
	vector<pii> v;
	for(int i = 0; i < n; i++)v.pb({A[i], B[i]});
	
	sort(v.begin(), v.end());
	create();
	//("%d\n", roots[0]);
	for(int i = 0; i < n; i++) ints[i+1] = v[i];
	int it2 = 1;
	for(int i = 1; i <= n; i++){
		roots[i] = roots[i-1];
		while(ints[it2].fi == i){
			int aux  = update(roots[i], 1, n, ints[it2++].se, 1);
			roots[i] = aux;
		}
	}
}

int can(int m, int K[]) {
	sort(K, K + m);
	//("B\n");
	int last = 0;
	for(int i = 0; i < m; i++){
		int r = K[i];
		pii aux = bb(roots[r], last, 1, n, r, n, r);
		//("A %d %d\n", r - aux.se, aux.fi);
		if(aux.fi == n + 1) return 0;
		//("%d\n", i);
		last = copyint(last, roots[r], 1, n, 1, aux.fi-1);
		last = update(last, 1, n , aux.fi, r - aux.se);
		
	}

	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int create()':
teams.cpp:26:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   26 |  return seg.size() - 1;
      |         ~~~~~~~~~~~^~~
teams.cpp: In function 'int copy(int)':
teams.cpp:33:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   33 |  return seg.size() - 1;
      |         ~~~~~~~~~~~^~~

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