oj.uz

Submission #426029

# Submission time Handle Problem Language Result Execution time Memory
426029 2021-06-13T13:06:20 Z Peti Meetings (IOI18_meetings) C++14
60 / 100
 5500 ms 335008 KB 
#include <bits/stdc++.h>
#include "meetings.h"

#pragma GCC optimize("Ofast")

using namespace std;

const long long INF = (long long)1e18;

struct segment_tree{
    vector<int> st, v;
    int maxn;

    int get(int x, int y){
        if(x == maxn) return y;
        if(y == maxn) return x;
        return v[x] >= v[y] ? x : y;
    }

    void init(vector<int> ert, int n){
        maxn = n;
        while(maxn != (maxn&(-maxn))) maxn += (maxn&(-maxn));
        v = ert;
        st.resize(maxn<<1, maxn);
        iota(st.begin()+maxn, st.begin()+maxn+n, 0);
        for(int i = maxn-1; i > 0; i--)
            st[i] = get(st[2*i], st[2*i+1]);
    }

    int query(int s, int e, int x, int l, int r){
        if(e <= l || r <= s)
            return maxn;
        if(s <= l && r <= e)
            return st[x];
        int m = (l+r)/2;
        return get(query(s, e, 2*x, l, m), query(s, e, 2*x+1, m, r));
    }

    int query(int l, int r){
        return query(l, r, 1, 0, maxn);
    }
};

struct egyenes{
    long long m, b;
    egyenes(){}
    egyenes(long long m, long long b) : m(m), b(b) {}
    long long ertek(long long x) { return m*x+b; }
};

struct lichao_tree{
    vector<egyenes> st;
    vector<long long> prop;
    int maxn;

    void init(int n){
        maxn = n;
        while(maxn != (maxn&(-maxn))) maxn += (maxn&(-maxn));
        st.assign(maxn<<1, egyenes(0, INF));
        prop.assign(maxn<<1, 0);
    }

    void propagate(int x){
        st[x].b += prop[x];
        if(x < maxn){
            prop[2*x] += prop[x];
            prop[2*x+1] += prop[x];
        }
        prop[x] = 0;
    }


    void add(egyenes e, int x, int l, int r){
        if(e.m == 0ll) return;
        propagate(x);
        int m = (l+r)/2;
        bool bal = e.ertek(l) < st[x].ertek(l);
        bool koz = e.ertek(m) < st[x].ertek(m);
        if(koz) swap(st[x], e);
        if(l+1 == r) return;
        if(bal == koz)
            add(e, 2*x+1, m, r);
        else
            add(e, 2*x, l, m);
    }

    void update(int s, int e, egyenes eg, int x, int l, int r){
        propagate(x);
        if(e <= l || r <= s)
            return;
        if(s <= l && r <= e){
            add(eg, x, l, r);
            return;
        }
        int m = (l+r)/2;
        update(s, e, eg, 2*x, l, m);
        update(s, e, eg, 2*x+1, m, r);
    }

    void update(int l, int r, egyenes e) { update(l, r, e, 1, 0, maxn); }

    void update_lines(int s, int e, long long c, int x, int l, int r){
        propagate(x);
        if(e <= l || r <= s)
            return;
        if(s <= l && r <= e){
            prop[x] += c;
            return;
        }
        int m = (l+r)/2;
        update_lines(s, e, c, 2*x, l, m);
        update_lines(s, e, c, 2*x+1, m, r);
    }

    void update_lines(int l, int r, long long c) { update_lines(l, r, c, 1, 0, maxn); }

    long long query(int ind, int x, int l, int r){
        propagate(x);
        if(l+1 == r)
            return st[x].ertek(ind);
        int m = (l+r)/2;
        if(ind < m)
            return min(st[x].ertek(ind), query(ind, 2*x, l, m));
        return min(st[x].ertek(ind), query(ind, 2*x+1, m, r));
    }

    long long query(int x) { return query(x, 1, 0, maxn); }
};

