oj.uz

Submission #298015

# Submission time Handle Problem Language Result Execution time Memory
298015 2020-09-12T09:47:08 Z miss_robot Holiday (IOI14_holiday) C++14
100 / 100
 2195 ms 60448 KB 
#include <bits/stdc++.h>
#include"holiday.h"

#pragma GCC optimize("Ofast")
#define ll long long

using namespace std;

const int L = 131072;
vector<int> t[2*L];
vector<ll> p[2*L];

ll qry(int i, int l, int r, int k){
	if(k <= 0) return 0;
	if(i >= L) return p[i][k-1];
	int a = lower_bound(t[i].begin(), t[i].end(), l)-t[i].begin(),
	    b = upper_bound(t[i].begin(), t[i].end(), r)-t[i].begin();
	if(b-a == k) return p[i][b-1] - (a?p[i][a-1]:0);
	a = lower_bound(t[i<<1|1].begin(), t[i<<1|1].end(), l)-t[i<<1|1].begin(),
	  b = upper_bound(t[i<<1|1].begin(), t[i<<1|1].end(), r)-t[i<<1|1].begin();
	return qry(i<<1, l, r, k-(b-a)) + qry(i<<1|1, l, r, min(k, b-a));
}

ll sum(int l, int r, int k){ // summe der k maximalen elemente im intervall [l, r]
	k = min(k, r-l+1);
	return qry(1, l, r, k);
}

void div1(int s, int d, int l, int r, int optl, int optr, ll& sol){ // erst nach rechts dann nach links
	if(l > r) return;
	ll best = -1;
	int opt = -1, m = (l+r)/2;
	for(int i = min(optr, max(optl, (d+s+2*m-1)/3)); i <= optr; i++){
		ll temp = sum(m, i, d-2*(i-s)-(s-m));
		if(temp > best) best = temp, opt = i;
	}
	sol = max(sol, best);
	div1(s, d, l, m-1, optl, opt, sol), div1(s, d, m+1, r, opt, optr, sol);
}

void div2(int s, int d, int l, int r, int optl, int optr, ll& sol){ // erst nach links dann nach rechts
	if(l > r) return;
	ll best = -1;
	int opt = -1, m = (l+r)/2;
	for(int i = optl; i <= max(optl, min(optr, (s-d+2*m+1)/3)); i++){
		ll temp = sum(i, m, d-2*(s-i)-(m-s));
		if(temp > best) best = temp, opt = i;
	}
	sol = max(sol, best);
	div2(s, d, l, m-1, optl, opt, sol), div2(s, d, m+1, r, opt, optr, sol);
}

ll findMaxAttraction(int n, int start, int d, int attraction[]){
	map< int, vector<int> > m;
	for(int i = 0; i < n; i++) m[attraction[i]].push_back(i);
	int k = L, j;
	for(auto& tmp : m){
		t[k] = tmp.second;
		for(auto& x : t[k]) p[k].push_back(tmp.first+(p[k].empty()?0:p[k].back()));
		k++;
	}
	for(int i = L-1; i; i--){
		j = k = 0;
		while(j < (int)t[i<<1].size() && k < (int)t[i<<1|1].size()){
			if(t[i<<1][j] < t[i<<1|1][k]) t[i].push_back(t[i<<1][j++]);
			else t[i].push_back(t[i<<1|1][k++]);
			p[i].push_back((j?p[i<<1][j-1]:0)+(k?p[i<<1|1][k-1]:0));
		}
		while(j < (int)t[i<<1].size()){
			t[i].push_back(t[i<<1][j++]);
			p[i].push_back((j?p[i<<1][j-1]:0)+(k?p[i<<1|1][k-1]:0));
		}
		while(k < (int)t[i<<1|1].size()){
			t[i].push_back(t[i<<1|1][k++]);
			p[i].push_back((j?p[i<<1][j-1]:0)+(k?p[i<<1|1][k-1]:0));
		}
	}
	ll sol = 0;
	div1(start, d, 0, start, start, n-1, sol), div2(start, d, start, n-1, 0, start, sol);
	return sol;
}

Compilation message

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:59:13: warning: unused variable 'x' [-Wunused-variable]
   59 |   for(auto& x : t[k]) p[k].push_back(tmp.first+(p[k].empty()?0:p[k].back()));
      |             ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12672 KB Output is correct
2 Correct 9 ms 12672 KB Output is correct
3 Correct 10 ms 12672 KB Output is correct
4 Correct 11 ms 12672 KB Output is correct
5 Correct 10 ms 12672 KB Output is correct
6 Correct 10 ms 12644 KB Output is correct
7 Correct 10 ms 12800 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 37784 KB Output is correct
2 Correct 154 ms 37740 KB Output is correct
3 Correct 159 ms 37784 KB Output is correct
4 Correct 155 ms 37740 KB Output is correct
5 Correct 192 ms 35420 KB Output is correct
6 Correct 28 ms 20404 KB Output is correct
7 Correct 85 ms 25264 KB Output is correct
8 Correct 118 ms 28784 KB Output is correct
9 Correct 22 ms 17908 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 13952 KB Output is correct
2 Correct 12 ms 13568 KB Output is correct
3 Correct 14 ms 13952 KB Output is correct
4 Correct 46 ms 14072 KB Output is correct
5 Correct 41 ms 13824 KB Output is correct
6 Correct 13 ms 13056 KB Output is correct
7 Correct 17 ms 13056 KB Output is correct
8 Correct 18 ms 13056 KB Output is correct
9 Correct 17 ms 12860 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 38380 KB Output is correct
2 Correct 191 ms 57388 KB Output is correct
3 Correct 401 ms 32752 KB Output is correct
4 Correct 36 ms 13952 KB Output is correct
5 Correct 18 ms 13056 KB Output is correct
6 Correct 18 ms 13056 KB Output is correct
7 Correct 17 ms 12928 KB Output is correct
8 Correct 2180 ms 60404 KB Output is correct
9 Correct 2195 ms 60448 KB Output is correct