oj.uz

Submission #172439

# Submission time Handle Problem Language Result Execution time Memory
172439 2020-01-01T14:36:08 Z gs18103 Teams (IOI15_teams) C++14
100 / 100
 1552 ms 219300 KB 
#include "teams.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 505050;
const int INF = INT_MAX >> 1;
const ll LINF = LLONG_MAX >> 1;
const ll mod = 1e9+9;

struct Node {
	int l, r, val;
	Node(int l, int r, int val) : l(l), r(r), val(val) {}
};

int n, root[MAX], h[MAX];
vector <Node> tree;
vector <int> num, numx;
pii arr[MAX];

void expand_tree(int s, int e, int k, int pnd, int cnd) {
	tree[cnd].val = tree[pnd].val + 1;
	if(s == e) return;
	int m = s + e >> 1;
	if(k <= m) {
		tree[cnd].r = tree[pnd].r;
		tree[cnd].l = tree.size();
		tree.eb(0, 0, 0);
		expand_tree(s, m, k, tree[pnd].l, tree[cnd].l);
	}
	else {
		tree[cnd].l = tree[pnd].l;
		tree[cnd].r = tree.size();
		tree.eb(0, 0, 0);
		expand_tree(m+1, e, k, tree[pnd].r, tree[cnd].r);
	}
}

void init(int N, int A[], int B[]) {
	n = N;
	for(int i = 0; i < n; i++) {
		arr[i] = make_pair(A[i], B[i]);
		num.eb(B[i]);
		numx.eb(A[i]);
	}
	sort(all(num));
	sort(all(numx));
	sort(arr, arr+n, [](pii a, pii b) {
		if(a.se == b.se) return a.fi < b.fi;
		return a.se < b.se;
	});
	for(int i = 0; i < n; i++) {
		arr[i].se = i + 1;
	}
	sort(arr, arr+n);
	tree.eb(0, 0, 0);
	for(int i = 0; i < n; i++) {
		root[i+1] = tree.size();
		tree.eb(0, 0, 0);
		expand_tree(1, n, arr[i].se, root[i], root[i+1]);
	}
	return;
}

int cal(int s, int e, int l, int r, int pnd, int cnd) {
	if(s > r || e < l || l > r) return 0;
	if(s >= l && e <= r) return tree[cnd].val - tree[pnd].val;
	int m = s + e >> 1;
	return cal(s, m, l, r, tree[pnd].l, tree[cnd].l)
		+ cal(m+1, e, l, r, tree[pnd].r, tree[cnd].r);
}

int get_r(int s, int e, int cnt, int pnd, int cnd) {
	if(s == e) return s;
	int m = s + e >> 1, lcnt = tree[tree[cnd].l].val - tree[tree[pnd].l].val;
	if(lcnt >= cnt) return get_r(s, m, cnt, tree[pnd].l, tree[cnd].l);
	else return get_r(m+1, e, cnt - lcnt, tree[pnd].r, tree[cnd].r);
}

int can(int M, int K[]) {
	ll temp = 0;
	for(int i = 0; i < M; i++) temp += K[i];
	if(temp > n) return 0;

	sort(K, K+M);
	stack <pii> stk;
	stk.em(0, n+1);
	for(int i = 0; i < M; i++) {
		int last = lower_bound(all(num), K[i]) - num.begin() + 1, cnt = K[i];
		int rx = upper_bound(all(numx), K[i]) - numx.begin();
		while(!stk.empty() && stk.top().se < last) stk.pop();
		while(!stk.empty()) {
			int x = stk.top().fi, y = stk.top().se;
			int temp = cal(1, n, last, y, root[x], root[rx]);
			if(temp < cnt) {
				cnt -= temp;
				last = y + 1;
				stk.pop();
			}
			else {
				int l = cal(1, n, 1, last - 1, root[x], root[rx]);
				int ny = get_r(1, n, l + cnt, root[x], root[rx]);
				stk.em(rx, ny);
				break;
			}
		}
		if(stk.empty()) return 0;
	}
	return 1;
}

Compilation message

teams.cpp: In constructor 'Node::Node(int, int, int)':
teams.cpp:21:30: warning: declaration of 'val' shadows a member of 'Node' [-Wshadow]
  Node(int l, int r, int val) : l(l), r(r), val(val) {}
                              ^
teams.cpp:20:12: note: shadowed declaration is here
  int l, r, val;
            ^~~
teams.cpp:21:30: warning: declaration of 'r' shadows a member of 'Node' [-Wshadow]
  Node(int l, int r, int val) : l(l), r(r), val(val) {}
                              ^
teams.cpp:20:9: note: shadowed declaration is here
  int l, r, val;
         ^
