Submission #586686

#	Time	Username	Problem	Language	Result	Execution time	Memory
586686		Tekor	Holiday (IOI14_holiday)	C++17	100 / 100	425 ms	7756 KiB

holiday

#include"holiday.h"

#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(v) v.begin(),v.end()
#define ll long long
#define pll pair <ll,ll>
const int N = 3e5 + 100;
ll t[N * 4],sum;
int t1[N * 4],p[N],c[N];
void upd(int v,int tl,int tr,int pos,ll x) {
	if(tl == tr) {
		if(x == 0) {
			t1[v] = 0;
			t[v] = 0;
			return;
		}
		t1[v] = 1;
		t[v] = x;
		return;
	}
	int tm = (tl + tr) / 2;
	if(pos <= tm)upd(v + v,tl,tm,pos,x);
	else upd(v + v + 1,tm + 1,tr,pos,x);
	t[v] = t[v + v] + t[v + v + 1];
	t1[v] = t1[v + v] + t1[v + v + 1];
}
ll get(int v,int tl,int tr,int x) {
	if(tl == tr)return t[v];
	int tm = (tl + tr) / 2;
	if(t1[v + v] >= x)return get(v + v,tl,tm,x);
	return get(v + v + 1,tm + 1,tr,x - t1[v + v]) + t[v + v];
}
int L,R,d,st,n;
ll ans;
void add(int x) {
	upd(1,0,n - 1,p[x],c[x]);
}
void del(int x) {
	upd(1,0,n - 1,p[x],0);
}
/*
5 2 7
10 2 20 30 1

*/
void calc(int l,int r,int optL,int optR) {
	if(l > r)return;
	int mid = (l + r) / 2;
	for(int i = L - 1;i >= mid;i--)add(i);
	for(int i = L;i < mid;i++)del(i);
	for(int i = R + 1;i <= optL;i++)add(i);
	for(int i = R;i > optL;i--)del(i);
	pair <ll,int> mx = mp(0,optL);
	R = optR;
	L = mid;
	for(int j = optL;j <= optR;j++) {
		if(j > optL)add(j);
		int kol = d - min(st - mid + j - mid,j - st + j - mid);
		if(mid == 0 && j == 3) {
		    //cout << kol << endl;
		}
		if(kol > 0)mx = max(mx,mp(get(1,0,n - 1,kol),j));
	}
	ans = max(ans,mx.f);
	//cout << mid << " " << mx.f << " " << mx.s << endl;
	if(l == r)return;
	calc(l,mid - 1,optL,mx.s);
	calc(mid + 1,r,mx.s,optR);
}
long long int findMaxAttraction(int NN, int start, int day, int a[]) {
	d = day;
	L = start + 1;
	R = start;
	st = start;
	n = NN;
	pii b[N];
	for(int i = 0;i < n;i++) {
		b[i] = mp(a[i],i);
		c[i] = a[i];
	}
	sort(b,b + n);
	reverse(b,b + n);
	for(int i = 0;i < n;i++) {
		p[b[i].s] = i;
	}
	calc(0,st,st,n - 1);
	return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53