oj.uz

Submission #406382

# Submission time Handle Problem Language Result Execution time Memory
406382 2021-05-17T13:53:34 Z pure_mem Teams (IOI15_teams) C++14
77 / 100
 1515 ms 368532 KB 
#include "teams.h"
#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int MAXN = 5e5 + 12, BS = 300;

struct node{
	int val = 0;
	node *l = nullptr, *r = nullptr;
	node(int _val = 0, node* _l = nullptr, node* _r = nullptr){
		val = _val, l = _l, r = _r;
	}
};
int getVal(node* v){
	return v ? v->val: 0;
}
node* upd(node* v, int tl, int tr, int pos, int val){
	if(tl == tr) return new node(getVal(v) + val);
	int tm = (tl + tr) / 2;
	if(pos <= tm) v = new node(0, upd(v ? v->l: v, tl, tm, pos, val), v ? v->r: v);
	else v = new node(0, v ? v->l: v, upd(v ? v->r: v, tm + 1, tr, pos, val));
	v->val = getVal(v->l) + getVal(v->r);
	return v;
}
int get(node* v, int tl, int tr, int l, int r){
	if(tl > r || l > tr) return 0;
	if(tl >= l && tr <= r) return getVal(v);
	int tm = (tl + tr) / 2;
	return (v->l ? get(v->l, tl, tm, l, r): 0) + (v->r ? get(v->r, tm + 1, tr, l, r): 0);
}
node* root[MAXN];

int n, dp[MAXN];
vector< int > rv[MAXN], mine[MAXN];

void init(int N, int A[], int B[]) {
	n = N, root[0] = new node();
	for(int i = 0;i < n;i++)
		rv[n - B[i] + 1].push_back(A[i]), mine[A[i]].push_back(B[i]);
	for(int i = 1;i <= n;i++){
		root[i] = root[i - 1];
		for(int v: rv[i]){
			root[i] = upd(root[i], 1, n, v, 1);
		}
	}			
}

int cf(int l, int r){
	return get(root[n - r + 1], 1, n, l, r);
}

int can(int M, int K[]) {
	sort(K, K + M);
  	vector< int > opt; int ptr = -1;
  	for(int i = 0;i < M;i++){
  		dp[i] = cf(1, K[i]) - K[i];
  		while(ptr >= 1 && dp[opt[ptr - 1]] + cf(K[opt[ptr - 1]] + 1, K[i]) < dp[opt[ptr]] + cf(K[opt[ptr]] + 1, K[i])) opt.pop_back(), ptr--;
  		if(ptr >= 0) dp[i] = min(dp[i], dp[opt[ptr]] + cf(K[opt[ptr]] + 1, K[i]) - K[i]);
  		ptr++, opt.push_back(i);
  		if(dp[i] < 0) return 0;
  	}
	return 1;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23776 KB Output is correct
2 Correct 14 ms 23756 KB Output is correct
3 Correct 14 ms 23764 KB Output is correct
4 Correct 14 ms 23812 KB Output is correct
5 Correct 14 ms 23756 KB Output is correct
6 Correct 15 ms 23884 KB Output is correct
7 Correct 14 ms 23756 KB Output is correct
8 Correct 14 ms 23820 KB Output is correct
9 Correct 14 ms 23784 KB Output is correct
10 Correct 16 ms 23756 KB Output is correct
11 Correct 13 ms 23792 KB Output is correct
12 Correct 15 ms 23756 KB Output is correct
13 Correct 14 ms 23756 KB Output is correct
14 Correct 14 ms 23792 KB Output is correct
15 Correct 14 ms 23756 KB Output is correct
16 Correct 14 ms 23812 KB Output is correct
17 Correct 14 ms 23756 KB Output is correct
18 Correct 16 ms 23756 KB Output is correct
19 Correct 15 ms 23808 KB Output is correct
20 Correct 14 ms 23708 KB Output is correct
21 Correct 14 ms 23804 KB Output is correct
22 Correct 16 ms 23764 KB Output is correct
23 Correct 14 ms 23756 KB Output is correct
24 Correct 16 ms 23804 KB Output is correct
25 Correct 15 ms 23756 KB Output is correct
26 Correct 14 ms 23756 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 84280 KB Output is correct
2 Correct 162 ms 84260 KB Output is correct
3 Correct 167 ms 84240 KB Output is correct
4 Correct 192 ms 84672 KB Output is correct
5 Correct 98 ms 81860 KB Output is correct
6 Correct 99 ms 81920 KB Output is correct
7 Correct 100 ms 81840 KB Output is correct
8 Correct 109 ms 81872 KB Output is correct
9 Correct 115 ms 83136 KB Output is correct
10 Correct 103 ms 82792 KB Output is correct
11 Correct 94 ms 82488 KB Output is correct
12 Correct 94 ms 82396 KB Output is correct
13 Correct 123 ms 82248 KB Output is correct
14 Correct 121 ms 83380 KB Output is correct
15 Correct 154 ms 84016 KB Output is correct
16 Correct 147 ms 84064 KB Output is correct
17 Correct 123 ms 82604 KB Output is correct
18 Correct 102 ms 82632 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 84676 KB Output is correct
2 Correct 173 ms 84668 KB Output is correct
3 Correct 255 ms 87616 KB Output is correct
4 Correct 163 ms 84676 KB Output is correct
5 Correct 154 ms 82276 KB Output is correct
6 Correct 148 ms 82244 KB Output is correct
7 Correct 106 ms 82276 KB Output is correct
8 Correct 137 ms 82260 KB Output is correct
9 Correct 125 ms 83128 KB Output is correct
10 Correct 143 ms 83040 KB Output is correct
11 Correct 145 ms 82948 KB Output is correct
12 Correct 166 ms 82764 KB Output is correct
13 Correct 226 ms 82764 KB Output is correct
14 Correct 297 ms 85828 KB Output is correct
15 Correct 195 ms 84404 KB Output is correct
16 Correct 208 ms 84548 KB Output is correct
17 Correct 151 ms 83060 KB Output is correct
18 Correct 149 ms 83044 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1187 ms 362820 KB Output is correct
2 Correct 1204 ms 362816 KB Output is correct
3 Correct 1491 ms 368532 KB Output is correct
4 Correct 1236 ms 362692 KB Output is correct
5 Correct 629 ms 350156 KB Output is correct
6 Correct 628 ms 350128 KB Output is correct
7 Correct 522 ms 350076 KB Output is correct
8 Correct 625 ms 350052 KB Output is correct
9 Correct 586 ms 351656 KB Output is correct
10 Correct 570 ms 349724 KB Output is correct
11 Correct 582 ms 349408 KB Output is correct
12 Correct 677 ms 349452 KB Output is correct
13 Correct 1158 ms 351080 KB Output is correct
14 Correct 1515 ms 363292 KB Output is correct
15 Correct 1048 ms 360024 KB Output is correct
16 Incorrect 1089 ms 359860 KB Output isn't correct
17 Halted 0 ms 0 KB -