oj.uz

Submission #97879

# Submission time Handle Problem Language Result Execution time Memory
97879 2019-02-19T09:45:17 Z onjo0127 Holiday (IOI14_holiday) C++11
100 / 100
 802 ms 54616 KB 
#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct node {
    int c;
    ll s;
    int l, r;
};

node T[2200009];

struct PST {
    int top, sz;
    vector<int> root;
    void upd(int nid, int pid, int s, int e, int x, ll y) {
        if(s == e) {
            T[nid] = {1, y, 0, 0};
            return;
        }
        int m = s+e >> 1;
        if(x <= m) {
            T[nid].l = ++top; T[nid].r = T[pid].r;
            upd(top, T[pid].l, s, m, x, y);
        }
        else {
            T[nid].l = T[pid].l; T[nid].r = ++top;
            upd(top, T[pid].r, m+1, e, x, y);
        }
        int lc = T[nid].l, rc = T[nid].r;
        T[nid].c = T[lc].c + T[rc].c;
        T[nid].s = T[lc].s + T[rc].s;
    }
    void add(int s, int e, int x, ll y) {
        int rt = ++top;
        upd(rt, root.back(), s, e, x, y);
        root.push_back(rt);
    }
    ll kth(int id1, int id2, int s, int e, int k) {
        if(s == e) return T[id2].s - T[id1].s;
        int r1 = T[id1].r, r2 = T[id2].r;
        int cr = T[r2].c - T[r1].c;
        int m = s+e >> 1;
        if(cr >= k) return kth(r1, r2, m+1, e, k);
        return kth(T[id1].l, T[id2].l, s, m, k - cr) + T[r2].s - T[r1].s;
    }
    PST(int N) {
        sz = N;
        for(int i=1; i<=4*N; i++) T[i] = {0, 0, i*2, i*2+1};
        root.push_back(1);
        top = 4*N;
    }
};

long long ans = 0;
int A[100009], B[100009], C[100009], st, dd;

void go(PST& pseg, int s, int e, int l, int r) {
    if(s > e || l > r) return;
    int m = s+e >> 1, id = l, lf;
    ll mx = -1;
    for(int i=l; i<=r; i++) {
        int lft = max(dd - (2*(st-m) + i-st), 0);
        if(lft == 0) break;
        ll v = pseg.kth(pseg.root[m-1], pseg.root[i], 1, pseg.sz, lft);
        if(mx < v) mx = v, id = i, lf = lft;
    }
    ans = max(ans, mx);
    go(pseg, s, m-1, l, id);
    go(pseg, m+1, e, id, r);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    int N = n; st = start + 1; dd = d;
    for(int i=1; i<=N; i++) A[i] = attraction[i-1];
    for(int i=1; i<=N; i++) B[i] = i;
    sort(B+1, B+N+1, [&](int P, int Q) {return A[P] < A[Q];});
    for(int i=1; i<=N; i++) C[B[i]] = i;
    for(int k=0; k<2; k++) {
        PST pseg(N);
        for(int i=1; i<=N; i++) pseg.add(1, N, C[i], A[i]);
        go(pseg, 1, st, st, N);
        reverse(A+1, A+N+1);
        reverse(C+1, C+N+1);
        st = N - st + 1;
    }
    return ans;
}

Compilation message

holiday.cpp: In member function 'void PST::upd(int, int, int, int, int, ll)':
holiday.cpp:22:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = s+e >> 1;
                 ~^~
holiday.cpp: In member function 'll PST::kth(int, int, int, int, int)':
holiday.cpp:44:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = s+e >> 1;
                 ~^~
holiday.cpp: In function 'void go(PST&, int, int, int, int)':
holiday.cpp:61:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = s+e >> 1, id = l, lf;
             ~^~
holiday.cpp:61:31: warning: variable 'lf' set but not used [-Wunused-but-set-variable]
     int m = s+e >> 1, id = l, lf;
                               ^~
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 384 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 53840 KB Output is correct
2 Correct 150 ms 53724 KB Output is correct
3 Correct 167 ms 53812 KB Output is correct
4 Correct 145 ms 53720 KB Output is correct
5 Correct 247 ms 49128 KB Output is correct
6 Correct 55 ms 14216 KB Output is correct
7 Correct 146 ms 26552 KB Output is correct
8 Correct 138 ms 32376 KB Output is correct
9 Correct 40 ms 10032 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 6 ms 1636 KB Output is correct
3 Correct 5 ms 1664 KB Output is correct
4 Correct 10 ms 1536 KB Output is correct
5 Correct 7 ms 1408 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 4 ms 768 KB Output is correct
8 Correct 4 ms 768 KB Output is correct
9 Correct 4 ms 768 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 53768 KB Output is correct
2 Correct 147 ms 53724 KB Output is correct
3 Correct 215 ms 23256 KB Output is correct
4 Correct 10 ms 1408 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 4 ms 768 KB Output is correct
8 Correct 757 ms 54488 KB Output is correct
9 Correct 802 ms 54616 KB Output is correct