oj.uz

Submission #718459

# Submission time Handle Problem Language Result Execution time Memory
718459 2023-04-04T07:01:19 Z qwerasdfzxcl Holiday (IOI14_holiday) C++17
100 / 100
 351 ms 45248 KB 
#include <bits/stdc++.h>
#include "holiday.h"

using namespace std;
typedef long long ll;

int n, s, d, r, c, a[100100], b[100100];
ll ans;

struct Node{
    int l, r;
    ll x;
    int c;
    Node(){}
    Node(int _l, int _r, ll _x, int _c): l(_l), r(_r), x(_x), c(_c) {}
};

struct PST{
    Node tree[2002000]; int pt1;
    int root[100100]; int pt2;
    int sz;

    ll ansx;
    int remc;

    void init(int n){
        sz = n;
        pt1 = pt2 = 0;
        tree[pt1++] = Node(0, 0, 0, 0);
        root[pt2++] = 0;
    }
    int cp(int x){
        tree[pt1++] = tree[x];
        return pt1-1;
    }
    void update(int i, int l, int r, int p, ll x, int c){
        if (r<p || p<l) return;
        if (l==r){
            tree[i].x += x;
            tree[i].c += c;
            return;
        }

        int m = (l+r)>>1;
        if (p<=m) update(tree[i].l=cp(tree[i].l), l, m, p, x, c);
        else update(tree[i].r=cp(tree[i].r), m+1, r, p, x, c);
        tree[i].x = tree[tree[i].l].x + tree[tree[i].r].x;
        tree[i].c = tree[tree[i].l].c + tree[tree[i].r].c;
    }
    void search(int il, int ir, int l, int r){
        if (remc<=0) return;
        if (tree[ir].c - tree[il].c <= remc){
            ansx += tree[ir].x - tree[il].x;
            remc -= tree[ir].c - tree[il].c;
            return;
        }

        int m = (l+r)>>1;
        search(tree[il].r, tree[ir].r, m+1, r);
        search(tree[il].l, tree[ir].l, l, m);
    }

    void update(int p, ll x, int c){
        root[pt2] = cp(root[pt2-1]);
        pt2++;
        update(root[pt2-1], 1, sz, p, x, c);
    }
    ll query(int l, int r, int c){
        c = max(c, 0);
        c = min(c, r-l+1);
        remc = c;
        ansx = 0;

        search(root[l-1], root[r], 1, n);
        return ansx;
    }
}tree;

ll f(int x, int y){
    return tree.query(s-x+1, s+y-1, d - (x-1)*2 - (y-1));
}

void dnc(int sx, int ex, int sy, int ey){
    if (sx > ex) return;
    
    int mid = (sx+ex)>>1;
    int opt = sy;
    ll val = f(mid, sy);
    for (int i=sy+1;i<=ey;i++){
        ll tmp = f(mid, i);
        if (tmp > val){
            val = tmp;
            opt = i;
        }
    }

    ans = max(ans, val);
    dnc(sx, mid-1, opt, ey);
    dnc(mid+1, ex, sy, opt);
}

ll solve(int N, int start, int D, int attraction[]){
    n = N, s = start+1, d = D, ans = 0;
    vector<pair<int, int>> V;
    for (int i=1;i<=n;i++){
        a[i] = attraction[i-1];
        V.emplace_back(a[i], i);
    } 

    sort(V.begin(), V.end());
    for (int i=0;i<n;i++) b[V[i].second] = i + 1;

    tree.init(n);
    for (int i=1;i<=n;i++){
        tree.update(b[i], a[i], 1);
    }

    r = s, c = n-s+1;

    dnc(1, r, 1, c);
    return ans;
}

long long int findMaxAttraction(int N, int start, int D, int attraction[]) {
    ll ans = solve(N, start, D, attraction);
    reverse(attraction, attraction+N);
    start = N - 1 - start;

    return max(ans, solve(N, start, D, attraction));
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 45204 KB Output is correct
2 Correct 78 ms 45228 KB Output is correct
3 Correct 88 ms 45116 KB Output is correct
4 Correct 77 ms 45104 KB Output is correct
5 Correct 89 ms 41268 KB Output is correct
6 Correct 22 ms 11968 KB Output is correct
7 Correct 48 ms 22256 KB Output is correct
8 Correct 56 ms 26888 KB Output is correct
9 Correct 15 ms 8496 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 45140 KB Output is correct
2 Correct 74 ms 45116 KB Output is correct
3 Correct 79 ms 19552 KB Output is correct
4 Correct 4 ms 1492 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 2 ms 980 KB Output is correct
8 Correct 351 ms 45248 KB Output is correct
9 Correct 343 ms 45140 KB Output is correct