Submission #541773

#	Time	Username	Problem	Language	Result	Execution time	Memory
541773		NachoLibre	Teams (IOI15_teams)	C++17	100 / 100	1493 ms	524288 KiB

teams

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define vint vector<int>
using namespace std;
#ifndef x
#include "teams.h"
#else
#endif

const int N = 500005, S = 200005;
int n, a[N], b[N], m, k[S], dp[S];
vector<int> e[N];

struct zz {
	zz *l = 0, *r = 0;
	vector<int> v;
	vector<array<int, 2> > t, lv, rv;
	void P() {
		// cout << "-" << endl;
		// cout << "+" << endl;
		int li = 0, ri = 0;
		while(li < sz(l->v) || ri < sz(r->v)) {
			if(li == sz(l->v) || (ri < sz(r->v) && r->v[ri] < l->v[li])) {
				v.push_back(r->v[ri]);
				t.push_back({1, ri});
				ri += 1;
			} else /* if(ri == sz(r->v) || r->v[ri] >= l->v[li]) */ {
				v.push_back(l->v[li]);
				t.push_back({0, li});
				li += 1;
			}
		}
		lv.resize(sz(v), {-1, -1});
		rv.resize(sz(v), {-1, -1});
		for(int i = 0; i < sz(v); ++i) {
			if(t[i][0] == 0) lv[i][0] = t[i][1];
			else if(i) lv[i][0] = lv[i - 1][0];
			if(t[i][0] == 1) rv[i][0] = t[i][1];
			else if(i) rv[i][0] = rv[i - 1][0];
		}
		for(int i = sz(v) - 1; i >= 0; --i) {
			if(t[i][0] == 0) lv[i][1] = t[i][1];
			else if(i < sz(v) - 1) lv[i][1] = lv[i + 1][1];
			if(t[i][0] == 1) rv[i][1] = t[i][1];
			else if(i < sz(v) - 1) rv[i][1] = rv[i + 1][1];
		}
	}
	void add(int x) {
		v.push_back(x);
		t.push_back({0, 0});
		lv.push_back({0, 0});
		rv.push_back({0, 0});
	}
} *root;

void bld(int l = 1, int r = n + 1, zz *&t = root) {
	if(!t) t = new zz();
	if(l == r) {
		for(int i = 0; i < sz(e[l]); ++i) {
			t->add(e[l][i]);
		}
		return;
	}
	int m = l + r >> 1;
	bld(l, m, t->l);
	bld(m + 1, r, t->r);
	t->P();
} //

int cnt(int vl, int vr, int sl, int l = 1, int r = n + 1, zz *&t = root) {
	if(!t || vl > vr || vl == -1 || vr == -1) { return 0; }
	if(r < sl) return 0;
	if(l >= sl) return vr - vl + 1;
	int m = l + r >> 1;
	return cnt(t->lv[vl][1], t->lv[vr][0], sl, l, m, t->l) + cnt(t->rv[vl][1], t->rv[vr][0], sl, m + 1, r, t->r);
} //

int Z(int i, int j) {
	// [k[i] + 1, k[j]] x [k[j], +oo)
	int xl = (i == -1 ? 1 : k[i] + 1), xr = k[j], sl = k[j];
	int vl = lower_bound(all(root->v), xl) - (root->v).begin();
	int vr = int(upper_bound(all(root->v), xr) - (root->v).begin()) - 1;
	return cnt(vl, vr, sl);
} //

void init(int _n, int _a[], int _b[]) {
	n = _n;
	for(int i = 0; i < n; ++i) {
		a[i] = _a[i];
		b[i] = _b[i];
		e[b[i]].push_back(a[i]);
	}
	for(int i = 1; i <= n; ++i) {
		sort(all(e[i]));
	}
	bld();
	// cout << "BLD" << endl;
} //

array<int, 2> mir(int vl, int vr, int cr, int l = 1, int r = n + 1, zz *&t = root) {
	if(!t || vl > vr || vl == -1 || vr == -1) { vl = 1; vr = 0; }
	if(l == r) {
		int ncr = cr - (vr - vl + 1);
		if(ncr >= 0) return {l, ncr};
		return {r + 1, cr};
	}
	if(vr - vl + 1 <= cr) {
		return {l, cr - (vr - vl + 1)};
	}
	int m = l + r >> 1;
	array<int, 2> x = mir(t->rv[vl][1], t->rv[vr][0], cr, m + 1, r, t->r);
	if(x[0] == m + 1) {
	}
}

int mindx(int i, int j) {
	if(0) {
		int xl = (i == -1 ? 1 : k[i] + 1), xr = k[j];
		int vl = lower_bound(all(root->v), xl) - (root->v).begin();
		int vr = int(upper_bound(all(root->v), xr) - (root->v).begin()) - 1;
		int cr = dp[j] - dp[i];
		int y = mir(vl, vr, cr)[0];
		// dp[j] - dp[i] > [k[i] + 1, k[j]] x [y, +oo)
	} else { // // // // // // // //
		if(dp[i] + Z(i, m - 1) >= dp[j] + Z(j, m - 1)) {
			return m;
		}
		int l = j, r = m - 1;
		while(l < r) {
			int md = l + r >> 1;
			if(dp[i] + Z(i, md) < dp[j] + Z(j, md)) r = md;
			else l = md + 1;
		}
		return l;
	} //
}

