oj.uz

Submission #780488

# Submission time Handle Problem Language Result Execution time Memory
780488 2023-07-12T09:26:28 Z egekabas Teams (IOI15_teams) C++14
0 / 100
 825 ms 32136 KB 
#include "teams.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
int n;

vector<int> startHere[100009];
vector<int> seg[400009];

void initSeg(int v, int tl, int tr){
	if(tl == tr){
		seg[v] = startHere[tl];
		sort(all(seg[v]));
	} else{
		int tm = (tl+tr)/2;
		initSeg(2*v, tl, tm);
		initSeg(2*v+1, tm+1, tr);

		seg[v].resize(seg[2*v].size() + seg[2*v+1].size());
		merge(all(seg[2*v]), all(seg[2*v+1]), seg[v].begin());
	}
}

int cnt(int v, int tl, int tr, int idx, int valL, int valR){
	if(idx < tl){
		return 0;
	} else if(idx >= tr){
		// cout << tl << ' ' << tr << '\n';
		int idx1 = lower_bound(all(seg[v]), valL)-seg[v].begin();
		int idx2 = upper_bound(all(seg[v]), valR)-seg[v].begin();
		return max(0, idx2-idx1);
	} else{
		int tm = (tl+tr)/2;
		return cnt(2*v, tl, tm, idx, valL, valR)+cnt(2*v+1, tm+1, tr, idx, valL, valR);
	}
}

void init(int N, int A[], int B[]) {
	n = N;
	for(int i = 0; i < n; ++i){
		startHere[A[i]].pb(B[i]);
	}
	
	initSeg(1, 1, n);
}

int can(int M, int K[]) {
	sort(K, K+M);

	int curMin = 0;
	int used = 0;

	for(int i = 0; i < M; ++i){
		if(K[i] > curMin){
			used = 0;
			curMin = K[i];
		}

		int l = curMin, r = n+1;
		while(l < r){
			int m = (l+r)/2;
			if(cnt(1, 1, n, K[i], curMin, m)-used >= K[i]){
				r = m;
			} else{
				l = m+1;
			}
		}
		if(l == n+1){
			return 0;
		}
		// cout << cnt(1, 1, n, K[i], curMin, l) << '\n';
		if(l == curMin){
			used += K[i];
		} else{
			used = K[i] - (cnt(1, 1, n, K[i], curMin, l-1)-used);
		}

		curMin = l;

		// cout << K[i] << ' ' << curMin << ' ' << used << '\n';
	}
	return 1;
}

Compilation message

teams.cpp: In function 'int cnt(int, int, int, int, int, int)':
teams.cpp:38:44: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   38 |   int idx1 = lower_bound(all(seg[v]), valL)-seg[v].begin();
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
teams.cpp:39:44: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   39 |   int idx2 = upper_bound(all(seg[v]), valR)-seg[v].begin();
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 21.0

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

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 24428 KB Output is correct
2 Correct 41 ms 24380 KB Output is correct
3 Correct 41 ms 24492 KB Output is correct
4 Correct 41 ms 24808 KB Output is correct
5 Correct 16 ms 20308 KB Output is correct
6 Correct 15 ms 20308 KB Output is correct
7 Correct 15 ms 20308 KB Output is correct
8 Correct 14 ms 20252 KB Output is correct
9 Correct 18 ms 20324 KB Output is correct
10 Correct 40 ms 20300 KB Output is correct
11 Correct 18 ms 20328 KB Output is correct
12 Correct 16 ms 20344 KB Output is correct
13 Correct 21 ms 20688 KB Output is correct
14 Correct 26 ms 22508 KB Output is correct
15 Incorrect 37 ms 24016 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 24840 KB Output is correct
2 Correct 45 ms 24752 KB Output is correct
3 Correct 825 ms 27764 KB Output is correct
4 Correct 41 ms 24780 KB Output is correct
5 Correct 245 ms 20652 KB Output is correct
6 Correct 221 ms 20728 KB Output is correct
7 Correct 20 ms 20692 KB Output is correct
8 Correct 166 ms 20736 KB Output is correct
9 Correct 18 ms 20428 KB Output is correct
10 Correct 155 ms 20680 KB Output is correct
11 Correct 183 ms 20784 KB Output is correct
12 Incorrect 222 ms 20632 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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