Submission #782660

#	Time	Username	Problem	Language	Result	Execution time	Memory
782660		ymm	Teams (IOI15_teams)	C++17	0 / 100	4058 ms	15092 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];

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]--;
	}
	Loop (i,1,N)
		cnt[i] += cnt[i-1];
	::n = n;
}

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);
	int mn = 0;
	LoopR (i,0,m) {
		if (cnt[k[i]] - k[i] + mn < 0)
			return 0;
		if (!i)
			continue;
		int x = seg::get(k[i-1]+1, k[i]+1, k[i]+1, N) - k[i];
		mn += x;
		mn = min(mn, 0);
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:27:15: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   27 | void init(int n, int a[], int b[]) {
      |           ~~~~^
teams.cpp:10:5: note: shadowed declaration is here
   10 | int n;
      |     ^

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