제출 #121882

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
121882		nvmdava	팀들 (IOI15_teams)	C++17	0 / 100	2829 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){
	y -> val++;
	if(l == r){
		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);
	}
}

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, t = 0;
	
	for(int i = 0; i < M; i++){
		ps += K[i];
		t += 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]){
				int q = queryX(root, 0, 500000, 0, K[i], K[i], K[i + 1] - 1);
				if(q > t){
					ps -= t;
					t = 0;
				} else {
					ps -= q;
					t -= q;
				}
			}
		}
	}
	return 1;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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