oj.uz

Submission #423268

# Submission time Handle Problem Language Result Execution time Memory
423268 2021-06-10T21:25:42 Z Antekb Teams (IOI15_teams) C++14
77 / 100
 2703 ms 97888 KB 
#include "teams.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb(x) push_back(x);
using namespace std;
const int N=(1<<19);
int n;
vector<int> tab[N+N];
void init(int _N, int A[], int B[]) {
	n=_N;
	for(int i=0; i<n; i++){
		//cerr<<A[i]<<" "<<B[i]<<"\n";
		A[i]+=N;
		while(A[i]){
			tab[A[i]].pb(B[i]);
			A[i]/=2;
		}
	}
	for(int i=1; i<N+N; i++)sort(tab[i].begin(), tab[i].end());
}
int count(int l, int r, int y){
	int ans=0;
	//cerr<<l<<" "<<r<<" "<<y<<" ";
	for(l+=N, r+=N; l<r; l>>=1, r>>=1){
		if(l&1){
			ans+=tab[l].end()-lower_bound(tab[l].begin(), tab[l].end(), y);
			l++;
		}
		if(r&1){
			--r;
			ans+=tab[r].end()-lower_bound(tab[r].begin(), tab[r].end(), y);
		}
	}
	//cerr<<ans<<"\n";
	return ans;
}
int dp[N], tab2[N];
vector<pair<int, int> > nowe;
int check(int k, int l){
	int L=tab2[l], R=N;
	while(L<R){
		int M=(L+R)>>1;
		if(dp[k]-count(tab2[k]+1, tab2[l]+1, M)<dp[l]){
			L=M+1;
		}
		else R=M;
	}
	/*cerr<<k<<" "<<l<<" "<<L<<"\n";
	cerr<<dp[k]<<" "<<dp[l]<<"\n";
	cerr<<tab2[k]<<" "<<tab2[l]<<"\n";
	cerr<<"\n";*/
	return L;
}
int can(int M, int K[]) {
	//cerr<<"a\n";
	sort(K, K+M);
	for(int i=0; i<M; i++)tab2[i]=K[i];
	set<int> S, S2;//S2 <0
	set<pair<int, int> > todo;
	for(int i=0; i<M; i++){
		while(todo.size() && (*todo.begin()).st<=K[i]){
			int a=(*todo.begin()).nd;
			if(S.find(a)!=S.end()){
				S.erase(S.find(a));
				S2.erase(S2.find(-a));
				if(S.lower_bound(a)!=S.end() && S2.lower_bound(a)!=S2.end()){
					int b=*S.lower_bound(a), c=-*S2.lower_bound(a);
					nowe.pb(make_pair(check(c, b), b));
				}
			}
			todo.erase(todo.begin());
			while(nowe.size()){
				todo.insert(nowe.back());
				nowe.pop_back();
			}
		}
		dp[i]=K[i]-count(0, K[i]+1, K[i]);
		//cerr<<dp[i]<<"\n";
		//for(int j=0; j<i; j++){
		if(S.size()){
			int p=*S.crbegin();
			dp[i]=max(dp[i], dp[p]+K[i]-count(K[p]+1, K[i]+1, K[i]));
		}
		
		//cerr<<i<<" a "<<dp[i]<<" "<<K[i]<<"\n";
		if(dp[i]>0)return 0;
		if(S.size()){
			int b=-*S2.begin();
			todo.insert({check(b, i), i});
		}
		S.insert(i);
		S2.insert(-i);
	}
	return 1;
}

Compilation message

teams.cpp: In function 'int count(int, int, int)':
teams.cpp:27:65: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   27 |    ans+=tab[l].end()-lower_bound(tab[l].begin(), tab[l].end(), y);
      |                                                                 ^
teams.cpp:32:65: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   32 |    ans+=tab[r].end()-lower_bound(tab[r].begin(), tab[r].end(), y);
      |                                                                 ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24908 KB Output is correct
