oj.uz

Submission #615130

# Submission time Handle Problem Language Result Execution time Memory
615130 2022-07-31T07:03:52 Z wiwiho Meetings (IOI18_meetings) C++14
100 / 100
 2500 ms 434144 KB 
#include "meetings.h"
 
#include <bits/stdc++.h>
#include <bits/extc++.h>
 
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;
 
const ll MOD = 1000000007;
const ll MAX = 1LL << 60;
 
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}
 
ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}
 
ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}
 
int n, q;

vector<ll> h;
struct SparseTable{
    vector<vector<int>> st;
    int argmin(int x, int y){
        if(h[x] == h[y]) return x < y ? x : y;
        else return h[x] > h[y] ? x : y;
    }
    void init(){
        st.resize(20, vector<int>(n + 1));
        iota(iter(st[0]), 0);
        for(int i = 1; i < 20; i++){
            for(int j = 1; j + (1 << i) - 1 <= n; j++){
                st[i][j] = argmin(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
    int query(int l, int r){
        int lg = __lg(r - l + 1);
        return argmin(st[lg][l], st[lg][r - (1 << lg) + 1]);
    }
};

SparseTable stb;

struct Node{
    ll mn = 0, mx = 0;
    ll a = 0, b = 0;
};

#define lc 2 * id + 1
#define rc 2 * id + 2

struct SegmentTree{
    vector<Node> st;

    void init(){
        st.resize(4 * n);
    }

    void addtag(ll a, ll b, int L, int R, int id){
        if(a == 0){
            st[id].mn += b;
            st[id].mx += b;
            st[id].b += b;
        }
        else{
            st[id].mn = a * L + b;
            st[id].mx = a * R + b;
            st[id].a = a;
            st[id].b = b;
        }
    }

    void push(int L, int R, int id){
        int M = (L + R) / 2;
        addtag(st[id].a, st[id].b, L, M, lc);
        addtag(st[id].a, st[id].b, M + 1, R, rc);
        st[id].a = st[id].b = 0;
    }

    void pull(int id){
        st[id].mn = min(st[lc].mn, st[rc].mn);
        st[id].mx = max(st[lc].mx, st[rc].mx);
    }

    void modify(int l, int r, ll a, ll b, int L = 1, int R = n, int id = 0){
        if(l > r) return;
        if(l <= L && R <= r){
            if(a == 0){
                addtag(a, b, L, R, id);
                return;
            }
            if(st[id].mn <= min(L * a + b, R * a + b)) return;
            if(st[id].mx >= max(L * a + b, R * a + b)){
                addtag(a, b, L, R, id);
                return;
            }
        }
        push(L, R, id);
        int M = (L + R) / 2;
        if(r <= M) modify(l, r, a, b, L, M, lc);
        else if(l > M) modify(l, r, a, b, M + 1, R, rc);
        else{
            modify(l, r, a, b, L, M, lc);
            modify(l, r, a, b, M + 1, R, rc);
        }
        pull(id);
    }

    ll query(int x, int L = 1, int R = n, int id = 0){
        if(L == R) return st[id].mn;
        push(L, R, id);
        int M = (L + R) / 2;
        if(x <= M) return query(x, L, M, lc);
        else return query(x, M + 1, R, rc);
    }
};

SegmentTree stl, str;
vector<ll> ans;
vector<vector<int>> qry;
vector<int> L, R;

void dfs(int l, int r){
    if(l > r) return;
    int mid = stb.query(l, r);
    dfs(l, mid - 1);
    dfs(mid + 1, r);

    for(int i : qry[mid]){
        ans[i] = min(stl.query(L[i]) + (R[i] - mid + 1) * h[mid], 
                str.query(R[i]) + (mid - L[i] + 1) * h[mid]);
    }
    
    stl.modify(l, mid, 0, (r - mid + 1) * h[mid]);
    str.modify(mid, r, 0, (mid - l + 1) * h[mid]);
    if(l < mid){
        ll tmp = str.query(mid - 1);
        str.modify(mid, r, h[mid], h[mid] * (-mid + 1) + tmp);
    }
    if(mid < r){
        ll tmp = stl.query(mid + 1);
        stl.modify(l, mid, -h[mid], h[mid] * (mid + 1) + tmp);
    }

    /*cerr << "dfs " << l << " " << r << " " << mid << "\n";
    for(int i = l; i < mid; i++) cerr << stl.query(i) << " ";
    cerr << ", ";
    cerr << stl.query(mid) << " " << str.query(mid) << " , ";
    for(int i = mid + 1; i <= r; i++) cerr << str.query(i) << " ";
    cerr << "\n";*/

}
 
vector<ll> minimum_costs(vector<int> H, vector<int> _L, vector<int> _R){
    n = H.size();
    q = _L.size();
 
    h.resize(n + 1);
    for(int i = 0; i < n; i++) h[i + 1] = H[i];
    L = _L; R = _R;
    for(int i = 0; i < q; i++) L[i]++, R[i]++;
    ans.resize(q, MAX);

    stb.init();
    stl.init();
    str.init();

    qry.resize(n + 1);
    for(int i = 0; i < q; i++){
        int mid = stb.query(L[i], R[i]);
        qry[mid].eb(i);
    }

    dfs(1, n);
 
    return ans;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 1368 KB Output is correct
3 Correct 3 ms 1364 KB Output is correct
4 Correct 5 ms 1364 KB Output is correct
5 Correct 4 ms 1364 KB Output is correct
6 Correct 5 ms 1620 KB Output is correct
7 Correct 5 ms 1364 KB Output is correct
8 Correct 5 ms 1620 KB Output is correct
9 Correct 4 ms 1492 KB Output is correct
10 Correct 12 ms 2516 KB Output is correct
11 Correct 8 ms 2468 KB Output is correct
12 Correct 8 ms 2516 KB Output is correct
13 Correct 10 ms 2480 KB Output is correct
14 Correct 12 ms 2820 KB Output is correct
15 Correct 11 ms 2516 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 37 ms 6716 KB Output is correct
3 Correct 240 ms 50508 KB Output is correct
4 Correct 205 ms 43800 KB Output is correct
5 Correct 258 ms 52432 KB Output is correct
6 Correct 212 ms 52760 KB Output is correct
7 Correct 254 ms 53820 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 37 ms 6716 KB Output is correct
3 Correct 240 ms 50508 KB Output is correct
4 Correct 205 ms 43800 KB Output is correct
5 Correct 258 ms 52432 KB Output is correct
6 Correct 212 ms 52760 KB Output is correct
7 Correct 254 ms 53820 KB Output is correct
8 Correct 227 ms 44336 KB Output is correct
9 Correct 243 ms 44196 KB Output is correct
10 Correct 217 ms 44316 KB Output is correct
11 Correct 221 ms 43628 KB Output is correct
12 Correct 244 ms 43968 KB Output is correct
13 Correct 225 ms 43780 KB Output is correct
14 Correct 247 ms 50452 KB Output is correct
15 Correct 223 ms 43660 KB Output is correct
16 Correct 287 ms 50776 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 1368 KB Output is correct
3 Correct 3 ms 1364 KB Output is correct
4 Correct 5 ms 1364 KB Output is correct
5 Correct 4 ms 1364 KB Output is correct
6 Correct 5 ms 1620 KB Output is correct
7 Correct 5 ms 1364 KB Output is correct
8 Correct 5 ms 1620 KB Output is correct
9 Correct 4 ms 1492 KB Output is correct
10 Correct 12 ms 2516 KB Output is correct
11 Correct 8 ms 2468 KB Output is correct
12 Correct 8 ms 2516 KB Output is correct
13 Correct 10 ms 2480 KB Output is correct
14 Correct 12 ms 2820 KB Output is correct
15 Correct 11 ms 2516 KB Output is correct
16 Correct 1 ms 304 KB Output is correct
17 Correct 37 ms 6716 KB Output is correct
18 Correct 240 ms 50508 KB Output is correct
19 Correct 205 ms 43800 KB Output is correct
20 Correct 258 ms 52432 KB Output is correct
21 Correct 212 ms 52760 KB Output is correct
22 Correct 254 ms 53820 KB Output is correct
23 Correct 227 ms 44336 KB Output is correct
24 Correct 243 ms 44196 KB Output is correct
25 Correct 217 ms 44316 KB Output is correct
26 Correct 221 ms 43628 KB Output is correct
27 Correct 244 ms 43968 KB Output is correct
28 Correct 225 ms 43780 KB Output is correct
29 Correct 247 ms 50452 KB Output is correct
30 Correct 223 ms 43660 KB Output is correct
31 Correct 287 ms 50776 KB Output is correct
32 Correct 2303 ms 331492 KB Output is correct
33 Correct 1772 ms 334436 KB Output is correct
34 Correct 1878 ms 330752 KB Output is correct
35 Correct 2095 ms 332060 KB Output is correct
36 Correct 1643 ms 334372 KB Output is correct
37 Correct 1983 ms 331072 KB Output is correct
38 Correct 2376 ms 383804 KB Output is correct
39 Correct 2178 ms 383828 KB Output is correct
40 Correct 2075 ms 337636 KB Output is correct
41 Correct 2328 ms 430968 KB Output is correct
42 Correct 2500 ms 434044 KB Output is correct
43 Correct 2451 ms 434144 KB Output is correct
44 Correct 2498 ms 383348 KB Output is correct