oj.uz

Submission #423267

# Submission time Handle Problem Language Result Execution time Memory
423267 2021-06-10T21:23:38 Z Antekb Teams (IOI15_teams) C++14
77 / 100
 1702 ms 101712 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;
		tab[A[i]].pb(B[i]);
	}
	for(int i=N; i<N+N; i++){
		if(tab[i].size())sort(tab[i].begin(), tab[i].end());
	}
	for(int i=N-1;i>0; i--){
		int wsk=0, wsk2=0;
		while(wsk<tab[i+i].size() || wsk2<tab[i+i+1].size()){
			if(wsk2==tab[i+i+1].size() || (wsk<tab[i+i].size() && tab[i+i+1][wsk2]>tab[i+i][wsk])){
				tab[i].pb(tab[i+i][wsk++]);
			}
			else tab[i].pb(tab[i+i+1][wsk2++]);
		}
		assert(tab[i].size()==tab[i+i+1].size()+tab[i+i].size());
		for(int j=1; j<tab[i].size(); j++)assert(tab[i][j]>=tab[i][j-1]);
	}
}
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 'void init(int, int*, int*)':
teams.cpp:22:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   while(wsk<tab[i+i].size() || wsk2<tab[i+i+1].size()){
      |         ~~~^~~~~~~~~~~~~~~~
teams.cpp:22:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   while(wsk<tab[i+i].size() || wsk2<tab[i+i+1].size()){
      |                                ~~~~^~~~~~~~~~~~~~~~~~
teams.cpp:23:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |    if(wsk2==tab[i+i+1].size() || (wsk<tab[i+i].size() && tab[i+i+1][wsk2]>tab[i+i][wsk])){
      |       ~~~~^~~~~~~~~~~~~~~~~~~
teams.cpp:23:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |    if(wsk2==tab[i+i+1].size() || (wsk<tab[i+i].size() && tab[i+i+1][wsk2]>tab[i+i][wsk])){
      |                                   ~~~^~~~~~~~~~~~~~~~
teams.cpp:29:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(int j=1; j<tab[i].size(); j++)assert(tab[i][j]>=tab[i][j-1]);
      |                ~^~~~~~~~~~~~~~
teams.cpp: In function 'int count(int, int, int)':
teams.cpp:37:65: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   37 |    ans+=tab[l].end()-lower_bound(tab[l].begin(), tab[l].end(), y);
      |                                                                 ^
teams.cpp:42:65: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   42 |    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 20 ms 24908 KB Output is correct
2 Correct 20 ms 24936 KB Output is correct
3 Correct 20 ms 24896 KB Output is correct
4 Correct 21 ms 24872 KB Output is correct
5 Correct 24 ms 24908 KB Output is correct
6 Correct 21 ms 25036 KB Output is correct
7 Correct 21 ms 24952 KB Output is correct
8 Correct 21 ms 24908 KB Output is correct
9 Correct 20 ms 24952 KB Output is correct
10 Correct 21 ms 24908 KB Output is correct
11 Correct 20 ms 24928 KB Output is correct
12 Correct 21 ms 24952 KB Output is correct
13 Correct 21 ms 24968 KB Output is correct
14 Correct 20 ms 24908 KB Output is correct
15 Correct 21 ms 24908 KB Output is correct
16 Correct 20 ms 24900 KB Output is correct
17 Correct 20 ms 24908 KB Output is correct
18 Correct 21 ms 24908 KB Output is correct
19 Correct 24 ms 24908 KB Output is correct
20 Correct 20 ms 24940 KB Output is correct
21 Correct 20 ms 24908 KB Output is correct
22 Correct 20 ms 24908 KB Output is correct
23 Correct 22 ms 24924 KB Output is correct
24 Correct 22 ms 24900 KB Output is correct
25 Correct 20 ms 24876 KB Output is correct
26 Correct 21 ms 24836 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 39212 KB Output is correct
2 Correct 78 ms 39096 KB Output is correct
3 Correct 77 ms 39120 KB Output is correct
4 Correct 82 ms 39992 KB Output is correct
5 Correct 46 ms 35580 KB Output is correct
6 Correct 39 ms 35580 KB Output is correct
7 Correct 38 ms 35480 KB Output is correct
8 Correct 37 ms 35512 KB Output is correct
9 Correct 66 ms 39176 KB Output is correct
10 Correct 54 ms 36772 KB Output is correct
11 Correct 40 ms 34492 KB Output is correct
12 Correct 41 ms 34704 KB Output is correct
13 Correct 52 ms 35872 KB Output is correct
14 Correct 65 ms 36804 KB Output is correct
15 Correct 73 ms 38996 KB Output is correct
16 Correct 72 ms 39048 KB Output is correct
17 Correct 42 ms 35528 KB Output is correct
18 Correct 42 ms 35444 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 39476 KB Output is correct
2 Correct 84 ms 39416 KB Output is correct
3 Correct 208 ms 42104 KB Output is correct
4 Correct 79 ms 39824 KB Output is correct
5 Correct 357 ms 35592 KB Output is correct
6 Correct 317 ms 35464 KB Output is correct
7 Correct 44 ms 35484 KB Output is correct
8 Correct 241 ms 35708 KB Output is correct
9 Correct 78 ms 39176 KB Output is correct
10 Correct 110 ms 37256 KB Output is correct
11 Correct 101 ms 34952 KB Output is correct
12 Correct 146 ms 34800 KB Output is correct
13 Correct 430 ms 36080 KB Output is correct
14 Correct 436 ms 40548 KB Output is correct
15 Correct 198 ms 39100 KB Output is correct
16 Correct 183 ms 39128 KB Output is correct
17 Correct 148 ms 35776 KB Output is correct
18 Correct 154 ms 35512 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 94964 KB Output is correct
2 Correct 443 ms 95092 KB Output is correct
3 Correct 753 ms 99576 KB Output is correct
4 Correct 388 ms 95732 KB Output is correct
5 Correct 943 ms 74488 KB Output is correct
6 Correct 869 ms 74372 KB Output is correct
7 Correct 114 ms 74432 KB Output is correct
8 Correct 706 ms 74404 KB Output is correct
9 Correct 271 ms 94656 KB Output is correct
10 Correct 278 ms 72948 KB Output is correct
11 Correct 249 ms 70472 KB Output is correct
12 Correct 471 ms 70952 KB Output is correct
13 Correct 1453 ms 77776 KB Output is correct
14 Correct 1702 ms 101712 KB Output is correct
15 Correct 617 ms 96996 KB Output is correct
16 Incorrect 592 ms 96532 KB Output isn't correct
17 Halted 0 ms 0 KB -