Submission #510016

#	Time	Username	Problem	Language	Result	Execution time	Memory
510016		keta_tsimakuridze	Teams (IOI15_teams)	C++14	100 / 100	3554 ms	343352 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 = 15e5 + 5;
int le_[N * 20], ri_[N * 20], root[N], tree[N * 20], n, cur, prev[N], k[N], a[N], b[N], nxt[N], p[N], rem[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];
	assert(cur <= N * 35);
	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;
	if(id <= mid) return tree[u] + get(le_[u], id, l, mid);
	return tree[u] + 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 = k[j] + 1, r = n, ans = n + 1;
	while(l <= r) {
		int mid = (l + r) / 2;
		if(dp[i] - get(root[k[i] + 1], mid, 1, n) >= dp[j] - get(root[k[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);
	vector<int> s; set<pii> bet;
	s.push_back(0);
	for(int i = 1; i <= M; i++) {
		k[i] = K[i - 1];  rem[i] = 0; nxt[i] = p[i] = 0;
	}
	for(int i = 1; i <= M; i++) {
		while(bet.size() && (*bet.begin()).f <= k[i]) {
			pii po = *bet.begin();
			bet.erase(po);
			int r = po.s, l = p[r];
			rem[r] = 1;
			if(nxt[r]) {
				nxt[l] = nxt[r];
				p[nxt[l]] = l;
				int x = nxt[l];
				bet.erase({prev[x], x});
				prev[x] = get(l, x);
				bet.insert({prev[x], x});
			}
			
		}
		while(s.size() && rem[s.back()]) s.pop_back();
		int x = s.back();
		dp[i] = dp[x] + k[i] - get(root[k[x] + 1], k[i], 1, n);
		prev[i] = get(x, i);s.push_back(i); nxt[x] = i; p[i] = x;
		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:43:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   43 | void init(int N, int A[], int B[]) {
      |           ~~~~^
teams.cpp:8:11: note: shadowed declaration is here
    8 | const int N = 15e5 + 5;
      |           ^
teams.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(int j = 0; j < V[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~

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