oj.uz

Submission #808773

# Submission time Handle Problem Language Result Execution time Memory
808773 2023-08-05T10:49:48 Z Sohsoh84 Teams (IOI15_teams) C++17
100 / 100
 1417 ms 470412 KB 
#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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94156 KB Output is correct
2 Correct 42 ms 94204 KB Output is correct
3 Correct 42 ms 94324 KB Output is correct
4 Correct 43 ms 94232 KB Output is correct
5 Correct 43 ms 94188 KB Output is correct
6 Correct 43 ms 94300 KB Output is correct
7 Correct 42 ms 94276 KB Output is correct
8 Correct 42 ms 94304 KB Output is correct
9 Correct 43 ms 94292 KB Output is correct
10 Correct 43 ms 94280 KB Output is correct
11 Correct 42 ms 94304 KB Output is correct
12 Correct 43 ms 94304 KB Output is correct
13 Correct 44 ms 94256 KB Output is correct
14 Correct 42 ms 94184 KB Output is correct
15 Correct 42 ms 94240 KB Output is correct
16 Correct 48 ms 94260 KB Output is correct
17 Correct 45 ms 94292 KB Output is correct
18 Correct 42 ms 94200 KB Output is correct
19 Correct 41 ms 94184 KB Output is correct
20 Correct 45 ms 94240 KB Output is correct
21 Correct 41 ms 94192 KB Output is correct
22 Correct 42 ms 94240 KB Output is correct
23 Correct 43 ms 94248 KB Output is correct
24 Correct 42 ms 94240 KB Output is correct
25 Correct 42 ms 94276 KB Output is correct
26 Correct 45 ms 94200 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 159904 KB Output is correct
2 Correct 146 ms 159756 KB Output is correct
3 Correct 147 ms 159684 KB Output is correct
4 Correct 144 ms 160964 KB Output is correct
5 Correct 99 ms 158492 KB Output is correct
6 Correct 100 ms 158512 KB Output is correct
7 Correct 99 ms 158456 KB Output is correct
8 Correct 105 ms 158536 KB Output is correct
9 Correct 98 ms 159872 KB Output is correct
10 Correct 94 ms 159584 KB Output is correct
11 Correct 100 ms 159296 KB Output is correct
12 Correct 98 ms 159160 KB Output is correct
13 Correct 109 ms 159028 KB Output is correct
14 Correct 118 ms 159564 KB Output is correct
15 Correct 168 ms 159624 KB Output is correct
16 Correct 135 ms 159604 KB Output is correct
17 Correct 104 ms 159488 KB Output is correct
18 Correct 103 ms 159516 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 160204 KB Output is correct
2 Correct 180 ms 160312 KB Output is correct
3 Correct 265 ms 163596 KB Output is correct
4 Correct 147 ms 160844 KB Output is correct
5 Correct 230 ms 158956 KB Output is correct
6 Correct 216 ms 159060 KB Output is correct
7 Correct 106 ms 158936 KB Output is correct
8 Correct 196 ms 158912 KB Output is correct
9 Correct 99 ms 159864 KB Output is correct
10 Correct 109 ms 159856 KB Output is correct
11 Correct 115 ms 159644 KB Output is correct
12 Correct 399 ms 159632 KB Output is correct
13 Correct 381 ms 159496 KB Output is correct
14 Correct 265 ms 162612 KB Output is correct
15 Correct 226 ms 160176 KB Output is correct
16 Correct 244 ms 160312 KB Output is correct
17 Correct 173 ms 160068 KB Output is correct
18 Correct 165 ms 159964 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 457668 KB Output is correct
2 Correct 864 ms 457756 KB Output is correct
3 Correct 1114 ms 465316 KB Output is correct
4 Correct 806 ms 459116 KB Output is correct
5 Correct 669 ms 451308 KB Output is correct
6 Correct 660 ms 451408 KB Output is correct
7 Correct 350 ms 451208 KB Output is correct
8 Correct 576 ms 455960 KB Output is correct
9 Correct 350 ms 458168 KB Output is correct
10 Correct 338 ms 454480 KB Output is correct
11 Correct 555 ms 455028 KB Output is correct
12 Correct 1270 ms 455832 KB Output is correct
13 Correct 1417 ms 458864 KB Output is correct
14 Correct 1227 ms 470412 KB Output is correct
15 Correct 976 ms 464000 KB Output is correct
16 Correct 898 ms 463912 KB Output is correct
17 Correct 561 ms 458776 KB Output is correct
18 Correct 549 ms 458828 KB Output is correct