oj.uz

Submission #780603

# Submission time Handle Problem Language Result Execution time Memory
780603 2023-07-12T10:45:55 Z dozer Teams (IOI15_teams) C++14
0 / 100
 2724 ms 524288 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 17 ms 12736 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2716 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 2724 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 270 ms 328660 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -