oj.uz

Submission #68942

# Submission time Handle Problem Language Result Execution time Memory
68942 2018-08-19T10:27:25 Z moonrabbit2 Holiday (IOI14_holiday) C++17
100 / 100
 486 ms 58544 KB 
#include "holiday.h"
#include <bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
struct node {int l,r,v1;ll v2;};
int n,start,d,a[N],b[N],c,cn,root[N];
map<int,int> mp,to;
ll ans;
node tree[20*N];
void initseg(int nd,int l,int r)
{
    tree[nd].v1=tree[nd].v2=0;
    if(l==r)return;
    tree[nd].l=++cn;
    tree[nd].r=++cn;
    int m=(l+r)/2;
    initseg(tree[nd].l,l,m);
    initseg(tree[nd].r,m+1,r);
}
void add(int ln,int rn,int l,int r,ll v1,ll v2)
{
    tree[rn].v1=tree[ln].v1+1;
    tree[rn].v2=tree[ln].v2+v2;
    if(l==r)return;
    int m=(l+r)/2;
    if(v1<=m){
        tree[rn].r=tree[ln].r;
        tree[rn].l=++cn;
        add(tree[ln].l,tree[rn].l,l,m,v1,v2);
    }
    else{
        tree[rn].l=tree[ln].l;
        tree[rn].r=++cn;
        add(tree[ln].r,tree[rn].r,m+1,r,v1,v2);
    }
}
ll query(int ln,int rn,int l,int r,ll k)
{
    if(k<=0) return 0;
    if(l==r){
        if(k<=tree[rn].v1-tree[ln].v1)
            return (tree[rn].v2-tree[ln].v2)/(tree[rn].v1-tree[ln].v1)*k;
        return tree[rn].v2-tree[ln].v2;
    }
    int m=(l+r)/2;
    ll use=tree[tree[rn].r].v1-tree[tree[ln].r].v1;
    if(use>k)
        return query(tree[ln].r,tree[rn].r,m+1,r,k);
    else
        return tree[tree[rn].r].v2-tree[tree[ln].r].v2+query(tree[ln].l,tree[rn].l,l,m,k-use);
}
void dnc(int s,int e,int l,int r)
{
    if(s>e||l>r)return;
    int m=(s+e)/2,best=l;
    ll cans=-1,curr;
    for(int i=l;i<=r;i++){
        curr=query(root[m-1],root[i],1,c,d-i+m-min(start-m,i-start));
        if(query<=0)break;
        if(curr>cans){
            cans=curr;
            best=i;
        }
    }
    ans=max(ans,cans);
    dnc(s,m-1,l,best);
    dnc(m+1,e,best,r);
}
ll findMaxAttraction(int n_,int start_,int d_,int attraction[])
{
    n=n_;
    start=start_;
    d=d_;
    for(int i=0;i<n;i++){
        a[i]=attraction[i];
        mp[a[i]]++;
    }
    for(auto &it : mp)
        to[it.first]=++c;
    root[0]=++cn;
    initseg(root[0],1,c);
    for(int i=1;i<=n;i++){
        root[i]=++cn;
        add(root[i-1],root[i],1,c,to[attraction[i-1]],attraction[i-1]);
    }
    start++;
    dnc(1,start,start,n);
    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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 396 KB Output is correct
4 Correct 2 ms 408 KB Output is correct
5 Correct 2 ms 584 KB Output is correct
6 Correct 2 ms 584 KB Output is correct
7 Correct 3 ms 584 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4004 KB Output is correct
2 Correct 14 ms 4004 KB Output is correct
3 Correct 17 ms 6308 KB Output is correct
4 Correct 19 ms 6680 KB Output is correct
5 Correct 41 ms 18964 KB Output is correct
6 Correct 20 ms 18964 KB Output is correct
7 Correct 25 ms 18964 KB Output is correct
8 Correct 35 ms 18964 KB Output is correct
9 Correct 12 ms 18964 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 18964 KB Output is correct
2 Correct 3 ms 18964 KB Output is correct
3 Correct 7 ms 18964 KB Output is correct
4 Correct 8 ms 18964 KB Output is correct
5 Correct 6 ms 18964 KB Output is correct
6 Correct 5 ms 18964 KB Output is correct
7 Correct 3 ms 18964 KB Output is correct
8 Correct 4 ms 18964 KB Output is correct
9 Correct 3 ms 18964 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 18964 KB Output is correct
2 Correct 155 ms 58544 KB Output is correct
3 Correct 126 ms 58544 KB Output is correct
4 Correct 6 ms 58544 KB Output is correct
5 Correct 3 ms 58544 KB Output is correct
6 Correct 3 ms 58544 KB Output is correct
7 Correct 4 ms 58544 KB Output is correct
8 Correct 486 ms 58544 KB Output is correct
9 Correct 476 ms 58544 KB Output is correct