oj.uz

Submission #116148

# Submission time Handle Problem Language Result Execution time Memory
116148 2019-06-10T23:58:28 Z RezwanArefin01 Holiday (IOI14_holiday) C++17
100 / 100
 949 ms 9056 KB 
#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;

typedef long long ll;

const int N = 1e5 + 10;
int pos[N], p[N], a[N], n, d;

struct Node {
    ll sum; int cnt; 
    Node(ll sum = 0, int cnt = 0) : 
        sum(sum), cnt(cnt) {} 
} t[N << 2]; 

Node merge(Node a, Node b) { 
    return Node(a.sum + b.sum, a.cnt + b.cnt); 
}

void update(int node, int l, int r, int i, int x) {
    if(l == r) { 
        if(x >= 0) t[node] = Node(x, 1);
        else t[node] = Node(0, 0);
        return; 
    } int m = l + r >> 1; 
    if(i <= m) update(node << 1, l, m, i, x); 
    else update(node << 1 | 1, m + 1, r, i, x); 
    t[node] = merge(t[node << 1], t[node << 1 | 1]); 
}

ll query(int node, int k) {
    if(t[node].cnt <= k) return t[node].sum;
    if(t[node << 1].cnt >= k) return query(node << 1, k);
    else return query(node << 1 | 1, k - t[node << 1].cnt) + t[node << 1].sum;
}

ll ans; 
int start; 

void recurr(int l, int r, int b, int e) {
    if(l > r) return;
    int m = l + r >> 1, opt; 
    ll mx = 0;

    for(int i = l; i <= m; ++i)
        update(1, 0, n - 1, pos[i], a[i]);

    for(int i = e; i >= b; --i) {
        update(1, 0, n - 1, pos[i], a[i]); 
        int k = d - (m - start) - (m - i); 
        if(k <= 0) break; 
        ll now = query(1, k); 
        if(now > mx) mx = now, opt = i; 
    }
    if(mx > ans) ans = mx; 

    for(int i = e; i >= b; --i) 
        update(1, 0, n - 1, pos[i], -1); 
    recurr(m + 1, r, opt, e);

    for(int i = l; i <= m; ++i)
        update(1, 0, n - 1, pos[i], -1); 
    for(int i = e; i > opt; --i) 
        update(1, 0, n - 1, pos[i], a[i]); 
    recurr(l, m - 1, b, opt);

    for(int i = e; i > opt; --i) 
        update(1, 0, n - 1, pos[i], -1); 
}

void solve(int st) {
    iota(p, p + n, 0);
    sort(p, p + n, [](int i, int j) { return a[i] > a[j]; });
    for(int i = 0; i < n; ++i) pos[p[i]] = i;

    start = st; 
    recurr(st, min(n - 1, st + (d - 1) / 2), 0, st); 
}

ll findMaxAttraction(int _n, int _start, int _d, int _a[]) {
    n = _n, d = _d; 
    copy(_a, _a + n, a);

    solve(_start);
    reverse(a, a + n); 
    solve(n - _start - 1); 

    return ans;
}

Compilation message

holiday.cpp: In function 'void update(int, int, int, int, int)':
holiday.cpp:25:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     } int m = l + r >> 1; 
               ~~^~~
holiday.cpp: In function 'void recurr(int, int, int, int)':
holiday.cpp:42:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1, opt; 
             ~~^~~
holiday.cpp:65:11: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
     recurr(l, m - 1, b, opt);
     ~~~~~~^~~~~~~~~~~~~~~~~~
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 7 ms 6656 KB Output is correct
2 Correct 7 ms 6528 KB Output is correct
3 Correct 7 ms 6656 KB Output is correct
4 Correct 7 ms 6528 KB Output is correct
5 Correct 6 ms 6656 KB Output is correct
6 Correct 7 ms 6656 KB Output is correct
7 Correct 6 ms 6656 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 8192 KB Output is correct
2 Correct 251 ms 8192 KB Output is correct
3 Correct 256 ms 8312 KB Output is correct
4 Correct 234 ms 8320 KB Output is correct
5 Correct 293 ms 8288 KB Output is correct
6 Correct 88 ms 7288 KB Output is correct
7 Correct 152 ms 7552 KB Output is correct
8 Correct 153 ms 7680 KB Output is correct
9 Correct 59 ms 6912 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6656 KB Output is correct
2 Correct 11 ms 6656 KB Output is correct
3 Correct 11 ms 6656 KB Output is correct
4 Correct 20 ms 6656 KB Output is correct
5 Correct 19 ms 6656 KB Output is correct
6 Correct 9 ms 6656 KB Output is correct
7 Correct 9 ms 6656 KB Output is correct
8 Correct 9 ms 6656 KB Output is correct
9 Correct 8 ms 6656 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 8192 KB Output is correct
2 Correct 248 ms 8312 KB Output is correct
3 Correct 186 ms 7424 KB Output is correct
4 Correct 17 ms 6656 KB Output is correct
5 Correct 10 ms 6656 KB Output is correct
6 Correct 9 ms 6656 KB Output is correct
7 Correct 9 ms 6656 KB Output is correct
8 Correct 912 ms 9056 KB Output is correct
9 Correct 949 ms 8952 KB Output is correct