oj.uz

Submission #548985

# Submission time Handle Problem Language Result Execution time Memory
548985 2022-04-14T22:04:39 Z lukameladze Holiday (IOI14_holiday) C++14
100 / 100
 1030 ms 10196 KB 
# 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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 704 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 704 KB Output is correct
5 Correct 1 ms 696 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 9456 KB Output is correct
2 Correct 32 ms 9440 KB Output is correct
3 Correct 38 ms 9388 KB Output is correct
4 Correct 36 ms 9512 KB Output is correct
5 Correct 51 ms 8740 KB Output is correct
6 Correct 13 ms 3148 KB Output is correct
7 Correct 29 ms 5236 KB Output is correct
8 Correct 41 ms 6192 KB Output is correct
9 Correct 11 ms 2500 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 964 KB Output is correct
2 Correct 1 ms 968 KB Output is correct
3 Correct 2 ms 984 KB Output is correct
4 Correct 16 ms 980 KB Output is correct
5 Correct 14 ms 852 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 5 ms 696 KB Output is correct
8 Correct 5 ms 724 KB Output is correct
9 Correct 5 ms 700 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 10196 KB Output is correct
2 Correct 33 ms 10176 KB Output is correct
3 Correct 310 ms 4968 KB Output is correct
4 Correct 14 ms 980 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 6 ms 724 KB Output is correct
7 Correct 6 ms 776 KB Output is correct
8 Correct 1024 ms 10032 KB Output is correct
9 Correct 1030 ms 10136 KB Output is correct