oj.uz

Submission #1108890

# Submission time Handle Problem Language Result Execution time Memory
1108890 2024-11-05T15:37:12 Z Pioneer Teams (IOI15_teams) C++17
77 / 100
 4000 ms 127344 KB 
#include "teams.h"
#include "bits/stdc++.h"

using namespace std;

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")

#define pb push_back
#define all(v) v.begin(),v.end()
#define ub upper_bound
#define lb lower_bound
#define sz(s) (int)s.size()

const int MAX=5e5+10;

int n;
vector<int> b[MAX];

struct segtree1{
	vector<int> t[4*MAX];

	void build(){
		for(int i=n;i<n+n;i++)sort(all(t[i]));
		for(int v=n-1;v>=1;v--){
			t[v].resize(sz(t[2*v])+sz(t[2*v+1]));
			merge(all(t[2*v]),all(t[2*v+1]),t[v].begin());
		}
	}
	
	int get(int l,int r,int x){
		int res=0;
		l+=n,r+=n;
		for(;l<r;l/=2,r/=2){
			if(l&1){
				res+=sz(t[l])-(lb(all(t[l]),x)-t[l].begin());
				l++;
			}
			if(r&1){
				r--;
				res+=sz(t[r])-(lb(all(t[r]),x)-t[r].begin());
			}
		}
		return res;
	}
}z;

void init(int N, int A[], int B[]){
	n=N;
	for(int i=0;i<N;i++){
		z.t[A[i]+N-1].pb(B[i]);
	}
	z.build();
}

int cnt[MAX],dp[MAX];

int can(int M, int K[]){
	sort(K,K+M);
	int sum=0;
	vector<int> a;
	for(int i=0;i<M;i++){
		sum+=K[i];
		cnt[K[i]]++;
		a.pb(K[i]);
	}
	if(sum>n)return 0;
	sort(all(a));
	a.erase(unique(all(a)),a.end());
	for(int x:a){
		dp[x]=z.get(0,x,x)-cnt[x]*x;
		for(int y:a){
			if(y>=x)break;
			dp[x]=min(dp[x],dp[y]+z.get(y,x,x)-cnt[x]*x);
		}
		if(dp[x]<0){
			for(int y:a)cnt[y]=0;
			return 0;
		}
	}
	for(int y:a)cnt[y]=0;
	return 1;
}

Compilation message

teams.cpp: In member function 'int segtree1::get(int, int, int)':
teams.cpp:36:48: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   36 |     res+=sz(t[l])-(lb(all(t[l]),x)-t[l].begin());
      |                                                ^
teams.cpp:41:48: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   41 |     res+=sz(t[r])-(lb(all(t[r]),x)-t[r].begin());
      |                                                ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 62800 KB Output is correct
2 Correct 12 ms 62656 KB Output is correct
3 Correct 11 ms 62880 KB Output is correct
4 Correct 11 ms 62816 KB Output is correct
5 Correct 12 ms 62668 KB Output is correct
6 Correct 12 ms 62876 KB Output is correct
7 Correct 12 ms 62800 KB Output is correct
8 Correct 12 ms 62800 KB Output is correct
9 Correct 13 ms 62908 KB Output is correct
10 Correct 14 ms 62800 KB Output is correct
11 Correct 11 ms 62800 KB Output is correct
12 Correct 12 ms 62800 KB Output is correct
13 Correct 12 ms 62800 KB Output is correct
14 Correct 11 ms 62800 KB Output is correct
15 Correct 12 ms 62800 KB Output is correct
16 Correct 11 ms 62800 KB Output is correct
17 Correct 12 ms 62800 KB Output is correct
18 Correct 11 ms 62832 KB Output is correct
19 Correct 12 ms 62968 KB Output is correct
20 Correct 12 ms 62736 KB Output is correct
21 Correct 16 ms 62800 KB Output is correct
22 Correct 13 ms 62800 KB Output is correct
23 Correct 11 ms 62800 KB Output is correct
24 Correct 11 ms 62800 KB Output is correct
25 Correct 12 ms 62800 KB Output is correct
26 Correct 11 ms 62900 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 73296 KB Output is correct
2 Correct 47 ms 73296 KB Output is correct
3 Correct 48 ms 73232 KB Output is correct
4 Correct 50 ms 74452 KB Output is correct
5 Correct 36 ms 70736 KB Output is correct
6 Correct 25 ms 70480 KB Output is correct
7 Correct 22 ms 70480 KB Output is correct
8 Correct 22 ms 70528 KB Output is correct
9 Correct 24 ms 70856 KB Output is correct
10 Correct 23 ms 70628 KB Output is correct
11 Correct 23 ms 70344 KB Output is correct
12 Correct 26 ms 70356 KB Output is correct
13 Correct 26 ms 70604 KB Output is correct
14 Correct 39 ms 72040 KB Output is correct
15 Correct 45 ms 73120 KB Output is correct
16 Correct 44 ms 73104 KB Output is correct
17 Correct 26 ms 70736 KB Output is correct
18 Correct 25 ms 70736 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 73824 KB Output is correct
2 Correct 49 ms 73812 KB Output is correct
3 Correct 144 ms 76848 KB Output is correct
4 Correct 49 ms 74440 KB Output is correct
5 Correct 2456 ms 70952 KB Output is correct
6 Correct 1748 ms 70956 KB Output is correct
7 Correct 29 ms 70736 KB Output is correct
8 Correct 1411 ms 70840 KB Output is correct
9 Correct 23 ms 70856 KB Output is correct
10 Correct 27 ms 70856 KB Output is correct
11 Correct 52 ms 70516 KB Output is correct
12 Correct 1008 ms 70716 KB Output is correct
13 Correct 397 ms 71108 KB Output is correct
14 Correct 173 ms 75080 KB Output is correct
15 Correct 74 ms 73488 KB Output is correct
16 Correct 78 ms 73544 KB Output is correct
17 Correct 77 ms 71240 KB Output is correct
18 Correct 76 ms 71108 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 121256 KB Output is correct
2 Correct 212 ms 121160 KB Output is correct
3 Correct 535 ms 127344 KB Output is correct
4 Correct 213 ms 122396 KB Output is correct
5 Execution timed out 4072 ms 105076 KB Time limit exceeded
6 Halted 0 ms 0 KB -