제출 #104391

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
104391		wilwxk	휴가 (IOI14_holiday)	C++11	0 / 100	1327 ms	9248 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define printf printf

struct node {
	int cnt;
	ll val;
};

const int MAXN=1e5+5;
node seg[MAXN*4];
int v[MAXN], vv[MAXN], onde[MAXN];
int f[MAXN], g[MAXN];
ll fv[MAXN], gv[MAXN];
int n, ori, x;
ll respf=0;

bool cmp(int a, int b) { return v[a]>v[b]; }

void update(int sind, int ini, int fim, int qind, int k) {
	if(qind<ini||qind>fim) return;
	if(ini==fim) {
		if(k) seg[sind].val=v[vv[ini]];
		else seg[sind].val=0;
		seg[sind].cnt=k;
		return;
	}
	int m=(ini+fim)/2; int e=sind*2; int d=e+1;
	update(e, ini, m, qind, k);
	update(d, m+1, fim, qind, k);

	seg[sind].cnt=seg[e].cnt+seg[d].cnt;
	seg[sind].val=seg[e].val+seg[d].val;
}

ll query(int sind, int ini, int fim, int val) {
	if(val<=0) return 0;
	if(val==seg[sind].cnt) return seg[sind].val;
	if(ini==fim) return val ? seg[sind].val : 0;
	int m=(ini+fim)/2; int e=sind*2; int d=e+1;
	if(seg[e].cnt>=val) return query(e, ini, m, val);
	else return seg[e].val+query(d, m+1, fim, val-seg[e].cnt);
}

void ativa(int ind, int k) { update(1, 1, n, onde[ind], k); }

void calc(int ini, int fim, int rini, int rfim) {
	if(fim<ini) return;
	int cur=(ini+fim)/2;

	ll melhor=0; int opt=rini;
	for(int i=rini; i<=rfim; i++) {
		ativa(i, 1);
		int pode=cur-(i-ori);
		ll val=query(1, 1, n, pode);
		if(val>melhor) opt=i, melhor=val;
	}
	g[cur]=opt; gv[cur]=melhor;
	//printf("g[%d]= %d // %lld\n", cur, opt, melhor);

	for(int i=opt; i<=rfim; i++) ativa(i, 0);
	calc(cur+1, fim, opt, rfim);
	for(int i=rini; i<=opt; i++) ativa(i, 0);
	calc(ini, cur-1, rini, opt);
	for(int i=rini; i<=rfim; i++) ativa(i, 0);
}

void calc2(int ini, int fim, int rini, int rfim) {
	if(fim<ini) return;
	int cur=(ini+fim)/2;

	ll melhor=0; int opt=rini;
	for(int i=rfim; i>=rini; i--) {
		ativa(i, 1);
		int pode=cur-(ori-1-i);
		ll val=query(1, 1, n, pode);
		if(val>melhor) opt=i, melhor=val;
	}
	f[cur]=opt; fv[cur]=melhor;
	// printf("f[%d]= %d // %lld\n", cur, opt, melhor);
	
	for(int i=rini; i<=opt; i++) ativa(i, 0);
	calc2(cur+1, fim, rini, opt);
	for(int i=opt; i<=rfim; i++) ativa(i, 0);
	calc2(ini, cur-1, opt, rfim);
	for(int i=rini; i<=rfim; i++) ativa(i, 0);
}

void resolve() {
	// for(int i=0; i<=x; i++) {
	// 	//faz a curva na direita
	// 	int sobra=x-i-(g[i]-ori+1); sobra=min(sobra, x);
	// 	sobra=0;
	// 	ll val=gv[i]; if(sobra>0) val+=fv[sobra];
	// 	// int sobra2=x-i-(g[i]-ori+1); sobra2=min(sobra2, x);
	// 	// ll val=gv[i]; if(sobra2>0) val+=fv[sobra2];

	// 	respf=max(respf, val);
	// 	// respf=max(respf, val2);
	// }
	// for(int i=0; i<=x; i++) {
	// 	//faz a curva na esquerda
	// 	int sobra=x-1-i-(ori-f[i]); sobra=min(sobra, x);
	// 	ll val=fv[i]; if(sobra>0) val+=gv[sobra];
	// 	// respf=max(respf, val);
	// }
	for(int i=1; i<=x; i++) respf=max(respf, gv[i]);
}

ll findMaxAttraction(int N, int ORI, int X, int V[]) {
	n=N; ori=ORI+1; x=X;
	for(int i=0; i<n; i++) v[i+1]=V[i], vv[i+1]=i+1;
	sort(vv+1, vv+1+n, cmp);
	for(int i=1; i<=n; i++) onde[vv[i]]=i;

	for(int i=1; i<=n; i++) ativa(i, 0);

	calc2(1, x, 1, ori-1);
	memset(f, 0, sizeof(f));
	memset(fv, 0, sizeof(fv));
	calc(1, x, ori, n);
	f[0]=g[0]=ori; fv[0]=gv[0]=0;

	resolve();

    return respf;
}

컴파일 시 표준 에러 (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