제출 #1163286

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163286		peteza	휴가 (IOI14_holiday)	C++20	24 / 100	129 ms	95164 KiB

holiday

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct node {
	ll cnt, sum;
	node *l, *r;
	node(): cnt(0), sum(0), l(0), r(0) {}
	node(ll c, ll s): cnt(c), sum(s), l(0), r(0) {}
	node(node* a, node* b): cnt(a->cnt+b->cnt), sum(a->sum+b->sum), l(a), r(b) {}
};

node *roots[100005];
int pospos[100005];
int D, ST;

node* build(int l, int r) {
	//cout << l<<r<<'\n';
	if(l ==r) return new node();
	int mid = (l+r)/2;
	return new node(build(l, mid), build(mid+1, r));
}

node *upd(node *old, int l, int r, int idx, ll val) {
	if(l==r) return new node(1, val);
	int mid = (l+r)/2;
	if(idx <= mid) return new node(upd(old->l, l, mid, idx, val), old->r);
	else return new node(old->l, upd(old->r, mid+1, r, idx, val));
}

ll qr(node *oldl, node *oldr, int k) {
	if(oldr->cnt-oldl->cnt <= k) return oldr->sum-oldl->sum;
	if(oldr->r->cnt-oldl->r->cnt >= k) return qr(oldl->r, oldr->r, k);
	return qr(oldl->l, oldr->l, k-oldr->r->cnt+oldl->r->cnt) + oldr->r->sum - oldl->r->sum;
}

ll getmxbet(int l, int r, int cnt) {
	if(cnt <= 0) return 0;
	return qr(roots[l], roots[r+1], cnt);
}

ll cbans=0;

void rundp1(int l, int r, int posl, int posr) {
	if(l>r) return;
	int mid = (l+r) /2;
	pair<ll, ll> bestans(0, mid);
	for(int i=max(posl, mid); i<=posr; i++) {
		//cout<<(mid) << ' ' << i << ' ' << ( D-ST-i+2*mid) << '\n';
		bestans = max(bestans, {getmxbet(mid, i, D-ST-i+2*mid), i});
	}
	cbans = max(cbans, bestans.first);
	rundp1(l, mid-1, posl, bestans.second);
	rundp1(mid+1, r, bestans.second, posr);
}

void rundp2(int l, int r, int posl, int posr) {
	if(l>r) return;
	int mid = (l+r)/2;
	pair<ll, ll> bestans(0, mid);
	for(int i=posl; i<=min(mid, posr); i++) {
		bestans = max(bestans, {getmxbet(i, mid, D-2*mid+ST+i), i});
	}
	cbans = max(cbans, bestans.first);
	rundp2(l, mid-1, posl, bestans.second);
	rundp2(mid+1, r, bestans.second, posr);
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
	cbans=0;
	D=d; ST=start;
	roots[0] = build(0, n-1);
	vector<pair<int, int>> idxval;
	for(int i=0;i<n;i++) {
		idxval.emplace_back(attraction[i], i);
	}
	sort(idxval.begin(), idxval.end());
	for(int i=0;i<n;i++) {pospos[idxval[i].second]=i;}
	for(int i=0;i<n;i++) {
		roots[i+1] = upd(roots[i], 0, n-1, pospos[i], attraction[i]);
	}
	rundp1(0, start, 0, n-1);
	rundp2(start, n-1, 0, n-1);
	return cbans;
}

/*
int val[5] = {10, 2, 20, 30, 1};

int main() {
	cout << findMaxAttraction(5, 2, 7, val);
	//cout << qr(roots[2], roots[3], 5);
}*/

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