Submission #501608

#	Time	Username	Problem	Language	Result	Execution time	Memory
501608		sidon	Teams (IOI15_teams)	C++17	0 / 100	548 ms	123016 KiB

teams

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

int sV;
struct WaveletTree{
	int l, r; vector<int> p;
	WaveletTree *L, *R;
	WaveletTree() {}
	WaveletTree(int *aL, int *aR, int vL, int vR) : l(vL), r(vR) {
		if(vR - vL < 2) return;
		if(aL == aR) return;

		int m = (l + r) / 2;
		auto toL = [m](int i) { return i < m; };

		p.resize(aR-aL+1);
		for(int i = 0; aL + i != aR; i++)
			p[i+1] = toL(*(aL+i)) + p[i];

		int *aM = stable_partition(aL, aR, toL);

		L = new WaveletTree(aL, aM, l, m);
		R = new WaveletTree(aM, aR, m, r);
	}
	int query(int sL, int sR, int _sV) {
		sV = _sV; return query(sL, sR);
	}
	int query(int sL, int sR) {
		if(sL == sR || sV >= r) return 0;
		if(sV <= l) return sR - sL;

		return L->query(p[sL], p[sR]) + R->query(sL-p[sL], sR-p[sR]);
	}
}* wt;

int N, sA[1<<19];

void init(int n, int A[], int B[]) {
	int s[N=n], sB[N];
	iota(s, s+n, 0);
	sort(s, s+n, [&](int &i, int &j) {
		return A[i] < A[j];
	});
	for(int i = 0; i < N; i++) {
		sA[i] = A[s[i]];
		sB[i] = B[s[i]];
	}
	wt = new WaveletTree(sB, sB + N, 1, N+1);
}

int can(int M, int K[]) {
	sort(K, K+M);
	int add = 0;
	for(int i = 0; i < M; ++i) {
		add += K[i];
		int j = upper_bound(sA, sA+N, K[i]) - sA;
		int next = i+1 < M ? K[i+1] : N + 1;
		int res = wt->query(0, j, K[i]) - wt->query(0, j, next);

		add = max(0, add - res);
	}
	return !add;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:56:39: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   56 |   int j = upper_bound(sA, sA+N, K[i]) - sA;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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