teams.cpp:21:30: warning: declaration of 'l' shadows a member of 'Node' [-Wshadow]
  Node(int l, int r, int val) : l(l), r(r), val(val) {}
                              ^
teams.cpp:20:6: note: shadowed declaration is here
  int l, r, val;
      ^
teams.cpp: In function 'void expand_tree(int, int, int, int, int)':
teams.cpp:32:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s + e >> 1;
          ~~^~~
teams.cpp:35:26: warning: conversion to 'int' from 'std::vector<Node>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   tree[cnd].l = tree.size();
                 ~~~~~~~~~^~
teams.cpp:41:26: warning: conversion to 'int' from 'std::vector<Node>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   tree[cnd].r = tree.size();
                 ~~~~~~~~~^~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:66:24: warning: conversion to 'int' from 'std::vector<Node>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   root[i+1] = tree.size();
               ~~~~~~~~~^~
teams.cpp: In function 'int cal(int, int, int, int, int, int)':
teams.cpp:76:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s + e >> 1;
          ~~^~~
teams.cpp: In function 'int get_r(int, int, int, int, int)':
teams.cpp:83:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s + e >> 1, lcnt = tree[tree[cnd].l].val - tree[tree[pnd].l].val;
          ~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:97:56: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   int last = lower_bound(all(num), K[i]) - num.begin() + 1, cnt = K[i];
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:98:41: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   int rx = upper_bound(all(numx), K[i]) - numx.begin();
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
teams.cpp:102:8: warning: declaration of 'temp' shadows a previous local [-Wshadow]
    int temp = cal(1, n, last, y, root[x], root[rx]);
        ^~~~
teams.cpp:89:5: note: shadowed declaration is here
  ll temp = 0;
     ^~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 3 ms 380 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 3 ms 420 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 3 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 412 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 28004 KB Output is correct
2 Correct 128 ms 28036 KB Output is correct
3 Correct 116 ms 27972 KB Output is correct
4 Correct 121 ms 28040 KB Output is correct
5 Correct 89 ms 28740 KB Output is correct
6 Correct 89 ms 28740 KB Output is correct
7 Correct 89 ms 28740 KB Output is correct
8 Correct 89 ms 28740 KB Output is correct
9 Correct 122 ms 29000 KB Output is correct
10 Correct 94 ms 28488 KB Output is correct
11 Correct 84 ms 28548 KB Output is correct
12 Correct 86 ms 28740 KB Output is correct
13 Correct 93 ms 28996 KB Output is correct
14 Correct 93 ms 29128 KB Output is correct
15 Correct 114 ms 29124 KB Output is correct
16 Correct 112 ms 29128 KB Output is correct
17 Correct 87 ms 29128 KB Output is correct
18 Correct 90 ms 28996 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 27972 KB Output is correct
2 Correct 125 ms 27976 KB Output is correct
3 Correct 340 ms 28076 KB Output is correct
4 Correct 123 ms 27972 KB Output is correct
5 Correct 198 ms 29052 KB Output is correct
6 Correct 184 ms 29008 KB Output is correct
7 Correct 93 ms 29016 KB Output is correct
8 Correct 162 ms 29032 KB Output is correct
9 Correct 122 ms 28848 KB Output is correct
10 Correct 172 ms 28644 KB Output is correct
11 Correct 196 ms 28740 KB Output is correct
12 Correct 262 ms 28792 KB Output is correct
13 Correct 316 ms 29128 KB Output is correct
14 Correct 384 ms 29284 KB Output is correct
15 Correct 167 ms 29252 KB Output is correct
16 Correct 166 ms 29228 KB Output is correct
17 Correct 146 ms 29252 KB Output is correct
18 Correct 148 ms 29252 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 825 ms 212640 KB Output is correct
2 Correct 836 ms 212628 KB Output is correct
3 Correct 1501 ms 212876 KB Output is correct
4 Correct 813 ms 212720 KB Output is correct
5 Correct 802 ms 212656 KB Output is correct
6 Correct 783 ms 212600 KB Output is correct
7 Correct 599 ms 212688 KB Output is correct
8 Correct 728 ms 212556 KB Output is correct
9 Correct 720 ms 217192 KB Output is correct
10 Correct 738 ms 215104 KB Output is correct
11 Correct 827 ms 215452 KB Output is correct
12 Correct 975 ms 216252 KB Output is correct
13 Correct 1261 ms 217720 KB Output is correct
14 Correct 1552 ms 218928 KB Output is correct
15 Correct 842 ms 218860 KB Output is correct
16 Correct 835 ms 219300 KB Output is correct
17 Correct 687 ms 218532 KB Output is correct
18 Correct 667 ms 218320 KB Output is correct