Submission #287347

#	Time	Username	Problem	Language	Result	Execution time	Memory
287347		Saboon	Teams (IOI15_teams)	C++17	100 / 100	3354 ms	104148 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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 < maxn; x += x & -x)
		fex[x].push_back(y);
}

void add(int x, int y){
	for (int idx = x; idx < maxn; 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 < maxn; 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 Uses[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 0;
	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++;
		}
	}
	int CommonUse = 0;
	up[idx] = n+1;
	for (int i = 0; i < idx; i++){
		Uses[i] = 0;
		int Marked = 0;
		for (int j = 0; j < i; j++){
			if (Uses[j] == 0)
				continue;
			int t = get(up[j], up[i], up[i+1]-1) - Marked;
			int tmp = min(t, Uses[j]);
			Marked += tmp, Uses[j] -= tmp, CommonUse -= tmp;
		}
		int me = get(up[i], up[i], up[i+1]-1) - Marked;
		bup[i] = max(0, bup[i]-me);
		int T = get(up[i], up[i+1], n) - CommonUse;
		if (T < bup[i])
			return 0;
		CommonUse += bup[i];
		Uses[i] += bup[i];
	}
	return 1;
}

Compilation message (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: 23 / 23