Submission #509899

#	Time	Username	Problem	Language	Result	Execution time	Memory
509899		keta_tsimakuridze	팀들 (IOI15_teams)	C++14	0 / 100	1144 ms	185540 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define prev Prev
#define f first
#define s second
using namespace std;
const int N = 3e5 + 5;
int le_[N * 20], ri_[N * 20], root[N], tree[N * 20], n, cur, prev[N], a[N], b[N];
long long dp[N]; 
void build(int u,int l,int r) {
	if(l == r) return;
	int mid = (l + r) / 2;
	le_[u] = ++cur; ri_[u] = ++cur;
	build(le_[u], l, mid); build(ri_[u], mid + 1, r);
}
void upd(int u,int st,int en,int l,int r) {
	if(l > en || r < st) return; 
	le_[cur] = le_[u], ri_[cur] = ri_[u]; 
	tree[cur] = tree[u];
	if(st <= l && r <= en) { 
		tree[cur]++;
		return;
	}
	int mid = (l + r) / 2, x = cur;
	if(st <= mid) {
		le_[x] = ++cur;
	}
	upd(le_[u], st, en, l, mid);
	if(en > mid) {
		ri_[x] = ++cur;
	}
	upd(ri_[u], st, en, mid + 1, r);
}
int get(int u,int id, int l,int r) {
	if(id > r || id < l) return 0;
	if(l == r) return tree[u];
	int mid = (l + r) >> 1;
	return tree[u] + get(le_[u], id, l, mid) + get(ri_[u], id, mid + 1, r);
}
void init(int N, int A[], int B[]) {
	n = N;
	vector<int> V[n + 2]; 
	for(int i = 0; i < n; i++) V[A[i]].push_back(B[i]);
	cur = root[n + 1] =  1;
	build(1, 1, n); 
	for(int i = n; i >= 1; i--) {
		root[i] = root[i + 1];
		for(int j = 0; j < V[i].size(); j++) {
			cur++;
			int x = cur;
			upd(root[i], i, V[i][j], 1, n); 
			root[i] = x;
		}
	}
}
 
int get(int i, int j) {
	int l = j, r = n, ans = n + 1;
	while(l <= r) {
		int mid = (l + r) / 2;
		if(dp[i] - get(root[i + 1], mid, 1, n) <= dp[j] - get(root[j + 1], mid, 1, n)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	return ans;
}
int can(int M, int K[]) {
	sort(K, K + M);
	set<int> s; set<pii> bet;
	s.insert(0);
	vector<int> k(M + 2); 
	for(int i = 1; i <= M; i++) {
		k[i] = K[i - 1]; 
	}
	for(int i = 1; i <= M; i++) {
		while(bet.size() && (*bet.begin()).f <= i) {
			pii p = *bet.begin();
			bet.erase(p);
			int r = p.s, l = *--s.upper_bound(r - 1);
			s.erase(l);
			if(s.upper_bound(l - 1) != s.begin()) {
				int p = *--s.upper_bound(l - 1);
				bet.erase({prev[l], l});
				prev[r] = get(k[p], k[r]);
				bet.insert({prev[r], r});
			}
			
		}
		int x = *s.begin();
		dp[i] = max(dp[i], dp[x] + k[i] - get(root[k[x] + 1], k[i], 1, n));
		s.insert(i);
		prev[i] = get(k[*--s.end()], k[i]);
		bet.insert({prev[i], i});
		if(dp[i] > 0) return 0;
	}
	return 1;
}
/*
int main() {
//	_inputFile = fopen("teams.in", "rb");
//	_outputFile = fopen("teams.out", "w");
	int n, q;
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i] >> b[i];
	init(n, a, b); 
	cin >> q;
	while(q--) {
		int k;
		cin >> k;
		int v[k + 2];
		for(int i = 0; i < k; i++) cin >> v[i];
		cout << can(k, v) << endl;
	}
    return 0;
} */

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:41:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   41 | void init(int N, int A[], int B[]) {
      |           ~~~~^
teams.cpp:8:11: note: shadowed declaration is here
    8 | const int N = 3e5 + 5;
      |           ^
teams.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int j = 0; j < V[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:82:9: warning: declaration of 'p' shadows a previous local [-Wshadow]
   82 |     int p = *--s.upper_bound(l - 1);
      |         ^
teams.cpp:77:8: note: shadowed declaration is here
   77 |    pii p = *bet.begin();
      |        ^

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