struct adat{
    int ind, l, r;
};

/*struct node{
    int l, r, lc, rc;
    long long ert;
    vector<adat> querys;
    node *L = nullptr, *R = nullptr;

    node(){}
    node(node *L, node *R, int l, int r, int lc, int rc) : L(L), R(R), l(l), r(r), lc(lc), rc(rc) {};
};
typedef node* gnode;*/

struct gnode{
    int l, r, lc, rc;
    long long ert;
};

segment_tree maxST;
lichao_tree lichao;
vector<int> h;

/*void kiir(gnode p){
    cout<<"node: ("<<(p->l)<<", "<<(p->r)<<")  ert: "<<p->ert<<"  cl: "<<p->lc<<"  cr: "<<p->rc<<"\n";
}*/
vector<vector<adat>> vegek((int)1e6);
vector<long long> meg;

int starts[(int)1e6];
vector<adat> buffer[(int)1e6];

void add_node(gnode os, gnode p, int ind){
    long long ossz = (long long)(p.r-p.l)*p.rc;
    if(h[p.l] > p.rc) ossz += (long long)(h[p.l] - p.rc);
    lichao.update_lines(p.r, os.r, ossz);
    lichao.update(p.r, os.r, {p.rc, p.ert-(long long)p.rc*p.r});
    return;
}

long long build(int l, int r, int lc, int rc, int len){
    if(l+1 == r){
        for(adat d : vegek[l]){
            int m = lower_bound(starts, starts+len, d.l)-starts;
            if(m == len) continue;
            buffer[m].push_back(d);
        }
        return h[l];
    }
    int m = maxST.query(l, r);
    int c = h[m];
    starts[len] = l;
    buffer[len].clear();
    if(m == l) m++;

    long long lb = build(l, m, lc, c, len+1);
    long long rb = build(m, r, c, rc, len+1);

    long long ert = min(lb + (long long)(r-m)*c, rb + (long long)(m-l)*c);
    add_node({l, r, lc, rc, ert}, {l, m, lc, c, lb}, len);

    for(adat d : buffer[len]){
        meg[d.ind] = min(meg[d.ind], lichao.query(d.r+1) + (long long)(l-d.l)*lc);
    }

    return ert;
}

/*void bejar(gnode p, int len){
    if(p->l+1 == p->r){
        return;
    }
    bejar(p->L, len);
    bejar(p->R, len+1);
}*/

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
    H.push_back((int)1e9+1);
    H.insert(H.begin(), (int)1e9+1);
    int n = (int)H.size();
    int q = (int)L.size();
    h = H;
    meg.assign(q, INF);
    vegek.assign((int)1e6, vector<adat>());

    maxST.init(H, n);
    lichao.init(n);
    for(int i = 0; i < q; i++)
        vegek[R[i]+2].push_back({i, L[i]+1, R[i]+1});
    build(0, n, 0, 0, 0);

    for(int i = 0; i < q; i++)
        vegek[R[i]+2].clear();

    reverse(h.begin(), h.end());
    maxST.init(h, n);
    for(int i = 0; i < q; i++)
        vegek[n-L[i]-1].push_back({i, n-R[i]-2, n-L[i]-2});
    build(0, n, 0, 0, 0);

    return meg;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 47244 KB Output is correct
