제출 #287172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
287172		Saboon	Teams (IOI15_teams)	C++14	77 / 100	3219 ms	96764 KiB

teams

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

const int maxn = 5e5 + 10;
const int SQRT = 2000;

int n;
vector<int> fex[maxn], fen[maxn];

void addinit(int x, int y){
	for (; x <= n; x += x & -x)
		fex[x].push_back(y);
}

void add(int x, int y){
	for (int idx = x; idx <= n; idx += idx & -idx){
		int idy = lower_bound(fex[idx].begin(),fex[idx].end(),y)-fex[idx].begin()+1;
		for (; idy <= fex[idx].size(); idy += idy & -idy)
			fen[idx][idy] ++;
	}
}

int get(int x, int y){
	int ret = 0;
	for (; x; x -= x & -x){
		int idy = upper_bound(fex[x].begin(),fex[x].end(),y)-fex[x].begin();
		for (;idy; idy -= idy & -idy)
			ret += fen[x][idy];
	}
	return ret;
}

int get(int x, int l, int r){
	return get(x, r) - get(x, l-1);
}

void init(int N, int A[], int B[]){
	n = N;
	for (int i = 0; i < n; i++)
		addinit(A[i],B[i]);
	for (int i = 1; i <= n; i++){
		sort(fex[i].begin(), fex[i].end());
		fex[i].resize(unique(fex[i].begin(),fex[i].end())-fex[i].begin());
		fen[i].resize(fex[i].size()+1);
	}
	for (int i = 0; i < n; i++)
		add(A[i],B[i]);
}

int up[SQRT], bup[SQRT];

int can(int m, int k[]){
	sort(k,k+m);
	long long sum = 0;
	for (int i = 0; i < m; i++)
		sum += k[i];
	if (sum > n)
		return false;
	int idx = 0, cnt = 0;
	for (int i = 0; i < m; i++){
		cnt ++;
		if (i == m-1 or k[i] != k[i+1]){
			up[idx] = k[i], bup[idx] = cnt*k[i];
			cnt = 0, idx++;
			continue;
		}
	}
	int CommonUse = 0;
	up[idx] = n+1;
	for (int i = 0; i < idx; i++){
		int me = get(up[i], up[i], up[i+1]-1);
		int LastUse = 0;
		if (i > 0)
			LastUse = get(up[i-1], up[i], up[i+1]-1);
		LastUse = min(CommonUse, LastUse);
		CommonUse -= LastUse;
		me -= LastUse;
		bup[i] -= me;
		if (bup[i] > 0){
			int T = get(up[i], up[i+1], n);
			T -= CommonUse;
			if (T < bup[i])
				return false;
			CommonUse += bup[i];
		}
	}
	return true;
}

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

teams.cpp: In function 'void add(int, int)':
teams.cpp:18:76: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   18 |   int idy = lower_bound(fex[idx].begin(),fex[idx].end(),y)-fex[idx].begin()+1;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:19:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   for (; idy <= fex[idx].size(); idy += idy & -idy)
      |          ~~~~^~~~~~~~~~~~~~~~~~
teams.cpp: In function 'int get(int, int)':
teams.cpp:27:55: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   27 |   int idy = upper_bound(fex[x].begin(),fex[x].end(),y)-fex[x].begin();
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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