oj.uz

Submission #387033

# Submission time Handle Problem Language Result Execution time Memory
387033 2021-04-07T20:10:03 Z alireza_kaviani Holiday (IOI14_holiday) C++11
100 / 100
 460 ms 20576 KB 
#include <bits/stdc++.h>
#include"holiday.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define all(x)		(x).begin() , (x).end()
#define X			first
#define Y			second

const int MAXN = (1 << 20) + 10;
const int LOG = 20;
const ll INF = 1e18;

ll n , d , start , ql , qr , ans , A[MAXN] , pos[MAXN] , fen[2][MAXN];

void add(int ind , int x , int val){
	for(x++; x < MAXN ; x += x & -x)	fen[ind][x] += val;
}

ll get(int x){
	ll cur = 0 , res = 0;
	for(int i = LOG - 1 ; i >= 0 ; i--){
		int nxt = (cur + (1 << i));
		if(fen[0][nxt] <= x){
			x -= fen[0][nxt];
			res += fen[1][nxt];
			cur = nxt;
		}
	}
	return res;
}

void ins(int x , int f){
	add(0 , pos[x] , 1 * f);
	add(1 , pos[x] , A[x] * f);
}

ll calc(int l , int r){
	while(l < ql)	ins(--ql , 1);
	while(qr < r)	ins(++qr , 1);
	while(ql < l)	ins(ql++ , -1);
	while(r < qr)	ins(qr-- , -1);
	return get(d - (r - l) - (r - start));
}

void solve(int l , int r , int optl , int optr){
	if(r < l)	return;
	int mid = l + r >> 1;
	ll mx = -1 , opt = -1;
	for(int i = optl ; i <= mid && i <= optr ; i++){
		ll cost = calc(i , mid);
		assert(fen[0][1 << LOG] == mid - i + 1);
		if(mx <= cost){
			mx = cost;
			opt = i;
		}
	}
	ans = max(ans , mx);
	solve(l , mid - 1 , optl , opt);
	solve(mid + 1 , r , opt , optr);
}

long long int findMaxAttraction(int N, int START, int D, int attract[]) {
	n = N; start = START; d = D;
	vector<pii> vec;
	for(int i = 0 ; i < n ; i++){
		A[i] = attract[i];
		vec.push_back({A[i] , i});
	}
	sort(all(vec) , greater<pii>());
	for(int i = 0 ; i < n ; i++)	pos[vec[i].Y] = i;
	ql = 0 , qr = -1; solve(start , n - 1 , 0 , start);
	reverse(A , A + n);
	reverse(pos , pos + n);
	fill(fen[0] , fen[0] + MAXN , 0);
	fill(fen[1] , fen[1] + MAXN , 0); start = n - start - 1;
	ql = 0 , qr = -1; solve(start , n - 1 , 0 , start);
	return ans;
}

Compilation message

holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:50:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |  int mid = l + r >> 1;
      |            ~~^~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 19552 KB Output is correct
2 Correct 101 ms 19552 KB Output is correct
3 Correct 100 ms 19624 KB Output is correct
4 Correct 101 ms 19552 KB Output is correct
5 Correct 111 ms 19424 KB Output is correct
6 Correct 40 ms 17640 KB Output is correct
7 Correct 65 ms 18276 KB Output is correct
8 Correct 77 ms 18532 KB Output is correct
9 Correct 32 ms 17384 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16876 KB Output is correct
2 Correct 13 ms 16876 KB Output is correct
3 Correct 12 ms 16876 KB Output is correct
4 Correct 19 ms 16876 KB Output is correct
5 Correct 18 ms 16876 KB Output is correct
6 Correct 12 ms 16748 KB Output is correct
7 Correct 12 ms 16748 KB Output is correct
8 Correct 12 ms 16748 KB Output is correct
9 Correct 13 ms 16748 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 19632 KB Output is correct
2 Correct 103 ms 19636 KB Output is correct
3 Correct 181 ms 18148 KB Output is correct
4 Correct 19 ms 16876 KB Output is correct
5 Correct 13 ms 16748 KB Output is correct
6 Correct 13 ms 16748 KB Output is correct
7 Correct 12 ms 16748 KB Output is correct
8 Correct 460 ms 20448 KB Output is correct
9 Correct 456 ms 20576 KB Output is correct