Submission #782769

#	Time	Username	Problem	Language	Result	Execution time	Memory
782769		ymm	Teams (IOI15_teams)	C++17	100 / 100	2741 ms	140804 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 = 500010;
int n;

namespace seg {
	vector<int> nds;
	vector<int> ls;
	int nxt = 1;
	struct node {
		int cnt, l, r;
	} nd[(1<<27)/sizeof(node)];

	int get(int t, int l, int r, int b, int e) {
		if (l <= b && e <= r)
			return nd[t].cnt;
		int ans = 0;
		if (l < (b+e)/2 && nd[t].l)
			ans += get(nd[t].l, l, r, b, (b+e)/2);
		if ((b+e)/2 < r && nd[t].r)
			ans += get(nd[t].r, l, r, (b+e)/2, e);
		return ans;
	}
	int add(int t, int p, int b, int e) {
		int ans = nxt++;
		nd[ans].cnt = nd[t].cnt+1;
		nd[ans].l = nd[t].l;
		nd[ans].r = nd[t].r;
		if (e-b == 1)
			return ans;
		if (p < (b+e)/2)
			nd[ans].l = add(nd[t].l, p, b, (b+e)/2);
		else
			nd[ans].r = add(nd[t].r, p, (b+e)/2, e);
		return ans;
	}

	void mk_seg(const vector<pii> &vec) {
		nds = {0};
		int p = 0;
		Loop (i,1,N+1) {
			int t = nds.back();
			while (p < vec.size() && vec[p].first < i)
				t = add(t, vec[p++].second, 0, N);
			nds.push_back(t);
		}
	}
	int get(int l1, int r1, int l2, int r2) {
		return get(nds[r1], l2, r2, 0, N)
		     - get(nds[l1], l2, r2, 0, N);
	}
}

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

void init(int n, int a[], int b[]) {
	Loop (i,0,n) {
		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());
	seg::mk_seg(vec);
}

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;
}

const int S = 700;

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);
	if (m > S)
		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 seg::mk_seg(const std::vector<std::pair<int, int> >&)':
teams.cpp:49:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |    while (p < vec.size() && vec[p].first < i)
      |           ~~^~~~~~~~~~~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:63:15: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   63 | 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:81: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]
   81 |   while (p < vec.size() && vec[p].first <= k[i])
      |          ~~^~~~~~~~~~~~
teams.cpp:85: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]
   85 |   if (pq.size() < k[i])
      |       ~~~~~~~~~~^~~~~~

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