oj.uz

Submission #12712

# Submission time Handle Problem Language Result Execution time Memory
12712 2015-01-01T13:25:49 Z dohyun0324 Holiday (IOI14_holiday) C++
100 / 100
 1556 ms 46088 KB 
#include"holiday.h"
#include<string.h>
#include<algorithm>
using namespace std;
int top,s,t=1,pos[100001],k,e,p2[530001],r=1;
long long dap,r1[530001],l1[530001],r2[530001],l2[530001],p[530001];
struct data{
    int x,y;
    bool operator<(const data&r)const{
        return x>r.x;
    }
}a[100001];
struct data2{
    int num;
    long long sum;
}tree[270010];
struct data3{
    int x,y,m1,m2;
}st[530010];
struct data3 st2[530010];
void update(int x){
    int p=x+t-1;
    if(tree[p].num) return;
    while(p>0){
        tree[p].num++; tree[p].sum+=a[x].x;
        p/=2;
    }
}
void finding(int x,int y,int k,int num){
    if(k==1 && num==0){s=0; return;}
    if(x==y){s=x-1; return;}
    if(num-tree[k*2].num>=0)
    {
        finding((x+y)/2+1,y,k*2+1,num-tree[k*2].num);
    }
    else finding(x,(x+y)/2,k*2,num);
}
long long query(int x,int y,int k,int s,int e){
    if(s<=x && y<=e) return tree[k].sum;
    if(s>y || e<x) return 0;
    return query(x,(x+y)/2,k*2,s,e)+query((x+y)/2+1,y,k*2+1,s,e);
}
void gap(int m,int x,int y,int sw){
    int i,ps=x;
    long long maxi=0;
    for(i=e+1;i<x;i++) update(pos[i]);
    for(i=x;i<=y;i++)
    {
        update(pos[i]);
        if(sw==1) finding(1,t,1,m-(i-1)-1);
        else finding(1,t,1,m-(i-1+1)*2);
        if(maxi<query(1,t,1,1,s))
        {
            maxi=query(1,t,1,1,s);
            ps=i;
        }
    }
    e=y;
    p[m]=maxi; p2[m]=ps;
}
void ins(int i)
{
    int m=(st[i].m1+st[i].m2)/2;
    st2[i*2-1].m1=st[i].m1; st2[i*2-1].m2=m;
    st2[i*2-1].x=st[i].x; st2[i*2-1].y=p2[m];
    st2[i*2].m1=m+1; st2[i*2].m2=st[i].m2;
    st2[i*2].x=p2[m]; st2[i*2].y=st[i].y;
}
void pro(int m1,int m2,int x,int y,int sw){
    int i,m;
    top=1; st[top].m1=m1; st[top].m2=m2; st[top].x=x; st[top].y=y;
    while(1)
    {
        memset(tree,0,sizeof tree);
        if(st[1].m1==st[1].m2) return;
        e=0;
        for(i=1;i<=top;i++){
            m=(st[i].m1+st[i].m2)/2;
            if(m==3)
            {
                m=3;
            }
            gap(m,st[i].x,st[i].y,sw);
        }
        for(i=1;i<=top;i++){
            ins(i);
        }
        top*=2;
        for(i=1;i<=top;i++) st[i]=st2[i];
    }
}
long long int findMaxAttraction(int n, int st, int d, int att[])
{
    int i;
    for(i=st-1;i>=0;i--) a[st-i].x=att[i], a[st-i].y=st-i;
    sort(a+1,a+st+1); for(i=1;i<=st;i++) pos[a[i].y]=i;
    for(i=1;;i++){if(r>=st*3) break; r*=2;}
    for(i=1;;i++){if(t>=st) break; t*=2;}
    pro(1,r,1,st,1); for(i=1;i<=r;i++) l1[i]=p[i];
    memset(p,0,sizeof p); pro(1,r,1,st,2); for(i=1;i<=r;i++) l2[i]=p[i];
    for(i=st+1;i<n;i++) a[i-st].x=att[i], a[i-st].y=i-st;
    sort(a+1,a+n-st); for(i=1;i<=n-st-1;i++) pos[a[i].y]=i;
    r=1; for(i=1;;i++){if(r>=(n-st-1)*3) break; r*=2;}
    for(i=1;;i++){if(t>=n-st-1) break; t*=2;}
    memset(p,0,sizeof p); pro(1,r,1,n-st-1,1); for(i=1;i<=r;i++) r1[i]=p[i];
    memset(p,0,sizeof p); pro(1,r,1,n-st-1,2); for(i=1;i<=r;i++) r2[i]=p[i];
    for(i=0;i<=d;i++){
        dap=max(dap,l1[i]+r2[d-i]);
        dap=max(dap,l2[i]+r1[d-i]);
        if(i>=1) dap=max(dap,l1[i-1]+r2[d-i]+att[st]);
        if(i>=1) dap=max(dap,l2[i-1]+r1[d-i]+att[st]);
    }
    return dap;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 46084 KB Output is correct
2 Correct 4 ms 46084 KB Output is correct
3 Correct 4 ms 46084 KB Output is correct
4 Correct 4 ms 46080 KB Output is correct
5 Correct 8 ms 46080 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1284 ms 46084 KB Output is correct
2 Correct 1252 ms 46084 KB Output is correct
3 Correct 1292 ms 46088 KB Output is correct
4 Correct 1228 ms 46080 KB Output is correct
5 Correct 1556 ms 46084 KB Output is correct
6 Correct 344 ms 46080 KB Output is correct
7 Correct 716 ms 46084 KB Output is correct
8 Correct 868 ms 46080 KB Output is correct
9 Correct 228 ms 46084 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 46084 KB Output is correct
2 Correct 32 ms 46088 KB Output is correct
3 Correct 32 ms 46084 KB Output is correct
4 Correct 40 ms 46088 KB Output is correct
5 Correct 32 ms 46084 KB Output is correct
6 Correct 16 ms 46084 KB Output is correct
7 Correct 24 ms 46084 KB Output is correct
8 Correct 20 ms 46084 KB Output is correct
9 Correct 20 ms 46084 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1304 ms 46080 KB Output is correct
2 Correct 1384 ms 46084 KB Output is correct
3 Correct 564 ms 46088 KB Output is correct
4 Correct 36 ms 46084 KB Output is correct
5 Correct 20 ms 46088 KB Output is correct
6 Correct 24 ms 46080 KB Output is correct
7 Correct 24 ms 46084 KB Output is correct
8 Correct 1384 ms 46084 KB Output is correct
9 Correct 1396 ms 46084 KB Output is correct