Submission #386689

#	Time	Username	Problem	Language	Result	Execution time	Memory
386689		alireza_kaviani	Teams (IOI15_teams)	C++11	0 / 100	916 ms	158688 KiB

teams

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

const int MAXN = 5e5 + 10;
const int LOG = 22;

int nodeInd , 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);
}

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(B[i] , root[i]);
		}
	}
}

int can(int M, int K[]) {
	int cur = 0;
	for(int i = 0 ; i < M ; i++){
		cur += K[i];
//		cout << cur << endl;
		if(get(K[i] , MAXN , root[K[i]]) < cur)	return 0;
		cur -= get(K[i] , (i + 1 < M ? K[i + 1] : MAXN) , root[K[i]]);
		cur = max(cur , 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 'void init(int, int*, int*)':
teams.cpp:46:11: warning: unused variable 'j' [-Wunused-variable]
   46 |   for(int j : vec[i]){
      |           ^

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