oj.uz

Submission #288329

# Submission time Handle Problem Language Result Execution time Memory
288329 2020-09-01T12:17:57 Z andrew Meetings (IOI18_meetings) C++17
36 / 100
 557 ms 196600 KB 
#include <bits/stdc++.h>
#include "meetings.h"

#define fi first
#define se second
#define p_b push_back
#define m_p make_pair
#define sz(x) (int)x.size()
#define pii pair <int, int>
#define all(x) x.begin(),x.end()

using namespace std;
typedef long long ll;
const ll inf = 1e18;

struct node{
    int pref, suf, size, ans;
};

vector <node> T;

node clr;

node merge(node a, node b){
    if(a.size == 0)return b;
    if(b.size == 0)return a;
    node res;
    res.size = a.size + b.size;
    res.pref = a.pref;
    if(a.pref == a.size)res.pref = a.size + b.pref;
    res.suf = b.suf;
    if(b.suf == b.size)res.suf = b.size + a.suf;
    res.ans = max(a.ans, max(b.ans, a.suf + b.pref));
    return res;
}

void build(int v, int tl, int tr, vector <int> &H){
    if(tl == tr){
        T[v].pref = T[v].suf = T[v].ans = (H[tl] == 1);
        T[v].size = 1;
    }else{
        int tm = (tl + tr) >> 1;
        build(v << 1, tl, tm, H);
        build(v << 1 | 1, tm + 1, tr, H);
        T[v] = merge(T[v << 1], T[v << 1 | 1]);
    }
}

node get(int v, int tl, int tr, int l, int r){
    if(l > r)return clr;
    if(tl == l && tr == r)return T[v];
    int tm = (tl + tr) >> 1;
    return merge(get(v << 1, tl, tm, l, min(r, tm)), get(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r));
}

vector<ll> minimum_costs(vector<int> H, vector<int> l, vector<int> r) {
    int n = sz(H), q = sz(l);
    if(n <= 5000 && q <= 5000){
        vector <ll> ans(q);
        vector < vector <ll> > pre_calc(n, vector <ll> (n, 0));
        for(int x = 0; x < n; x++){
            int mx = H[x];
            ll sc = 0;
            for(int j = x; j < n; j++){
                mx = max(mx, H[j]);
                sc += mx;
                pre_calc[x][j] = sc;
            }
            mx = H[x];
            sc = 0;
            for(int j = x; j >= 0; j--){
                mx = max(mx, H[j]);
                sc += mx;
                pre_calc[x][j] = sc;
            }
        }
        for(int i = 0; i < q; i++){
            ans[i] = pre_calc[l[i]][r[i]];
            for(int x = l[i] + 1; x <= r[i]; x++){
                ans[i] = min(ans[i], pre_calc[x - 1][l[i]] + pre_calc[x][r[i]]);
            }
        }
        return ans;
    }else{
        vector <ll> ans(q);
        T.resize(4 * n + 3);
        build(1, 0, n - 1, H);
        for(int i = 0; i < q; i++){
            ans[i] = 2 * (r[i] - l[i] + 1) - get(1, 0, n - 1, l[i], r[i]).ans;
        }
        return ans;
    }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 58 ms 70904 KB Output is correct
3 Correct 56 ms 71032 KB Output is correct
4 Correct 63 ms 70904 KB Output is correct
5 Correct 57 ms 70904 KB Output is correct
6 Correct 57 ms 70904 KB Output is correct
7 Correct 56 ms 70904 KB Output is correct
8 Correct 55 ms 70904 KB Output is correct
9 Correct 56 ms 70904 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 58 ms 70904 KB Output is correct
3 Correct 56 ms 71032 KB Output is correct
4 Correct 63 ms 70904 KB Output is correct
5 Correct 57 ms 70904 KB Output is correct
6 Correct 57 ms 70904 KB Output is correct
7 Correct 56 ms 70904 KB Output is correct
8 Correct 55 ms 70904 KB Output is correct
9 Correct 56 ms 70904 KB Output is correct
10 Correct 360 ms 196344 KB Output is correct
11 Correct 557 ms 196600 KB Output is correct
12 Correct 361 ms 196472 KB Output is correct
13 Correct 554 ms 196472 KB Output is correct
14 Correct 368 ms 196472 KB Output is correct
15 Correct 365 ms 196472 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 42 ms 2196 KB Output is correct
3 Correct 130 ms 11768 KB Output is correct
4 Correct 130 ms 11768 KB Output is correct
5 Correct 102 ms 11768 KB Output is correct
6 Correct 122 ms 11768 KB Output is correct
7 Correct 133 ms 11640 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 42 ms 2196 KB Output is correct
3 Correct 130 ms 11768 KB Output is correct
4 Correct 130 ms 11768 KB Output is correct
5 Correct 102 ms 11768 KB Output is correct
6 Correct 122 ms 11768 KB Output is correct
7 Correct 133 ms 11640 KB Output is correct
8 Incorrect 129 ms 11768 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 58 ms 70904 KB Output is correct
3 Correct 56 ms 71032 KB Output is correct
4 Correct 63 ms 70904 KB Output is correct
5 Correct 57 ms 70904 KB Output is correct
6 Correct 57 ms 70904 KB Output is correct
7 Correct 56 ms 70904 KB Output is correct
8 Correct 55 ms 70904 KB Output is correct
9 Correct 56 ms 70904 KB Output is correct
10 Correct 360 ms 196344 KB Output is correct
11 Correct 557 ms 196600 KB Output is correct
12 Correct 361 ms 196472 KB Output is correct
13 Correct 554 ms 196472 KB Output is correct
14 Correct 368 ms 196472 KB Output is correct
15 Correct 365 ms 196472 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 42 ms 2196 KB Output is correct
18 Correct 130 ms 11768 KB Output is correct
19 Correct 130 ms 11768 KB Output is correct
20 Correct 102 ms 11768 KB Output is correct
21 Correct 122 ms 11768 KB Output is correct
22 Correct 133 ms 11640 KB Output is correct
23 Incorrect 129 ms 11768 KB Output isn't correct
24 Halted 0 ms 0 KB -