oj.uz

Submission #286684

# Submission time Handle Problem Language Result Execution time Memory
286684 2020-08-30T18:05:14 Z Atill83 Teams (IOI15_teams) C++14
77 / 100
 2019 ms 128880 KB 
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
int n;
const int MAXN = (int) 5e5 + 5;

vector<int> t[4*MAXN];

void add(int v, int tl, int tr, int val, int pos){
	if(tl == tr){
		t[v].push_back(val);
	}else{
		int tm = (tl + tr) / 2;
		if(pos <= tm){
			add(2*v, tl, tm, val, pos);
		}else{
			add(2*v+1, tm + 1, tr, val, pos);
		}
		t[v].push_back(val);
	}
}

int que(int v, int tl, int tr, int l, int r, int val){
	if(l > r) return 0;
	if(tl == l && tr == r){
		return t[v].end() - lower_bound(t[v].begin(), t[v].end(), val);
	}else{
		int tm = (tl + tr) / 2;
		return que(2*v, tl, tm, l, min(tm, r), val) + que(2*v+1, tm + 1, tr, max(tm + 1, l), r, val);
	}
}



void init(int N, int A[], int B[]) {
	n = N;
	for(int i = 0; i < N; i++){
		add(1, 1, N, B[i], A[i]); 
	}
	for(int i = 1; i < 4*MAXN; i++) sort(t[i].begin(), t[i].end());
}
int dp[MAXN];

int can(int M, int K[]) {
	int N = n;
	sort(K, K + M);
	vector<int> lst;
	dp[0] = que(1, 1, N , 1, K[0], K[0]) - K[0];
	if(dp[0] < 0) return 0;
	lst.push_back(0);
	for(int i = 1; i < M; i++){
		dp[i] = que(1, 1, N, 1, K[i], K[i]) - K[i];
		while(lst.size() > 1){
			int cur = lst.back();
			lst.pop_back();
			int deg1 = dp[cur] + que(1, 1, N, K[cur] + 1, K[i], K[i]);
			int deg2 = dp[lst.back()] + que(1, 1, N , K[lst.back()] + 1, K[i], K[i]);
			if(deg2 > deg1){
				lst.push_back(cur);
				break;
			}
		}
		dp[i] = min(dp[i], dp[lst.back()] + que(1, 1, N, K[lst.back()] + 1, K[i], K[i]) - K[i]);
		lst.push_back(i);
		if(dp[i] < 0) return 0;
	}
	return 1;
}

Compilation message

teams.cpp: In function 'int que(int, int, int, int, int, int)':
teams.cpp:26:21: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   26 |   return t[v].end() - lower_bound(t[v].begin(), t[v].end(), val);
      |          ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47232 KB Output is correct
2 Correct 35 ms 47232 KB Output is correct
3 Correct 35 ms 47352 KB Output is correct
4 Correct 35 ms 47232 KB Output is correct
5 Correct 35 ms 47352 KB Output is correct
6 Correct 36 ms 47352 KB Output is correct
7 Correct 36 ms 47352 KB Output is correct
8 Correct 36 ms 47360 KB Output is correct
9 Correct 35 ms 47348 KB Output is correct
10 Correct 35 ms 47232 KB Output is correct
11 Correct 35 ms 47348 KB Output is correct
12 Correct 36 ms 47360 KB Output is correct
13 Correct 36 ms 47360 KB Output is correct
14 Correct 36 ms 47360 KB Output is correct
15 Correct 36 ms 47360 KB Output is correct
16 Correct 36 ms 47232 KB Output is correct
17 Correct 36 ms 47224 KB Output is correct
18 Correct 36 ms 47232 KB Output is correct
19 Correct 36 ms 47232 KB Output is correct
20 Correct 36 ms 47336 KB Output is correct
21 Correct 35 ms 47232 KB Output is correct
22 Correct 35 ms 47312 KB Output is correct
23 Correct 36 ms 47232 KB Output is correct
24 Correct 36 ms 47340 KB Output is correct
25 Correct 36 ms 47232 KB Output is correct
26 Correct 38 ms 47224 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 61032 KB Output is correct
2 Correct 249 ms 61220 KB Output is correct
3 Correct 255 ms 61244 KB Output is correct
4 Correct 247 ms 61676 KB Output is correct
5 Correct 138 ms 57020 KB Output is correct
6 Correct 138 ms 57148 KB Output is correct
7 Correct 137 ms 57140 KB Output is correct
8 Correct 139 ms 57148 KB Output is correct
9 Correct 98 ms 56592 KB Output is correct
10 Correct 93 ms 56280 KB Output is correct
11 Correct 90 ms 55944 KB Output is correct
12 Correct 91 ms 56600 KB Output is correct
13 Correct 120 ms 58196 KB Output is correct
14 Correct 166 ms 58652 KB Output is correct
15 Correct 219 ms 60904 KB Output is correct
16 Correct 213 ms 60652 KB Output is correct
17 Correct 108 ms 58336 KB Output is correct
18 Correct 108 ms 58088 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 61800 KB Output is correct
2 Correct 249 ms 61800 KB Output is correct
3 Correct 393 ms 65256 KB Output is correct
4 Correct 242 ms 61848 KB Output is correct
5 Correct 245 ms 57660 KB Output is correct
6 Correct 232 ms 57660 KB Output is correct
7 Correct 147 ms 57532 KB Output is correct
8 Correct 234 ms 57672 KB Output is correct
9 Correct 98 ms 57112 KB Output is correct
10 Correct 110 ms 56640 KB Output is correct
11 Correct 115 ms 56452 KB Output is correct
12 Correct 177 ms 57152 KB Output is correct
13 Correct 320 ms 59216 KB Output is correct
14 Correct 409 ms 62816 KB Output is correct
15 Correct 286 ms 61796 KB Output is correct
16 Correct 276 ms 61676 KB Output is correct
17 Correct 178 ms 58460 KB Output is correct
18 Correct 158 ms 58712 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1517 ms 122080 KB Output is correct
2 Correct 1487 ms 122328 KB Output is correct
3 Correct 1926 ms 128880 KB Output is correct
4 Correct 1497 ms 121944 KB Output is correct
5 Correct 925 ms 100060 KB Output is correct
6 Correct 899 ms 99928 KB Output is correct
7 Correct 673 ms 100060 KB Output is correct
8 Correct 913 ms 99892 KB Output is correct
9 Correct 394 ms 98288 KB Output is correct
10 Correct 394 ms 94468 KB Output is correct
11 Correct 443 ms 95016 KB Output is correct
12 Correct 615 ms 96300 KB Output is correct
13 Correct 1278 ms 106400 KB Output is correct
14 Correct 2019 ms 124284 KB Output is correct
15 Correct 1329 ms 119496 KB Output is correct
16 Incorrect 1338 ms 118584 KB Output isn't correct
17 Halted 0 ms 0 KB -