Submission #782740

#	Time	Username	Problem	Language	Result	Execution time	Memory
782740		ymm	Teams (IOI15_teams)	C++17	34 / 100	4035 ms	8360 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef std::pair<int,int> pii;
typedef long long ll;
using namespace std;

const int N = 200010;
int n;

namespace seg {
	vector<pii> vec;
	void add(int x, int y) {
		vec.push_back({x, y});
	}
	int get(int l1, int r1, int l2, int r2) {
		int ans = 0;
		for (auto [x, y] : vec)
			ans += l1 <= x && x < r1 && l2 <= y && y < r2;
		return ans;
	}
}

int cnt[N];
vector<pii> vec;

void init(int n, int a[], int b[]) {
	Loop (i,0,n) {
		seg::add(a[i], b[i]+1);
		cnt[a[i]]++;
		cnt[b[i]+1]--;
		vec.push_back({a[i], b[i]+1});
	}
	Loop (i,1,N)
		cnt[i] += cnt[i-1];
	::n = n;
	sort(vec.begin(), vec.end());
}

int can2(int m, int k[])
{
	priority_queue<int,vector<int>,greater<int>> pq;
	int p = 0;
	Loop (i,0,m) {
		while (p < vec.size() && vec[p].first <= k[i])
			pq.push(vec[p++].second);
		while (pq.size() && k[i] >= pq.top())
			pq.pop();
		if (pq.size() < k[i])
			return 0;
		if (i == m-1)
			return 1;
		Loop (_,0,k[i])
			pq.pop();
	}
	return -1;
}

int can(int m, int k[]) {
	ll sum = 0;
	Loop (i,0,m)
		sum += k[i];
	if (sum > n)
		return 0;
	sort(k, k+m);
	return can2(m ,k);
	vector<int> dp(m);
	LoopR (i,0,m) {
		dp[i] = cnt[k[i]] - k[i];
		Loop (j,i+1,m) {
			int x = seg::get(0, k[i]+1, k[i]+1, k[j]+1);
			x += dp[j] - k[i];
			dp[i] = min(dp[i], x);
		}
		if (dp[i] < 0)
			return 0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:28:15: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   28 | void init(int n, int a[], int b[]) {
      |           ~~~~^
teams.cpp:10:5: note: shadowed declaration is here
   10 | int n;
      |     ^
teams.cpp: In function 'int can2(int, int*)':
teams.cpp:46:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   while (p < vec.size() && vec[p].first <= k[i])
      |          ~~^~~~~~~~~~~~
teams.cpp:50:17: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |   if (pq.size() < k[i])
      |       ~~~~~~~~~~^~~~~~

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