Submission #808773

#	Time	Username	Problem	Language	Result	Execution time	Memory
808773		Sohsoh84	Teams (IOI15_teams)	C++17	100 / 100	1417 ms	470412 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define debug(x)		cerr << #x << ": " << x << endl;
#define all(x)			(x).begin(), (x).end()

const int MAXN = 4e6 + 10;
const int INF = 1e9 + 10;

struct node {
	node *lc, *rc;
	ll val;

	node() {}
	node(ll val_): lc(nullptr), rc(nullptr), val(val_) {}
	node(node* lc_, node* rc_): lc(lc_), rc(rc_) {
		val = lc_ -> val + rc_ -> val;
	}
};

namespace segment {
	node* sg[MAXN];

	node* build(int l, int r) {
		if (l == r) return new node(0);
		int mid = (l + r) >> 1;
		return new node(build(l, mid), build(mid + 1, r));
	}

	node* update(int ind, int l, int r, node* v) {
		if (l == r) return new node((v -> val) + 1);
		int mid = (l + r) >> 1;
		if (ind <= mid) return new node(update(ind, l, mid, v -> lc), v -> rc);
		else return new node(v -> lc, update(ind, mid + 1, r, v -> rc));
	}

	int query(int ql, int qr, int l, int r, node* v) {
		if (ql > r || qr < l) return 0;
		if (ql <= l && qr >= r) return v -> val;

		int mid = (l + r) >> 1;
		return query(ql, qr, l, mid, v -> lc) +
			query(ql, qr, mid + 1, r, v -> rc);
	}
}

int n, ps[MAXN];
vector<int> R[MAXN];
int dp[MAXN], F[MAXN];
vector<int> vec;

inline int get(int l, int r) {
	if (r < l) return 0;
	return segment::query(l, n, 1, n, segment::sg[r]);
}

inline int cov(int l, int r) {
	ll s = ps[r] - ps[l - 1];
	return s - get(l, r - 1);
}

namespace li_chao {
	int best[MAXN], T[MAXN];
	
	inline int calc(int ind, int x) {
//		if (x <= vec[ind]) return INF;
		return dp[ind] + cov(vec[ind] + 1, x);
	}
	
	void add(int f, int l = 1, int r = n + 1, int v = 1) {
		T[v] = 1;
		int m = (l + r) >> 1;
		bool lf = calc(f, l) < calc(best[v], l);
		bool md = calc(f, m) < calc(best[v], m);

		if (md) swap(best[v], f);
		if (r - l == 1) return;
		else if (lf != md) add(f, l, m, v << 1);
		else add(f, m, r, v << 1 | 1);
	}

	int query(int x, int l = 1, int r = n + 1, int v = 1) {
		int m = (l + r) >> 1;
		if (r - l == 1) return calc(best[v], x);
		else if (x < m) return min(calc(best[v], x), query(x, l, m, v << 1)); 
		else return min(calc(best[v], x), query(x, m, r, v << 1 | 1));
	}

	void clear(int l = 1, int r = n + 1, int v = 1) {
		best[v] = 0;
		if (r - l == 1 || !T[v]) {
			T[v] = 0;
			return;
		}

		T[v] = 0;

		int m = (l + r) >> 1;
		clear(l, m, v << 1);
		clear(m, r, v << 1 | 1);
	}
}

void init(int N, int A[], int B[]) {
	n = N;
	for (int i = 0; i < n; i++) {
		R[B[i]].push_back(A[i]);
		ps[A[i]]++;
	}

	for (int i = 1; i <= n; i++) ps[i] += ps[i - 1];

	segment::sg[0] = segment::build(1, n);
	for (int i = 1; i <= n; i++) {
		node* v = segment::sg[i - 1];
		for (int l : R[i])
			v = segment::update(l, 1, n, v);

		segment::sg[i] = v;
	}
}

inline void clear(int M, int K[]) {
	vec.clear();
	for (int i = 0; i < M; i++) {
		F[K[i]] = 0;
		dp[i] = 0;
	}

	dp[M] = 0;
	li_chao::clear();
}

int can(int M, int K[]) {
	int m = M, s = 0;
	
	for (int i = 0; i < m; i++) {
		s += K[i];
		if (s > n) {
			clear(M, K);
			return 0;
		}

		F[K[i]] += K[i];
		vec.push_back(K[i]);
	}

	sort(all(vec));
	vec.resize(unique(all(vec)) - vec.begin());
		
	vec.insert(vec.begin(), 0);
	dp[0] = 0;

	m = vec.size();
	for (int i = 1; i < m; i++) {
		dp[i] = numeric_limits<int>::max();
		dp[i] = li_chao::query(vec[i]) - F[vec[i]];
	
		if (dp[i] < 0) {
			clear(M, K);
			return 0;
		}

		li_chao::add(i);
	}

	clear(M, K);
	return 1;
}    

Compilation message (stderr)

teams.cpp: In function 'int segment::query(int, int, int, int, node*)':
teams.cpp:43:39: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   43 |   if (ql <= l && qr >= r) return v -> val;
      |                                  ~~~~~^~~
teams.cpp: In function 'int cov(int, int)':
teams.cpp:63:11: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   63 |  return s - get(l, r - 1);
      |         ~~^~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:158:14: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  158 |  m = vec.size();
      |      ~~~~~~~~^~

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