multiset<int> sx;
multiset<array<int, 2> > sy;
void insert_51(int i) {
	int x = -1;
	if(sz(sx)) x = *(--sx.end());
	sx.insert(i);
	if(x == -1) return;
	sy.insert({mindx(x, i), i});
} //

bool pop_51(int i) {
	if(!sz(sy) || (*sy.begin())[0] > i) {
		return 0;
	}
	int x = (*sy.begin())[1];
	sy.erase(sy.begin());
	auto it = sx.find(x);
	sx.erase(it++);
	if(it == sx.end()) return 1;
	int z = *it;
	it--;
	int y = *it;
	sy.erase(sy.find({mindx(x, z), z}));
	sy.insert({mindx(y, z), z});
	return 1;
} //

void clear_51() {
	sx.clear();
	sy.clear();
} //

int can(int _m, int _k[]) {
	clear_51();
	m = _m;
	for(int i = 0; i < m; ++i) {
		dp[i] = 0;
		// // // //
		k[i] = _k[i];
	}
	sort(k, k + m);
	dp[0] = Z(-1, 0) - k[0]; ///
	insert_51(0);
	int dr = dp[0];
	for(int i = 1; i < m; ++i) {
		while(pop_51(i));
		int x = *(--sx.end());
		dp[i] = dp[x] + Z(x, i) - k[i];
		dp[i] = min(dp[i], Z(-1, i) - k[i]);
		dr = min(dr, dp[i]);
		insert_51(i);
	}
	return dr >= 0;
} //

#ifdef x
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	freopen("x.txt", "r", stdin);
    int N;
    cin >> N;
    int *A = (int*)malloc(sizeof(int)*(unsigned int)N);
    int *B = (int*)malloc(sizeof(int)*(unsigned int)N);
    for (int i = 0; i < N; ++i) {
    	cin >> A[i];
    	cin >> B[i];
    }
    init(N, A, B);
    int Q;
    cin >> Q;
    for (int i = 0; i < Q; ++i) {
    	int M;
    	cin >> M;
		int *K = (int*)malloc(sizeof(int)*(unsigned int)M);
    	for (int j = 0; j < M; ++j) {
    		cin >> K[j];
    	}
    	// fprintf(_outputFile,"%d\n", can(M, K));
		cout << can(M, K) << endl;
    }
	return 0;
}
#endif

Compilation message (stderr)

teams.cpp: In function 'void bld(int, int, zz*&)':
teams.cpp:67:6: warning: declaration of 'm' shadows a global declaration [-Wshadow]
   67 |  int m = l + r >> 1;
      |      ^
teams.cpp:14:20: note: shadowed declaration is here
   14 | int n, a[N], b[N], m, k[S], dp[S];
      |                    ^
teams.cpp:67:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |  int m = l + r >> 1;
      |          ~~^~~
teams.cpp: In function 'int cnt(int, int, int, int, int, zz*&)':
teams.cpp:77:6: warning: declaration of 'm' shadows a global declaration [-Wshadow]
   77 |  int m = l + r >> 1;
      |      ^
teams.cpp:14:20: note: shadowed declaration is here
   14 | int n, a[N], b[N], m, k[S], dp[S];
      |                    ^
teams.cpp:77:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |  int m = l + r >> 1;
      |          ~~^~~
teams.cpp: In function 'int Z(int, int)':
teams.cpp:84:41: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   84 |  int vl = lower_bound(all(root->v), xl) - (root->v).begin();
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'std::array<int, 2> mir(int, int, int, int, int, zz*&)':
teams.cpp:113:6: warning: declaration of 'm' shadows a global declaration [-Wshadow]
  113 |  int m = l + r >> 1;
      |      ^
teams.cpp:14:20: note: shadowed declaration is here
   14 | int n, a[N], b[N], m, k[S], dp[S];
      |                    ^
teams.cpp:113:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 |  int m = l + r >> 1;
      |          ~~^~~
teams.cpp: In function 'int mindx(int, int)':
teams.cpp:122:42: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  122 |   int vl = lower_bound(all(root->v), xl) - (root->v).begin();
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
teams.cpp:125:7: warning: unused variable 'y' [-Wunused-variable]
  125 |   int y = mir(vl, vr, cr)[0];
      |       ^
teams.cpp:133:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  133 |    int md = l + r >> 1;
      |             ~~^~~
teams.cpp: In function 'std::array<int, 2> mir(int, int, int, int, int, zz*&)':
teams.cpp:115:10: warning: control reaches end of non-void function [-Wreturn-type]
  115 |  if(x[0] == m + 1) {

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