Submission #780464

#	Time	Username	Problem	Language	Result	Execution time	Memory
780464		egekabas	Teams (IOI15_teams)	C++14	0 / 100	890 ms	32120 KiB

teams

#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';
		used = K[i]- (cnt(1, 1, n, K[i], curMin, l-1)-used);
		curMin = l;

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

Compilation message (stderr)

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
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23