Submission #121872

#	Time	Username	Problem	Language	Result	Execution time	Memory
121872		nvmdava	Teams (IOI15_teams)	C++17	0 / 100	3012 ms	524288 KiB

teams

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

int n;
struct Y{
	Y *l = NULL, *r = NULL;
	int val = 0;
};
struct X{
	X *l = NULL, *r = NULL;
	Y *y = new Y();
} *root = new X();

void updateY(Y* y, int l, int r, int loc){
	if(l == r){
		y -> val++;
		return;
	}
	int m = (l + r) >> 1;
	if(m >= loc){
		if(y -> l == NULL) y -> l = new Y();
		updateY( y -> l, l, m, loc);
	} else {
		if(y -> r == NULL) y -> r = new Y();
		updateY( y -> r, m + 1, r, loc);
	}
	y -> val = (y -> l == NULL ? 0 : y -> l -> val) + (y -> r == NULL ? 0 : y -> r -> val);
}

void updateX(X* x, int l, int r, int a, int b){
	updateY(x -> y, 0, 500000, b);
	if(l == r) return;
	int m = (l + r) >> 1;
	if(m >= a){
		if(x -> l == NULL) x -> l = new X();
		updateX( x -> l, l, m, a, b);
	} else {
		if(x -> r == NULL) x -> r = new X();
		updateX( x -> r, m + 1, r, a, b);
	}
}

int queryY(Y* y, int l, int r, int L, int R){
	if(l > R || r < L) return 0;
	if(l >= L && r <= R) return y -> val;
	int m = (l + r) >> 1;
	return (y -> l == NULL ? 0 : queryY(y -> l, l, m, L, R)) + (y -> r == NULL ? 0 : queryY(y -> r, m + 1, r, L, R));
}

int queryX(X* x, int l, int r, int L, int R, int D, int U){
	
	if(l > R || r < L) return 0;
	if(l >= L && r <= R) return queryY(x -> y, 0, 500000, D, U);
	int m = (l + r) >> 1;
	return (x -> l == NULL ? 0 : queryX(x -> l, l, m, L, R, D, U)) + (x -> r == NULL ? 0 : queryX(x -> r, m + 1, r, L, R, D, U));
}


void init(int N, int A[], int B[]){
	for(int i = 0; i < N; i++){
		updateX(root, 0, 500000, A[i], B[i]);
	}
}

int can(int M, int K[]) {
	sort(K + 0, K + M);
	
	int it = 0, ps = 0;
	
	for(int i = 0; i < M; i++){
		ps += K[i];
		if(queryX(root, 0, 500000, 0, K[i], K[i], 500000) < ps) return 0;
		if(i != M - 1){
			if(K[i] != K[i + 1])
				ps -= queryX(root, 0, 500000, 0, K[i], K[i], K[i + 1] - 1);
		}
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:69:6: warning: unused variable 'it' [-Wunused-variable]
  int it = 0, ps = 0;
      ^~

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