oj.uz

Submission #98854

# Submission time Handle Problem Language Result Execution time Memory
98854 2019-02-26T18:28:48 Z figter001 Holiday (IOI14_holiday) C++14
0 / 100
 1260 ms 7732 KB 
#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int nax = 1e5+50;

vector<pair<int,int>> a,b;
int s,n,idx[nax],l,r,cnt[4*nax],k;
ll dp[nax],d,seg[4*nax],val;

ll dis(ll a,ll b){
	if(a > b)swap(a,b);
	if(s >= a && s <= b){
		ll go = min(abs(s-b) , abs(s-a));
		ll go2 = max(abs(s-b) , abs(s-a));
		return go*2 + go2;
	}else{
		ll go = max(abs(s-b) , abs(s-a));
		return go;
	}
}

void update(int n,int s,int e){
	if(s > r || e < l)return;
	if(s == e){
		seg[n] = val;
		cnt[n] = (val > 0);
		return;
	}
	update(n*2,s,(s+e)/2);
	update(n*2+1,(s+e)/2+1,e);
	seg[n] = seg[n*2] + seg[n*2+1];
	cnt[n] = cnt[n*2] + cnt[n*2+1];
}

ll get(int n,int s,int e){
	if(s == e){
		if(k == 0)
			return 0;
		else 
			return seg[n];
	}
	if(k > cnt[n*2]){
		k -= cnt[n*2];
		return seg[n*2] + get(n*2+1,(s+e)/2+1,e);
	}else{
		return get(n*2,(s+e)/2+1,e);
	}
}

void solve(int x,int y,int ox,int oy){
	if(x > y)
		return;
	int md = (x+y)/2;
	int o1 = -1,o2 = -1;
	ll best = -1e18;
	for(int i=max(ox,x);i<=min(oy,y);i++){
		ll rem = d - dis(ox,i);
		l = r = idx[i];
		val = a[i].first;
		update(1,1,n);
		if(rem < 0)continue;
		k = rem;
		ll cur = get(1,1,n);
		if(cur > best){
			best = cur;
			o1 = i;
		}
	}
	for(int i=max(ox,x);i<=min(oy,y);i++){
		l = r = idx[i];
		val = 0;
		update(1,1,n);
	}
	dp[y] = max(dp[y],best);
	best = -1e18;
	for(int i=min(oy,y);i>=max(ox,x);i--){
		ll rem = d - dis(min(oy,y),i);
		l = r = idx[i];
		val = a[i].first;
		update(1,1,n);
		if(rem < 0)continue;
		k = rem;
		ll cur = get(1,1,n);
		// if(x == 0 && y == 4)cout << i << ' ' << cur << ' ' << best << endl;
		if(cur > best){
			best = cur;
			o2 = i;
		}
	}
	for(int i=min(oy,y);i>=max(ox,x);i--){
		l = r = idx[i];
		val = 0;
		update(1,1,n);
	}
	// cout << ox << ' ' << oy << ' ' << x << ' ' << y << ' ' << dp[y] << ' ' << o1 << ' ' << o2 << endl;
	dp[y] = max(best,dp[y]);
	solve(x,md-1,ox,o1);
	solve(md+1,y,o2,oy);
}

long long int findMaxAttraction(int N, int start, int days, int attraction[]) {
	n = N;
	s = start;
	d = days;
	for(int i=0;i<n;i++)
		a.push_back({attraction[i],i});
	b = a;
	sort(b.begin(),b.end());
	reverse(b.begin(),b.end());
	for(int i=0;i<n;i++)
		idx[b[i].second] = i+1;
	solve(0,n-1,0,n-1);
	ll ans = 0;
	// printf("\n");
	for(int i=0;i<n;i++){
		// cout << i << ' ' << dp[i] << endl;
		ans = max(ans,dp[i]);
	}
    return ans;
}

Compilation message

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Incorrect 2 ms 372 KB Output isn't correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 951 ms 6856 KB Output is correct
2 Correct 117 ms 6908 KB Output is correct
3 Correct 970 ms 6832 KB Output is correct
4 Correct 145 ms 6888 KB Output is correct
5 Correct 1260 ms 6668 KB Output is correct
6 Correct 277 ms 2224 KB Output is correct
7 Incorrect 664 ms 3800 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 512 KB Output is correct
2 Correct 16 ms 512 KB Output is correct
3 Correct 15 ms 512 KB Output is correct
4 Incorrect 26 ms 512 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 950 ms 6860 KB Output is correct
2 Correct 1045 ms 7732 KB Output is correct
3 Incorrect 150 ms 3824 KB Output isn't correct
4 Halted 0 ms 0 KB -