oj.uz

Submission #93820

# Submission time Handle Problem Language Result Execution time Memory
93820 2019-01-11T18:51:17 Z Bodo171 Holiday (IOI14_holiday) C++14
100 / 100
 380 ms 5972 KB 
#include"holiday.h"
#include <iostream>
#include <algorithm>
using namespace std;
const int nmax=100005;
pair<long long,long long> aib[nmax];
long long ans;
pair<int,int> norm[nmax];
int wh[nmax],v[nmax],opt[nmax];
long long mx[nmax];
int n,D;
inline int lbit(int x)
{
    return ((x^(x-1))&x);
}
void update(int poz,long long v1,long long v2)
{
    for(int idx=poz;idx<=n;idx+=lbit(idx))
            aib[idx].first+=v1,aib[idx].second+=v2;
}
long long find_kth(int k)
{
    int cat=0,poz=0;
    long long ret=0;
    for(int p=17;p>=0;p--)
    {
        if(poz+(1<<p)<=n&&cat+aib[poz+(1<<p)].first<=k)
        {
            poz+=(1<<p);
            cat+=aib[poz].first;
            ret+=aib[poz].second;
        }
    }
    return ret;
}
void add(int poz)
{
    update(wh[poz],1,v[poz]);
}
void rem(int poz)
{
    update(wh[poz],-1,-v[poz]);
}
long long qr(int st,int dr,int mm)
{
    long long rr=find_kth(D-2*(dr-mm)-(mm-st));
    ans=max(ans,rr);
    if(rr>mx[dr])
        mx[dr]=rr,opt[dr]=st;
    return rr;
}
void solve(int s,int st,int dr,int optst,int optdr)
{
    if(st>dr) return;
    int m=(st+dr)/2;
    for(int i=st;i<=m;i++)
    {
        add(i);
    }
    qr(optdr,m,s);
    for(int i=optdr-1;i>=optst;i--)
    {
        add(i);
        qr(i,m,s);
    }
    if(!opt[m]) opt[m]=optdr;
    for(int i=optst;i<optdr;i++)
        rem(i);
    solve(s,m+1,dr,opt[m],optdr);
    for(int i=opt[m];i<optdr;i++)
        add(i);
    for(int i=st;i<=m;i++)
        rem(i);
    solve(s,st,m-1,optst,opt[m]);
    for(int i=opt[m];i<optdr;i++)
        rem(i);

}
void solvebrut(int s)
{
    for(int i=s;i<=n;i++)
    {
        add(i);
        qr(s,i,s);
        for(int j=s-1;j>=1;j--)
        {
            add(j);
            qr(j,i,s);
        }
        for(int j=s-1;j>=1;j--)
            rem(j);
    }
    for(int i=s;i<=n;i++)
        rem(i);
}
long long int findMaxAttraction(int N, int start, int d, int attraction[]) {
    n=N;
    for(int i=1;i<=n;i++)
        v[i]=attraction[i-1];
    for(int i=1;i<=n;i++)
        norm[i].first=v[i],norm[i].second=i;
    sort(norm+1,norm+n+1);
    for(int i=1;i<=n;i++)
        wh[norm[i].second]=n-i+1;
    D=d;
    start++;
    solve(start,start,n,1,start);
    //if(n<=3000||start<=100||start>=n-100) solvebrut(start);
    for(int i=1;i<=n;i++)
        mx[i]=0,opt[i]=0;
    for(int i=1;i<=n/2;i++)
        swap(v[i],v[n-i+1]),swap(wh[i],wh[n-i+1]);
    solve(n-start+1,n-start+1,n,1,n-start+1);
   // if(n<=3000||start<=100||start>=n-100) solvebrut(n-start+1);
    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 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 4948 KB Output is correct
2 Correct 55 ms 4956 KB Output is correct
3 Correct 62 ms 5052 KB Output is correct
4 Correct 57 ms 5072 KB Output is correct
5 Correct 99 ms 4736 KB Output is correct
6 Correct 23 ms 1656 KB Output is correct
7 Correct 48 ms 2808 KB Output is correct
8 Correct 59 ms 3192 KB Output is correct
9 Correct 15 ms 1272 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 5112 KB Output is correct
2 Correct 63 ms 5052 KB Output is correct
3 Correct 108 ms 2552 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 3 ms 380 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 371 ms 5972 KB Output is correct
9 Correct 380 ms 5820 KB Output is correct