2 Correct 17 ms 24908 KB Output is correct
3 Correct 17 ms 24908 KB Output is correct
4 Correct 17 ms 24908 KB Output is correct
5 Correct 17 ms 24908 KB Output is correct
6 Correct 18 ms 24908 KB Output is correct
7 Correct 20 ms 24940 KB Output is correct
8 Correct 20 ms 24908 KB Output is correct
9 Correct 17 ms 24908 KB Output is correct
10 Correct 17 ms 24908 KB Output is correct
11 Correct 16 ms 25024 KB Output is correct
12 Correct 20 ms 24936 KB Output is correct
13 Correct 19 ms 24908 KB Output is correct
14 Correct 18 ms 24908 KB Output is correct
15 Correct 18 ms 24916 KB Output is correct
16 Correct 18 ms 24856 KB Output is correct
17 Correct 17 ms 24908 KB Output is correct
18 Correct 19 ms 24908 KB Output is correct
19 Correct 17 ms 24940 KB Output is correct
20 Correct 17 ms 24940 KB Output is correct
21 Correct 17 ms 24928 KB Output is correct
22 Correct 18 ms 24936 KB Output is correct
23 Correct 18 ms 24832 KB Output is correct
24 Correct 20 ms 24908 KB Output is correct
25 Correct 17 ms 24908 KB Output is correct
26 Correct 17 ms 24908 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 38100 KB Output is correct
2 Correct 224 ms 38152 KB Output is correct
3 Correct 227 ms 38344 KB Output is correct
4 Correct 217 ms 38884 KB Output is correct
5 Correct 132 ms 34744 KB Output is correct
6 Correct 134 ms 34728 KB Output is correct
7 Correct 131 ms 34812 KB Output is correct
8 Correct 132 ms 34804 KB Output is correct
9 Correct 110 ms 38576 KB Output is correct
10 Correct 96 ms 36520 KB Output is correct
11 Correct 84 ms 34268 KB Output is correct
12 Correct 97 ms 34416 KB Output is correct
13 Correct 105 ms 35608 KB Output is correct
14 Correct 158 ms 36016 KB Output is correct
15 Correct 190 ms 38056 KB Output is correct
16 Correct 197 ms 37944 KB Output is correct
17 Correct 94 ms 35360 KB Output is correct
18 Correct 98 ms 35384 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 38632 KB Output is correct
2 Correct 236 ms 38528 KB Output is correct
3 Correct 312 ms 41384 KB Output is correct
4 Correct 223 ms 38932 KB Output is correct
5 Correct 438 ms 35068 KB Output is correct
6 Correct 409 ms 35068 KB Output is correct
7 Correct 138 ms 35068 KB Output is correct
8 Correct 331 ms 35048 KB Output is correct
9 Correct 113 ms 38904 KB Output is correct
10 Correct 156 ms 36596 KB Output is correct
11 Correct 143 ms 34252 KB Output is correct
12 Correct 188 ms 34620 KB Output is correct
13 Correct 538 ms 35668 KB Output is correct
14 Correct 565 ms 40044 KB Output is correct
15 Correct 304 ms 38460 KB Output is correct
16 Correct 307 ms 38540 KB Output is correct
17 Correct 200 ms 35516 KB Output is correct
18 Correct 178 ms 35568 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1374 ms 91964 KB Output is correct
2 Correct 1418 ms 91956 KB Output is correct
3 Correct 1808 ms 97888 KB Output is correct
4 Correct 1424 ms 92844 KB Output is correct
5 Correct 1578 ms 73152 KB Output is correct
6 Correct 1414 ms 72872 KB Output is correct
7 Correct 647 ms 73276 KB Output is correct
8 Correct 1218 ms 73068 KB Output is correct
9 Correct 568 ms 93488 KB Output is correct
10 Correct 527 ms 71660 KB Output is correct
11 Correct 511 ms 69156 KB Output is correct
12 Correct 725 ms 69708 KB Output is correct
13 Correct 1793 ms 77532 KB Output is correct
14 Correct 2703 ms 94156 KB Output is correct
15 Correct 1360 ms 89640 KB Output is correct
16 Incorrect 1382 ms 88688 KB Output isn't correct
17 Halted 0 ms 0 KB -