2 Correct 38 ms 47516 KB Output is correct
3 Correct 39 ms 47584 KB Output is correct
4 Correct 40 ms 47596 KB Output is correct
5 Correct 38 ms 47608 KB Output is correct
6 Correct 42 ms 48212 KB Output is correct
7 Correct 38 ms 47552 KB Output is correct
8 Correct 43 ms 47920 KB Output is correct
9 Correct 41 ms 47720 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 47244 KB Output is correct
2 Correct 38 ms 47516 KB Output is correct
3 Correct 39 ms 47584 KB Output is correct
4 Correct 40 ms 47596 KB Output is correct
5 Correct 38 ms 47608 KB Output is correct
6 Correct 42 ms 48212 KB Output is correct
7 Correct 38 ms 47552 KB Output is correct
8 Correct 43 ms 47920 KB Output is correct
9 Correct 41 ms 47720 KB Output is correct
10 Correct 46 ms 48324 KB Output is correct
11 Correct 42 ms 48264 KB Output is correct
12 Correct 48 ms 48300 KB Output is correct
13 Correct 44 ms 48324 KB Output is correct
14 Correct 56 ms 49464 KB Output is correct
15 Correct 46 ms 48312 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47264 KB Output is correct
2 Correct 112 ms 53408 KB Output is correct
3 Correct 717 ms 81444 KB Output is correct
4 Correct 418 ms 65196 KB Output is correct
5 Correct 618 ms 81108 KB Output is correct
6 Correct 582 ms 76804 KB Output is correct
7 Correct 700 ms 81388 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47264 KB Output is correct
2 Correct 112 ms 53408 KB Output is correct
3 Correct 717 ms 81444 KB Output is correct
4 Correct 418 ms 65196 KB Output is correct
5 Correct 618 ms 81108 KB Output is correct
6 Correct 582 ms 76804 KB Output is correct
7 Correct 700 ms 81388 KB Output is correct
8 Correct 473 ms 67680 KB Output is correct
9 Correct 324 ms 66360 KB Output is correct
10 Correct 461 ms 67844 KB Output is correct
11 Correct 433 ms 65948 KB Output is correct
12 Correct 340 ms 64672 KB Output is correct
13 Correct 396 ms 64964 KB Output is correct
14 Correct 839 ms 86532 KB Output is correct
15 Correct 386 ms 64176 KB Output is correct
16 Correct 639 ms 76548 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 47244 KB Output is correct
2 Correct 38 ms 47516 KB Output is correct
3 Correct 39 ms 47584 KB Output is correct
4 Correct 40 ms 47596 KB Output is correct
5 Correct 38 ms 47608 KB Output is correct
6 Correct 42 ms 48212 KB Output is correct
7 Correct 38 ms 47552 KB Output is correct
8 Correct 43 ms 47920 KB Output is correct
9 Correct 41 ms 47720 KB Output is correct
10 Correct 46 ms 48324 KB Output is correct
11 Correct 42 ms 48264 KB Output is correct
12 Correct 48 ms 48300 KB Output is correct
13 Correct 44 ms 48324 KB Output is correct
14 Correct 56 ms 49464 KB Output is correct
15 Correct 46 ms 48312 KB Output is correct
16 Correct 34 ms 47264 KB Output is correct
17 Correct 112 ms 53408 KB Output is correct
18 Correct 717 ms 81444 KB Output is correct
19 Correct 418 ms 65196 KB Output is correct
20 Correct 618 ms 81108 KB Output is correct
21 Correct 582 ms 76804 KB Output is correct
22 Correct 700 ms 81388 KB Output is correct
23 Correct 473 ms 67680 KB Output is correct
24 Correct 324 ms 66360 KB Output is correct
25 Correct 461 ms 67844 KB Output is correct
26 Correct 433 ms 65948 KB Output is correct
27 Correct 340 ms 64672 KB Output is correct
28 Correct 396 ms 64964 KB Output is correct
29 Correct 839 ms 86532 KB Output is correct
30 Correct 386 ms 64176 KB Output is correct
31 Correct 639 ms 76548 KB Output is correct
32 Correct 3027 ms 176928 KB Output is correct
33 Correct 2270 ms 166792 KB Output is correct
34 Correct 3315 ms 168728 KB Output is correct
35 Correct 3733 ms 183520 KB Output is correct
36 Correct 2171 ms 179420 KB Output is correct
37 Correct 3027 ms 187948 KB Output is correct
38 Execution timed out 5604 ms 335008 KB Time limit exceeded
39 Halted 0 ms 0 KB -