| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 104391 |
2019-04-06T11:22:49 Z |
wilwxk |
Holiday (IOI14_holiday) |
C++11 |
|
1327 ms |
9248 KB |
#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;
}
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;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1327 ms |
8544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
1784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1012 ms |
9248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
