Submission #798337

#	Time	Username	Problem	Language	Result	Execution time	Memory
798337		prvocislo	Teams (IOI15_teams)	C++17	100 / 100	1216 ms	248508 KiB

teams

#pragma once
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

const int len = 2e7 + 5;
int sum[len], ls[len], rs[len], l[len], r[len], cnt = 0;
int build(int li, int ri)
{
	int vr = cnt++;
	l[vr] = li, r[vr] = ri, sum[vr] = 0;
	if (li != ri) ls[vr] = build(li, (li + ri) / 2), rs[vr] = build((li + ri) / 2 + 1, ri);
	return vr;
}
int upd(int i, int vr) // vrati novy koren
{
	if (i < l[vr] || i > r[vr]) return vr;
	int v2 = cnt++;
	sum[v2] = sum[vr] + 1;
	l[v2] = l[vr], r[v2] = r[vr];
	if (l[vr] != r[vr]) ls[v2] = upd(i, ls[vr]), rs[v2] = upd(i, rs[vr]);
	return v2;
}
int query(int li, int ri, int vr)
{
	if (ri < l[vr] || li > r[vr]) return 0;
	if (li <= l[vr] && r[vr] <= ri) return sum[vr];
	return query(li, ri, ls[vr]) + query(li, ri, rs[vr]);
}
vector<int> ro;
int n;
void init(int N, int A[], int B[])
//void init(int N, vector<int> A, vector<int> B)
{
	n = N, cnt = 0;
	ro.resize(N + 1);
	vector<vector<int> > e(N + 1);
	for (int i = 0; i < N; i++) e[A[i]].push_back(B[i]);
	ro[0] = build(0, N);
	for (int i = 0; i <= N; i++)
	{
		if (i) ro[i] = ro[i - 1];
		for (int x : e[i]) ro[i] = upd(x, ro[i]);
	}
}
int can(int M, int K[])
//int can(int M, vector<int> K)
{
	int s = 0;
	for (int i = 0; i < M; i++) s += K[i];
	if (s > n) return 0;
	sort(K, K + M);
	//sort(K.begin(), K.end());
	vector<pair<int, int> > v;
	for (int i = 0; i < M; i++)
	{
		if (!i || v.back().first != K[i]) v.push_back({ K[i], 0 });
		v.back().second += K[i];
	}
	vector<int> dp(v.size(), 0); // najvacsie mozne places - kids
	for (int ri = v.size() - 1; ri >= 0; ri--)
	{
		dp[ri] = v[ri].second - (query(v[ri].first, n, ro[v[ri].first]));
		if (dp[ri] > 0) return 0;
		int mx = -1e9;
		for (int li = ri + 1; li < v.size(); li++) if (dp[li] > mx)
		{
			mx = dp[li];
			dp[ri] = max(dp[ri], dp[li] + v[ri].second - query(v[ri].first, v[li].first - 1, ro[v[ri].first]));
			if (dp[ri] > 0) return 0;
		}
	}
	return 1;
}

Compilation message (stderr)

teams.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:75:25: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   75 |  for (int ri = v.size() - 1; ri >= 0; ri--)
      |                ~~~~~~~~~^~~
teams.cpp:80:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for (int li = ri + 1; li < v.size(); li++) if (dp[li] > mx)
      |                         ~~~^~~~~~~~~~

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