Submission #657767

#	Time	Username	Problem	Language	Result	Execution time	Memory
657767		lkh3happy	Holiday (IOI14_holiday)	C++14	100 / 100	756 ms	9440 KiB

holiday

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

long long A[100001], t[400001], cnt[400001], ll=1, rr=0;
vector<long long> cp;

void upd(int l, int r, int n, int x, int v){
    if(r<x || x<l) return;
    if(l==r){
        cnt[n]+=v; t[n]+=v*cp[l-1]; return;
    }
    int m=l+r>>1;
    upd(l, m, n*2, x, v); upd(m+1, r, n*2+1, x, v);
    t[n]=t[n*2]+t[n*2+1]; cnt[n]=cnt[n*2]+cnt[n*2+1];
}

long long kth(int l, int r, int n, int k){
    if(l==r) return min(cnt[n], 1LL*k)*cp[l-1];
    int m=l+r>>1;
    if(cnt[n*2+1]>=k) return kth(m+1, r, n*2+1, k);
    return kth(l, m, n*2, k-cnt[n*2+1])+t[n*2+1];
}

void move(int l, int r){
    for(;rr<r;) upd(1, cp.size(), 1, A[++rr], 1);
    for(;ll>l;) upd(1, cp.size(), 1, A[--ll], 1);
    for(;rr>r;) upd(1, cp.size(), 1, A[rr--], -1);
    for(;ll<l;) upd(1, cp.size(), 1, A[ll++], -1);
}

long long dnc(int l, int r, int s, int e, int st, int d){
    if(r<l) return 0;
    int m=l+r>>1;
    long long mx=0, idx=e;
    if(d-(m-st+m-e)>0){
        move(e, m);
        mx=kth(1, cp.size(), 1, d-(m-st+m-e));
        for(int i=e-1;i>=s && d-(m-st+m-i);i--){
            move(i, m);
            if(mx<kth(1, cp.size(), 1, d-(m-st+m-i))) mx=kth(1, cp.size(), 1, d-(m-st+m-i)), idx=i;
        }
    }
    return max(mx, max(dnc(l, m-1, s, idx, st, d), dnc(m+1, r, idx, e, st, d)));
}

long long solve(int n, int s, int d){
    for(int i=0;i<=400000;i++) t[i]=cnt[i]=0; ll=1; rr=0;
    return dnc(s, n, 1, s, s, d);
}

long long findMaxAttraction(int n, int s, int d, int At[]){
    for(int i=0;i<n;i++) A[i+1]=At[i], cp.push_back(At[i]); s++;
    sort(cp.begin(), cp.end());
    cp.erase(unique(cp.begin(), cp.end()), cp.end());
    for(int i=1;i<=n;i++) A[i]=lower_bound(cp.begin(), cp.end(), A[i])-cp.begin()+1;
    long long ans=solve(n, s, d);
    reverse(A+1, A+n+1); s=n+1-s;
    return max(ans, solve(n, s, d));
    return 0;
}

Compilation message (stderr)

holiday.cpp: In function 'void upd(int, int, int, int, int)':
holiday.cpp:14:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |     int m=l+r>>1;
      |           ~^~
holiday.cpp: In function 'long long int kth(int, int, int, int)':
holiday.cpp:21:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     int m=l+r>>1;
      |           ~^~
holiday.cpp: In function 'long long int dnc(int, int, int, int, int, int)':
holiday.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int m=l+r>>1;
      |           ~^~
holiday.cpp: In function 'long long int solve(int, int, int)':
holiday.cpp:49:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   49 |     for(int i=0;i<=400000;i++) t[i]=cnt[i]=0; ll=1; rr=0;
      |     ^~~
holiday.cpp:49:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   49 |     for(int i=0;i<=400000;i++) t[i]=cnt[i]=0; ll=1; rr=0;
      |                                               ^~
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:54:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   54 |     for(int i=0;i<n;i++) A[i+1]=At[i], cp.push_back(At[i]); s++;
      |     ^~~
holiday.cpp:54:61: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   54 |     for(int i=0;i<n;i++) A[i+1]=At[i], cp.push_back(At[i]); s++;
      |                                                             ^

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53