oj.uz

Submission #425641

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

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){
        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){
            //cout<<"insert line "<<l<<" "<<r<<"\n";
            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;

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

gnode build(int l, int r, int lc, int rc){
    if(l+1 == r){
        gnode temp = new node(nullptr, nullptr, l, r, lc, rc);
        temp->ert = h[l];
        return temp;
    }
    int m = maxST.query(l, r);
    int c = h[m];
    if(m == l) m++;
    gnode p = new node(build(l, m, lc, c), build(m, r, c, rc), l, r, lc, rc);
    p->ert = min(p->L->ert + (long long)(r-m)*c, p->R->ert + (long long)(m-l)*c);
    return p;
}

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];
gnode 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);
    //cout<<"node add: "<<p->r<<" "<<os->r<<"\n";
    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;
}

void bejar(gnode p, int len){
    //kiir(p);
    if(p->l+1 == p->r){
        for(adat d : vegek[p->l]){
            int m = lower_bound(starts, starts+len, d.l)-starts;
            if(m == len) continue;
            buffer[m]->querys.push_back(d);
        }
        return;
    }
    bejar(p->L, len);
    starts[len] = p->l;
    buffer[len] = p->L;
    bejar(p->R, len+1);
    //if(p->L->l == 1 && p->L->r == 4)
    add_node(p, p->L, len);
    for(adat d : p->L->querys){
        //cout<<"query: ---------------------------\n";
        //kiir(p->L);
        //cout<<d.r+1<<" ind\n";
        meg[d.ind] = min(meg[d.ind], lichao.query(d.r+1) + (long long)(p->L->l-d.l)*p->lc);
    }
}

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});
    bejar(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});
    bejar(build(0, n, 0, 0), 0);

    return meg;
}

Compilation message

meetings.cpp: In constructor 'node::node(node*, node*, int, int, int, int)':
meetings.cpp:136:25: warning: 'node::R' will be initialized after [-Wreorder]
  136 |     node *L = nullptr, *R = nullptr;
      |                         ^
meetings.cpp:133:9: warning:   'int node::l' [-Wreorder]
  133 |     int l, r, lc, rc;
      |         ^
meetings.cpp:139:5: warning:   when initialized here [-Wreorder]
  139 |     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) {};
      |     ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23684 KB Output is correct
2 Correct 24 ms 24908 KB Output is correct
3 Correct 26 ms 24980 KB Output is correct
4 Correct 25 ms 24908 KB Output is correct
5 Correct 25 ms 25016 KB Output is correct
6 Correct 31 ms 25292 KB Output is correct
7 Correct 27 ms 24944 KB Output is correct
8 Correct 29 ms 25164 KB Output is correct
9 Correct 28 ms 25092 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23684 KB Output is correct
2 Correct 24 ms 24908 KB Output is correct
3 Correct 26 ms 24980 KB Output is correct
4 Correct 25 ms 24908 KB Output is correct
5 Correct 25 ms 25016 KB Output is correct
6 Correct 31 ms 25292 KB Output is correct
7 Correct 27 ms 24944 KB Output is correct
8 Correct 29 ms 25164 KB Output is correct
9 Correct 28 ms 25092 KB Output is correct
10 Correct 35 ms 26404 KB Output is correct
11 Correct 41 ms 26376 KB Output is correct
12 Correct 36 ms 26364 KB Output is correct
13 Correct 32 ms 26320 KB Output is correct
14 Correct 45 ms 27072 KB Output is correct
15 Correct 32 ms 26436 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23696 KB Output is correct
2 Correct 106 ms 31960 KB Output is correct
3 Correct 689 ms 83216 KB Output is correct
4 Correct 468 ms 75572 KB Output is correct
5 Correct 625 ms 86704 KB Output is correct
6 Correct 673 ms 84672 KB Output is correct
7 Correct 753 ms 85136 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23696 KB Output is correct
2 Correct 106 ms 31960 KB Output is correct
3 Correct 689 ms 83216 KB Output is correct
4 Correct 468 ms 75572 KB Output is correct
5 Correct 625 ms 86704 KB Output is correct
6 Correct 673 ms 84672 KB Output is correct
7 Correct 753 ms 85136 KB Output is correct
8 Correct 466 ms 76644 KB Output is correct
9 Correct 359 ms 74932 KB Output is correct
10 Correct 417 ms 76784 KB Output is correct
11 Correct 399 ms 75288 KB Output is correct
12 Correct 328 ms 73796 KB Output is correct
13 Correct 381 ms 75736 KB Output is correct
14 Correct 893 ms 88492 KB Output is correct
15 Correct 368 ms 75112 KB Output is correct
16 Correct 698 ms 82148 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23684 KB Output is correct
2 Correct 24 ms 24908 KB Output is correct
3 Correct 26 ms 24980 KB Output is correct
4 Correct 25 ms 24908 KB Output is correct
5 Correct 25 ms 25016 KB Output is correct
6 Correct 31 ms 25292 KB Output is correct
7 Correct 27 ms 24944 KB Output is correct
8 Correct 29 ms 25164 KB Output is correct
9 Correct 28 ms 25092 KB Output is correct
10 Correct 35 ms 26404 KB Output is correct
11 Correct 41 ms 26376 KB Output is correct
12 Correct 36 ms 26364 KB Output is correct
13 Correct 32 ms 26320 KB Output is correct
14 Correct 45 ms 27072 KB Output is correct
15 Correct 32 ms 26436 KB Output is correct
16 Correct 19 ms 23696 KB Output is correct
17 Correct 106 ms 31960 KB Output is correct
18 Correct 689 ms 83216 KB Output is correct
19 Correct 468 ms 75572 KB Output is correct
20 Correct 625 ms 86704 KB Output is correct
21 Correct 673 ms 84672 KB Output is correct
22 Correct 753 ms 85136 KB Output is correct
23 Correct 466 ms 76644 KB Output is correct
24 Correct 359 ms 74932 KB Output is correct
25 Correct 417 ms 76784 KB Output is correct
26 Correct 399 ms 75288 KB Output is correct
27 Correct 328 ms 73796 KB Output is correct
28 Correct 381 ms 75736 KB Output is correct
29 Correct 893 ms 88492 KB Output is correct
30 Correct 368 ms 75112 KB Output is correct
31 Correct 698 ms 82148 KB Output is correct
32 Correct 3357 ms 401232 KB Output is correct
33 Correct 2624 ms 386520 KB Output is correct
34 Correct 3234 ms 404204 KB Output is correct
35 Correct 3642 ms 403152 KB Output is correct
36 Correct 2460 ms 407236 KB Output is correct
37 Correct 3463 ms 421660 KB Output is correct
38 Execution timed out 5538 ms 509320 KB Time limit exceeded
39 Halted 0 ms 0 KB -