oj.uz

Submission #970538

# Submission time Handle Problem Language Result Execution time Memory
970538 2024-04-26T16:47:24 Z jamesbamber Meetings (IOI18_meetings) C++17
36 / 100
 748 ms 9820 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct segment{
    struct node{
        int pref, suff, sz, mx;
        node(): pref(0), suff(0), mx(0), sz(0) {}
        node(int val): pref(val), suff(val), mx(val), sz(1) {}
        node(node a, node b) {
            pref = a.pref;
            if(a.mx == a.sz) pref = a.sz + b.pref;
            suff = b.suff;
            if(b.mx == b.sz) suff = b.sz + a.suff;
            sz = a.sz + b.sz;
            mx = max({a.mx, b.mx, a.suff + b.pref});
        }
    };  
    vector<node> tr;

    void build(int v, int l, int r, vector<int> &vec){
        if(r-l == 1){
            tr[v] = node(vec[l] == 1);
            return;
        }
        int m = (l+r)/2;
        build(2*v, l, m, vec);
        build(2*v+1, m, r, vec);
        tr[v] = node(tr[2*v], tr[2*v+1]);
        //cerr << v << " " << l << " " << r << " " << tr[v].mx << " " << tr[v].sz << " " << tr[v].pref << " " << tr[v].suff << endl;
    }

    segment(int sz, vector<int> &vec){
        tr.resize(4*sz);
        build(1, 0, sz, vec);
    }

    node query(int v, int l, int r, int ql, int qr){
        if(l >= qr  or r <= ql) return node();
        if(l >= ql and r <= qr) return tr[v];
        int m = (l+r)/2;
        return node(query(2*v, l, m, ql, qr), query(2*v+1, m, r, ql, qr));
    }
};

vector<long long> quadratic(vector<int> H, vector<int> L, vector<int> R) {
    int Q = L.size();
    vector<ll> ans(Q);

    for(int q=0; q<Q; q++){
        int l = L[q], r = R[q]+1;
        int sz = r-l;
        vector<ll> pref(sz), suff(sz);
        stack<pair<ll,ll>> s;
        ll curr = 0;
        for(int i=l; i<r; i++){
            ll rm = 0;
            while(s.size() and s.top().first <= H[i]){
                rm += s.top().second;
                curr -= s.top().first*s.top().second;
                s.pop();
            }
            s.push({H[i], rm+1});
            curr += H[i]*(rm+1);
            pref[i-l] = curr;
        }

        while(s.size()) s.pop();
        curr = 0;
        for(int i=r-1; i>=l; i--){
            ll rm = 0;
            while(s.size() and s.top().first <= H[i]){
                rm += s.top().second;
                curr -= s.top().first*s.top().second;
                s.pop();
            }
            s.push({H[i], rm+1});
            curr += H[i]*(rm+1);
            suff[i-l] = curr;
        }

        ll mn = min(pref[sz-1], suff[0]);
        for(int i=1; i<sz; i++){
            mn = min(mn, pref[i-1]+suff[i]);
        }
        ans[q] = mn;
    }

    return ans;
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {

    int Q = L.size(); int N = H.size();
    if(N <= 5000 and Q <= 5000) return quadratic(H, L, R);

    vector<ll> ans(Q);

    segment st(N, H);

    for(int q=0; q<Q; q++){
        int l = L[q], r = R[q]+1;
        ans[q] = 2*(r-l) - st.query(1, 0, N, l, r).mx;
    }
    return ans;
}

Compilation message

meetings.cpp: In constructor 'segment::node::node()':
meetings.cpp:9:29: warning: 'segment::node::mx' will be initialized after [-Wreorder]
    9 |         int pref, suff, sz, mx;
      |                             ^~
meetings.cpp:9:25: warning:   'int segment::node::sz' [-Wreorder]
    9 |         int pref, suff, sz, mx;
      |                         ^~
meetings.cpp:10:9: warning:   when initialized here [-Wreorder]
   10 |         node(): pref(0), suff(0), mx(0), sz(0) {}
      |         ^~~~
meetings.cpp: In constructor 'segment::node::node(int)':
meetings.cpp:9:29: warning: 'segment::node::mx' will be initialized after [-Wreorder]
    9 |         int pref, suff, sz, mx;
      |                             ^~
meetings.cpp:9:25: warning:   'int segment::node::sz' [-Wreorder]
    9 |         int pref, suff, sz, mx;
      |                         ^~
meetings.cpp:11:9: warning:   when initialized here [-Wreorder]
   11 |         node(int val): pref(val), suff(val), mx(val), sz(1) {}
      |         ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 444 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 444 KB Output is correct
10 Correct 236 ms 876 KB Output is correct
11 Correct 748 ms 856 KB Output is correct
12 Correct 232 ms 848 KB Output is correct
13 Correct 744 ms 856 KB Output is correct
14 Correct 185 ms 1364 KB Output is correct
15 Correct 186 ms 876 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 26 ms 2140 KB Output is correct
3 Correct 62 ms 9816 KB Output is correct
4 Correct 62 ms 9820 KB Output is correct
5 Correct 47 ms 9812 KB Output is correct
6 Correct 59 ms 9820 KB Output is correct
7 Correct 67 ms 9816 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 26 ms 2140 KB Output is correct
3 Correct 62 ms 9816 KB Output is correct
4 Correct 62 ms 9820 KB Output is correct
5 Correct 47 ms 9812 KB Output is correct
6 Correct 59 ms 9820 KB Output is correct
7 Correct 67 ms 9816 KB Output is correct
8 Incorrect 61 ms 9812 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 344 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 444 KB Output is correct
10 Correct 236 ms 876 KB Output is correct
11 Correct 748 ms 856 KB Output is correct
12 Correct 232 ms 848 KB Output is correct
13 Correct 744 ms 856 KB Output is correct
14 Correct 185 ms 1364 KB Output is correct
15 Correct 186 ms 876 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 26 ms 2140 KB Output is correct
18 Correct 62 ms 9816 KB Output is correct
19 Correct 62 ms 9820 KB Output is correct
20 Correct 47 ms 9812 KB Output is correct
21 Correct 59 ms 9820 KB Output is correct
22 Correct 67 ms 9816 KB Output is correct
23 Incorrect 61 ms 9812 KB Output isn't correct
24 Halted 0 ms 0 KB -