Submission #386804

#	Time	Username	Problem	Language	Result	Execution time	Memory
386804		alireza_kaviani	Teams (IOI15_teams)	C++11	100 / 100	1541 ms	355164 KiB

teams

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

const int MAXN = 2e6 + 10;
const int LOG = 22;

int nodeInd , tot , seg[MAXN * LOG] , lc[MAXN * LOG] , rc[MAXN * LOG] , root[MAXN];
vector<int> vec[MAXN];

void build(int id , int l = 0 , int r = MAXN){
	if(r - l == 1)	return;
	lc[id] = ++nodeInd;
	rc[id] = ++nodeInd;
	int mid = l + r >> 1;
	build(lc[id] , l , mid);
	build(rc[id] , mid , r);
}

int add(int x , int cid , int l = 0 , int r = MAXN){
	int id = ++nodeInd;
	seg[id] = seg[cid]; lc[id] = lc[cid]; rc[id] = rc[cid];
	if(r - l == 1){
		seg[id]++;
		return id;
	}
	int mid = l + r >> 1;
	if(x < mid)	lc[id] = add(x , lc[id] , l , mid);
	else	rc[id] = add(x , rc[id] , mid , r);
	seg[id] = seg[lc[id]] + seg[rc[id]];
	return id;
}

int get(int ql , int qr , int id , int l = 0 , int r = MAXN){
	if(qr <= l || r <= ql)	return 0;
	if(ql <= l && r <= qr)	return seg[id];
	int mid = l + r >> 1;
	return get(ql , qr , lc[id] , l , mid) + get(ql , qr , rc[id] , mid , r);
}

int solve(int x , int val , int cid , int id2 , int l = 0 , int r = MAXN){
	if(r <= x || val == tot)	return cid;
	int id1 = ++nodeInd;
	seg[id1] = seg[cid]; lc[id1] = lc[cid]; rc[id1] = rc[cid];
	if(x <= l && (seg[id2] - seg[id1] + tot <= val || r - l == 1)){
		int cnt = min(val - tot , seg[id2] - seg[id1]); tot += cnt;
//		cout << x << ' ' << val << ' ' << cnt << ' ' << seg[id1] << ' ' << seg[id2] << ' ' << l << ' ' << r << endl;
		seg[id1] += cnt; lc[id1] = lc[id2]; rc[id1] = rc[id2];
		return id1;
	}
	int mid = l + r >> 1;
	lc[id1] = solve(x , val , lc[id1] , lc[id2] , l , mid);
	rc[id1] = solve(x , val , rc[id1] , rc[id2] , mid , r);
	seg[id1] = seg[lc[id1]] + seg[rc[id1]];
	return id1;
}

void init(int N, int A[], int B[]) {
	for(int i = 0 ; i < N ; i++)	vec[A[i]].push_back(B[i]);
	build(0);
	for(int i = 1 ; i <= N ; i++){
		root[i] = root[i - 1];
		for(int j : vec[i]){
			root[i] = add(j , root[i]);
		}
	}
}

int can(int M, int K[]) {
	int cur = 0;
	sort(K , K + M);
	for(int i = 0 ; i < M ; i++){
		tot = 0 , cur = solve(K[i] , K[i] , cur , root[K[i]]);
//		cout << tot << endl;
		if(tot < K[i])	return 0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void build(int, int, int)':
teams.cpp:15:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |  int mid = l + r >> 1;
      |            ~~^~~
teams.cpp: In function 'int add(int, int, int, int)':
teams.cpp:27:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |  int mid = l + r >> 1;
      |            ~~^~~
teams.cpp: In function 'int get(int, int, int, int, int)':
teams.cpp:37:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |  int mid = l + r >> 1;
      |            ~~^~~
teams.cpp: In function 'int solve(int, int, int, int, int, int)':
teams.cpp:51:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |  int mid = l + r >> 1;
      |            ~~^~~

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