Submission #780603

#	Time	Username	Problem	Language	Result	Execution time	Memory
780603		dozer	Teams (IOI15_teams)	C++14	0 / 100	2724 ms	524288 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define st first
#define nd second
#define sp " "
#define pii pair<int, int>
#define LOGN 20

const int S = 400;
int tree[S + 5][100005];
int a[500005], b[500005], n;

void update(int bit[], int x, int val){
	while(x <= n){
		bit[x] += val;
		int lsb = x & -x;
		x += lsb;
	}
}

int query(int bit[], int x){
	int ans = 0;
	while(x > 0){
		ans += bit[x];
		int lsb = x & -x;
		x -= lsb;
	}
	return ans;
}

void init(int N, int A[], int B[]) {
	n = N;
	vector<int> v(N);
	iota(v.begin(), v.end(), 0);
	sort(v.begin(), v.end(), [&](int a, int b){
		if (B[a] == B[b]) return A[a] < A[b];
		return B[a] < B[b];
	});
	for (int i = 0; i < N; i++)
	{
		a[i] = A[v[i]], b[i] = B[v[i]];
	}

	for (int i = 0; i < N; i++){
		int g = i / S;
		update(tree[g], a[i], 1);
	}
}

int can(int M, int K[]) {
	sort(K, K + M);
	vector<int> vis(n, 0);
	vector<array<int, 3>> queries;
	int ans = 1;
	for (int i = 0; i < M; i++){
		int pos	= 0;
		for (int j = LOGN; j >= 0; j--){
			int tmp = pos + (1<<j);
			if (tmp < n && b[tmp] < K[i]) pos = tmp;
		}
		if (b[pos] < K[i]) pos++;
		int curr = K[i];
		while(pos < n && curr > 0){
			if (a[pos] > K[i]){
				update(tree[pos / S], a[pos], -1);
				queries.pb({pos / S, a[pos], 1});
				pos++;
				continue;
			}

			int x = query(tree[pos / S], K[i]);
			if (x > 0){
				curr--;
				update(tree[pos / S], 1, -1);
				queries.pb({pos / S, 1, 1});
			}
			pos++;
		}
		/*
		while(pos < n && curr > 0){
			int rem = query(tree[pos / S], K[i]);
			int diff = min(rem, curr);
			curr -= diff;
			update(tree[pos / S], 1, -diff);
			queries.pb({pos / S, 1, diff});
			pos += S;
		}*/
		if (curr > 0) ans = 0;
	}

	for (auto i : queries){
		update(tree[i[0]], i[1], i[2]);
	}
	return ans;
}

Compilation message (stderr)

teams.cpp: In lambda function:
teams.cpp:37:42: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   37 |  sort(v.begin(), v.end(), [&](int a, int b){
      |                                      ~~~~^
teams.cpp:13:16: note: shadowed declaration is here
   13 | int a[500005], b[500005], n;
      |                ^
teams.cpp:37:35: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   37 |  sort(v.begin(), v.end(), [&](int a, int b){
      |                               ~~~~^
teams.cpp:13:5: note: shadowed declaration is here
   13 | int a[500005], b[500005], n;
      |     ^

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