oj.uz

Submission #780416

# Submission time Handle Problem Language Result Execution time Memory
780416 2023-07-12T08:54:54 Z egekabas Teams (IOI15_teams) C++14
0 / 100
 863 ms 38916 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){
		int idx1 = upper_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[]) {
	int curMin = 0;
	int previous = 0;

	for(int i = 0; i < M; ++i){
		if(K[i] > curMin){
			previous = 0;
		}
		if(previous >= K[i]){
			previous -= K[i];
			continue;
		}
		int l = curMin+1, r = n+1;
		while(l < r){
			int m = (l+r)/2;
			if(previous + cnt(1, 1, n, K[i], curMin, m) >= K[i]){
				r = m;
			} else{
				l = m+1;
			}
		}
		if(l == n+1){
			return 0;
		}
		previous = previous + cnt(1, 1, n, K[i], curMin, l) - K[i];
		curMin = l;
	}
	return 1;
}

Compilation message

teams.cpp: In function 'int cnt(int, int, int, int, int, int)':
teams.cpp:37:44: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   37 |   int idx1 = upper_bound(all(seg[v]), valL)-seg[v].begin();
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
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 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 12048 KB Output is correct
3 Correct 5 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Incorrect 6 ms 11988 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 25688 KB Output is correct
2 Correct 40 ms 25548 KB Output is correct
3 Incorrect 39 ms 25636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 26312 KB Output is correct
2 Correct 43 ms 26316 KB Output is correct
3 Incorrect 863 ms 29668 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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