oj.uz

Submission #254822

# Submission time Handle Problem Language Result Execution time Memory
254822 2020-07-30T16:39:33 Z b00n0rp Holiday (IOI14_holiday) C++17
100 / 100
 911 ms 8936 KB 
#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
#define F first
#define S second
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define pb push_back

const int MX = 100005;
int ans = 0,N,D,S;
pii a[MX];

struct node{
	int cnt,sum;
} seg[4*MX];

void upd(int ind,int l,int r,int pos,int val,int type){
	if(pos < l or pos > r) return;
	if(l == r){
		seg[ind].cnt = type;
		seg[ind].sum = val*type;
		return;
	}
	int m = (l+r)/2;
	upd(2*ind,l,m,pos,val,type);
	upd(2*ind+1,m+1,r,pos,val,type);
	seg[ind].cnt = seg[2*ind].cnt+seg[2*ind+1].cnt;
	seg[ind].sum = seg[2*ind].sum+seg[2*ind+1].sum;
}

int quer(int ind,int l,int r,int rem){
	if(l == r){
		if(rem) return seg[ind].sum;
		else return 0;
	}
	int m = (l+r)/2;
	if(seg[2*ind+1].cnt >= rem) return quer(2*ind+1,m+1,r,rem);
	else return seg[2*ind+1].sum+quer(2*ind,l,m,rem-seg[2*ind+1].cnt);
}

void solve(int l,int r,int optl,int optr){
	// assumes r+1...optl-1 are already activated in segtree
	int mid = (l+r)/2;
	if(S-mid >= D){
		if(mid != r) solve(mid+1,r,optl,optr);
		return;
	}
	int cur = -1,opt = optl;
	FOR(i,mid,r+1) upd(1,0,N-1,a[i].S,a[i].F,1);
	FOR(i,optl,optr+1){
		upd(1,0,N-1,a[i].S,a[i].F,1);
		int rem = D-2*min(S-mid,i-S)-max(S-mid,i-S);
		if(rem <= 0) break;
		int gg = quer(1,0,N-1,rem);
		if(gg > cur){
			cur = gg;
			opt = i;
		}
	}
	if(cur > ans) ans = cur;
	FOR(i,mid,r+1) upd(1,0,N-1,a[i].S,a[i].F,0);
	FOR(i,optl,optr+1) upd(1,0,N-1,a[i].S,a[i].F,0);

	if(l != mid){
		FOR(i,mid,r+1) upd(1,0,N-1,a[i].S,a[i].F,1);
		solve(l,mid-1,optl,opt);
		FOR(i,mid,r+1) upd(1,0,N-1,a[i].S,a[i].F,0);
	}
	if(r != mid){
		FOR(i,optl,opt) upd(1,0,N-1,a[i].S,a[i].F,1);
		solve(mid+1,r,opt,optr);
		FOR(i,optl,opt) upd(1,0,N-1,a[i].S,a[i].F,0);
	}
}

int findMaxAttraction(signed n, signed start, signed d, signed attraction[]) {
	vector<pii> v;
	D = d;
	N = n;
	S = start;
	REP(i,n) v.pb({attraction[i],i});
	sort(v.begin(),v.end());
	REP(i,n) a[v[i].S] = {v[i].F,i};
	solve(0,start,start,n-1);
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 8036 KB Output is correct
2 Correct 56 ms 8036 KB Output is correct
3 Correct 55 ms 8048 KB Output is correct
4 Correct 53 ms 8036 KB Output is correct
5 Correct 71 ms 7780 KB Output is correct
6 Correct 21 ms 2424 KB Output is correct
7 Correct 38 ms 4340 KB Output is correct
8 Correct 48 ms 4724 KB Output is correct
9 Correct 14 ms 2168 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 640 KB Output is correct
2 Correct 9 ms 640 KB Output is correct
3 Correct 9 ms 640 KB Output is correct
4 Correct 14 ms 640 KB Output is correct
5 Correct 10 ms 640 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 8036 KB Output is correct
2 Correct 62 ms 8040 KB Output is correct
3 Correct 163 ms 4084 KB Output is correct
4 Correct 11 ms 640 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 864 ms 8924 KB Output is correct
9 Correct 911 ms 8936 KB Output is correct