oj.uz

Submission #425729

# Submission time Handle Problem Language Result Execution time Memory
425729 2021-06-13T10:37:26 Z Peti Meetings (IOI18_meetings) C++14
60 / 100
 5500 ms 539312 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;

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);
    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){
    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);
    add_node(p, p->L, len);
    for(adat d : p->L->querys){
        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:138:25: warning: 'node::R' will be initialized after [-Wreorder]
  138 |     node *L = nullptr, *R = nullptr;
      |                         ^
meetings.cpp:135:9: warning:   'int node::l' [-Wreorder]
  135 |     int l, r, lc, rc;
      |         ^
meetings.cpp:141:5: warning:   when initialized here [-Wreorder]
  141 |     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 23756 KB Output is correct
2 Correct 26 ms 25028 KB Output is correct
3 Correct 31 ms 24960 KB Output is correct
4 Correct 27 ms 25044 KB Output is correct
5 Correct 30 ms 25036 KB Output is correct
6 Correct 35 ms 25548 KB Output is correct
7 Correct 29 ms 25036 KB Output is correct
8 Correct 32 ms 25328 KB Output is correct
9 Correct 31 ms 25120 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23756 KB Output is correct
2 Correct 26 ms 25028 KB Output is correct
3 Correct 31 ms 24960 KB Output is correct
4 Correct 27 ms 25044 KB Output is correct
5 Correct 30 ms 25036 KB Output is correct
6 Correct 35 ms 25548 KB Output is correct
7 Correct 29 ms 25036 KB Output is correct
8 Correct 32 ms 25328 KB Output is correct
9 Correct 31 ms 25120 KB Output is correct
10 Correct 38 ms 26492 KB Output is correct
11 Correct 37 ms 26528 KB Output is correct
12 Correct 40 ms 26556 KB Output is correct
13 Correct 39 ms 26472 KB Output is correct
14 Correct 46 ms 27460 KB Output is correct
15 Correct 35 ms 26664 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23672 KB Output is correct
2 Correct 120 ms 33024 KB Output is correct
3 Correct 753 ms 89980 KB Output is correct
4 Correct 439 ms 75584 KB Output is correct
5 Correct 592 ms 91400 KB Output is correct
6 Correct 636 ms 88372 KB Output is correct
7 Correct 787 ms 89836 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23672 KB Output is correct
2 Correct 120 ms 33024 KB Output is correct
3 Correct 753 ms 89980 KB Output is correct
4 Correct 439 ms 75584 KB Output is correct
5 Correct 592 ms 91400 KB Output is correct
6 Correct 636 ms 88372 KB Output is correct
7 Correct 787 ms 89836 KB Output is correct
8 Correct 445 ms 77356 KB Output is correct
9 Correct 346 ms 75616 KB Output is correct
10 Correct 423 ms 77440 KB Output is correct
11 Correct 373 ms 75336 KB Output is correct
12 Correct 323 ms 73924 KB Output is correct
13 Correct 411 ms 75672 KB Output is correct
14 Correct 849 ms 94796 KB Output is correct
15 Correct 336 ms 75136 KB Output is correct
16 Correct 721 ms 85436 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23756 KB Output is correct
2 Correct 26 ms 25028 KB Output is correct
3 Correct 31 ms 24960 KB Output is correct
4 Correct 27 ms 25044 KB Output is correct
5 Correct 30 ms 25036 KB Output is correct
6 Correct 35 ms 25548 KB Output is correct
7 Correct 29 ms 25036 KB Output is correct
8 Correct 32 ms 25328 KB Output is correct
9 Correct 31 ms 25120 KB Output is correct
10 Correct 38 ms 26492 KB Output is correct
11 Correct 37 ms 26528 KB Output is correct
12 Correct 40 ms 26556 KB Output is correct
13 Correct 39 ms 26472 KB Output is correct
14 Correct 46 ms 27460 KB Output is correct
15 Correct 35 ms 26664 KB Output is correct
16 Correct 23 ms 23672 KB Output is correct
17 Correct 120 ms 33024 KB Output is correct
18 Correct 753 ms 89980 KB Output is correct
19 Correct 439 ms 75584 KB Output is correct
20 Correct 592 ms 91400 KB Output is correct
21 Correct 636 ms 88372 KB Output is correct
22 Correct 787 ms 89836 KB Output is correct
23 Correct 445 ms 77356 KB Output is correct
24 Correct 346 ms 75616 KB Output is correct
25 Correct 423 ms 77440 KB Output is correct
26 Correct 373 ms 75336 KB Output is correct
27 Correct 323 ms 73924 KB Output is correct
28 Correct 411 ms 75672 KB Output is correct
29 Correct 849 ms 94796 KB Output is correct
30 Correct 336 ms 75136 KB Output is correct
31 Correct 721 ms 85436 KB Output is correct
32 Correct 3306 ms 402708 KB Output is correct
33 Correct 2347 ms 400676 KB Output is correct
34 Correct 3346 ms 418304 KB Output is correct
35 Correct 4265 ms 417324 KB Output is correct
36 Correct 2843 ms 407436 KB Output is correct
37 Correct 3455 ms 422032 KB Output is correct
38 Execution timed out 5594 ms 539312 KB Time limit exceeded
39 Halted 0 ms 0 KB -