Submission #548985

#	Time	Username	Problem	Language	Result	Execution time	Memory
548985		lukameladze	Holiday (IOI14_holiday)	C++14	100 / 100	1030 ms	10196 KiB

holiday

# include "holiday.h"
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int, int> 
#define pb push_back
using namespace std;
const int N = 3e5 + 5;
long long curle,n,ans,anss,d,s,a1[N];
pii a[N];
long long ind[N];
struct nod {
    long long sum, raod;
};
nod tree[4*N];
nod merge(nod a, nod b) {
    nod pas = {0,0};
    pas.sum = a.sum + b.sum;
    pas.raod = a.raod + b.raod;
    return pas;
}
void update(int node, int le, int ri, int idx, int val) {
    if (le > idx || ri < idx) return ;
    if (le == ri) {
        if (val == 1) {
            //cout<<le<<" "<<a[idx].f<<endl;
            tree[node] = {a[idx].f,1};
        } else tree[node] = {0,0};
        return ;
    }
    int mid = (le + ri) / 2;
    update(2*node,le,mid,idx,val);
    update(2*node + 1, mid + 1, ri, idx,val);
    tree[node] = merge(tree[2*node], tree[2*node + 1]);
}
long long findkth(long long node, long long le, long long ri, long long k) {
    if (tree[node].raod <= k) {
        return tree[node].sum;
    }
    int mid = (le + ri) / 2;
    if (tree[2*node].raod < k) {
        k -= tree[2*node].raod;
        return tree[2*node].sum + findkth(2*node + 1,mid + 1,ri,k);
    } else return findkth(2*node,le,mid,k);
}
void solve(int le, int ri, int optl, int optr) {
    long long mid = (le + ri) / 2;
    while (curle > mid) {
        curle--;
        update(1,1,n,ind[curle],1);
    }
    while(curle < mid) {
        update(1,1,n,ind[curle],-1);
        curle++;
    }
    long long ansidx = optl;
    long long ans = 0;
    for (long long i = optl; i <= optr; i++) {
        //cout<<i<<" ";
        update(1,1,n,ind[i],1);
        int K = d - (2*(s-mid)) - (i - s);
        if (K <= 0) continue;
        if (ans < findkth(1,1,n,K)) {
            ans = findkth(1,1,n,K);
            ansidx = i;
        }
    }  
    curle = mid;
    anss = max(anss,ans);
    if (le == ri) return ;
    for (int i = optl; i <= optr; i++) {
        update(1,1,n,ind[i],-1);
    }
    if (ans != 0)
    solve(le,mid,optl,ansidx);
    for (int i = optl; i <= ansidx - 1; i++) {
        update(1,1,n,ind[i],1);
    }
    solve(mid + 1, ri, ansidx, optr);
}
long long findMaxAttraction(int nn, int ss,int dd, int ar[]) {
    n = nn; s = ss; d = dd;
    s++;
    for (int i = 1; i <= n ;i++) {
        a[i].f = ar[i - 1];
        a1[i] = a[i].f;
        a[i].s = i;
        //cout<<a[i].f<<" ";
    }
    if (d == 1) {
        return a[s].f;
        exit(0);
    }
    sort(a + 1, a + n + 1);
    reverse(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        ind[a[i].s] = i;
    }
    curle = s + 1;
    if (s != n)
    solve(1,s,s + 1,n);
    //cout<<anss<<endl;
    reverse(a1 + 1, a1 + n + 1);
    for (int i = 1; i <= n; i++) {
        a[i].f = a1[i];
        a[i].s = i;
    }
    sort(a + 1,  a + n + 1);
    reverse(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        ind[a[i].s] = i;
    }
    s = n - s + 1;
     curle = s + 1;
    for (int i = 1; i <= 4*n; i++) {
        tree[i].sum = 0;
        tree[i].raod = 0;
    }
    if (s != n)
    solve(1,s,s + 1, n);
    return anss;
}
/*
int main() {
    int n, start, d;
    int attraction[100000];
    int i, n_s;
    n_s = scanf("%d %d %d", &n, &start, &d);
    for (i = 0 ; i < n; ++i) {
	n_s = scanf("%d", &attraction[i]);
    }
    printf("%lld\n", findMaxAttraction(n, start, d, attraction));
    return 0;
}*/
 

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