Submission #30535

#	Time	Username	Problem	Language	Result	Execution time	Memory
30535		Nikefor	Holiday (IOI14_holiday)	C++98	0 / 100	23 ms	5876 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
#define max_n 1<<17
#define ll long long
using namespace std;
typedef pair<ll,int> li;
int n, d, start, L, R;
ll res;
pair<ll,int> segment[max_n];
int id[max_n];
int ord[max_n];
int a[max_n];
ll get(int x) {
	int k = 1;
	ll sum = 0;
	while(x < n) {
    	if(segment[k+k+1].second >= x) k = k+k+1;
    	else {
    		x -= segment[k+k+1].second;
    		sum += segment[k+k+1].first;
    		k>>=1;
    	}
    }
    sum += (x > 0) * segment[k].first;
    return sum;

}
void add(int x) {
	segment[x+n] = make_pair(a[ord[x]],1);
	x+= n;
	x>>=1;
	for(;x>1;x>>=1) {
		segment[x].first = segment[x+x].first + segment[x+x+1].first; 
		segment[x].second = segment[x+x].second + segment[x+x+1].second; 
	}
}
void erase(int x) {
	segment[x+n] = make_pair(0,0);
	x+=n;
	x>>=1;
	for(;x>1;x>>=1) {
		segment[x].first = segment[x+x].first + segment[x+x+1].first; 
		segment[x].second = segment[x+x].second + segment[x+x+1].second; 
	}
}
void fix(int l, int r) {
	while(l>L) erase(id[L++]);
	while(r<R) erase(id[R--]);
	while(l<L) add(id[--L]);
	while(r>R) add(id[++R]);
}
bool cmp(int x, int y) {	
	return a[x]<a[y];
}
void solve(int l, int r, int sl, int sr) {
	if(l>r) return;
	int mid = (l+r)>>1;
	for(int i = sl; i<=sr; i++) {
		if(i>mid) break;
		fix(i,mid);
		ll tmp = get(d-(mid-i)-(mid-start));
		res = max(res, tmp);
	}
	solve(l, mid-1, sl,sr);
	solve(mid+1,r,sl,sr);
}
void solveStart(void) {
	for(int i=1; i<=n; i++) ord[i] = i;
	sort(ord+1, ord+n+1, cmp);
	for(int i = 1; i <= n; i++)
    id[ord[i]] = i;
   	L = 1;
   	R = 0;
   	memset(segment, 0, sizeof(segment));
   	for(int i = start; i <= n; i++) {
    	add(id[i]);
    	res = max(res, get(d - (i - start)));
    }
   	memset(segment, 0, sizeof(segment));
   	solve(start, n, 1, start);
}
long long int findMaxAttraction(int N, int Start, int D, int attraction[]) {
    n = N, d = D, start = Start+1;
    for (int i = 0; i < N; ++i)
    {
    	a[i+1] = attraction[i];
    	ord[i+1] = i+1;
    }
    solveStart();
    reverse(a+1, a+n+1);


    return res;
}

Compilation message (stderr)

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
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53