oj.uz

Submission #492221

# Submission time Handle Problem Language Result Execution time Memory
492221 2021-12-06T01:59:06 Z blue Meetings (IOI18_meetings) C++17
60 / 100
 2676 ms 786436 KB 
#include "meetings.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <deque>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using pii = pair<int, int>;
#define sz(x) (int(x.size()))

const int mx = 750'000;
const ll INF = 1'000'000'000'000'000'000LL;


int N;
int Q;

vi H;

vi L, R;
vi M(mx);
vi peak_queries[mx];

vi HD;

vi lc, rc;
vi le, re;
vll ans;










struct segtree
{
    int l;
    int r;
    pii v;

    segtree* left = NULL;
    segtree* right = NULL;


    segtree()
    {
        ;
    }

    segtree(int L, int R, vi& Z)
    {
        l = L;
        r = R;
        if(l == r)
        {
            v = {Z[l], l};
        }
        else
        {
            int m = (l+r)/2;
            left = new segtree(l, m, Z);
            right = new segtree(m+1, r, Z);
            v = max(left->v, right->v);
        }
    }

    pii rangemax(int L, int R)
    {
        if(R < l || r < L) return {-1, -1};
        else if(L <= l && r <= R) return v;
        else return max(left->rangemax(L, R), right->rangemax(L, R));
    }

    void clear_tree()
    {
        if(left != NULL)
        {
            left->clear_tree();
            right->clear_tree();
            delete left;
            delete right;
        }
    }
};

segtree ST;

vi subtree;

int build_tree(int l, int r)
{
    if(r < l) return -1;
    int m = ST.rangemax(l, r).second;
    lc[m] = build_tree(l, m-1);
    rc[m] = build_tree(m+1, r);

    if(lc[m] != -1) subtree[m] += subtree[lc[m]];
    if(rc[m] != -1) subtree[m] += subtree[rc[m]];

    return m;
}

int x1[1'500'000];
int x2[1'500'000];
ll y1[1'500'000];
ll y2[1'500'000];


// struct seg
// {
//     int i;
// };

int seg_ct = -1;

int new_segment(int X1, ll Y1, int X2, ll Y2)
{
    seg_ct++;
    x1[seg_ct] = X1;
    y1[seg_ct] = Y1;
    x2[seg_ct] = X2;
    y2[seg_ct] = Y2;
    return seg_ct;
}

ll get_slope(int i)
{
    if(x2[i] == x1[i]) return 0;
    else return (y2[i]-y1[i])/(x2[i]-x1[i]);
}

struct func
{
    ll lp = 0;
    deque<int> d;

    void inc(ll W)
    {
        lp += W;
    }

    void push_back(func& K)
    {
        for(int k: K.d)
        {
            y1[k] += K.lp - lp;
            y2[k] += K.lp - lp;
            d.push_back(k);
            // d.push_back(seg{k.x1, k.y1 + K.lp - lp, k.x2, k.y2 + K.lp - lp});
        }
    }

    void push_front(func& K)
    {
        reverse(K.d.begin(), K.d.end());
        for(int k: K.d)
        {
            y1[k] += K.lp - lp;
            y2[k] += K.lp - lp;
            d.push_front(k);
            // d.push_front(seg{k.x1, k.y1 + K.lp - lp, k.x2, k.y2 + K.lp - lp});
        }
    }

    void front_AP(ll a, ll sl)
    {
        int xf = x1[d.front()];
        int xb = -1;
        while(!d.empty())
        {
            ll dy2 = y2[d.front()] + lp;
            int dx2 = x2[d.front()];

            ll dy1 = y1[d.front()] + lp;
            int dx1 = x1[d.front()];


            ll new_y2 = a + sl*(dx2 - xf);
            if(new_y2 > dy2) break;
            else if(a > dy1) break;
            else
            {
                xb = max(xb, x2[d.front()]);
                d.pop_front();
            }
        }


        if(!d.empty())
        {
            // cerr << "case X\n";
            ll dy1 = y1[d.front()] + lp;
            ll dx1 = x1[d.front()];


            ll new_y1 = a + sl*(dx1 - xf);
            if(new_y1 <= y1[d[0]] + lp)
            {
                // ll d_sl = (d[0].y2 - d[0].y1)/(d[0].x2 - d[0].x1);
                ll d_sl = get_slope(d[0]);
                int lo = x1[d[0]];
                int hi = x2[d[0]];
                while(lo != hi)
                {
                    int mid = (lo+hi)/2 + 1;
                    ll mid_y = lp + y1[d[0]]+ (mid-x1[d[0]])*d_sl;

                    ll new_y = a + sl*(mid - xf);

                    if(new_y <= mid_y)
                        lo = mid;
                    else
                        hi = mid-1;
                }

                xb = max(xb, lo);

                x1[d[0]] = lo+1;
                y1[d[0]] = y2[d[0]] - (x2[d[0]] - x1[d[0]])*d_sl;

            }
        }


        if(xf <= xb)
        {
            d.push_front(new_segment(xf, a - lp, xb, a+sl*(xb-xf) - lp));
        }
    }
};



vector<func*> F(mx);


void dfs(int u)
{
    if(u == -1) return;

    le[u] = re[u] = u;

    if(lc[u] != -1)
    {
        dfs(lc[u]);
        subtree[u] += subtree[lc[u]];
        le[u] = le[lc[u]];
    }
    if(rc[u] != -1)
    {
        dfs(rc[u]);
        subtree[u] += subtree[rc[u]];
        re[u] = re[rc[u]];
    }

    for(int q: peak_queries[u])
    {
        int lo = 0;
        int hi = sz(F[rc[u]]->d) - 1;
        while(lo != hi)
        {
            int mid = (lo+hi)/2;
            if(x2[F[rc[u]]->d[mid]] < R[q])
                lo = mid+1;
            else
                hi = mid;
        }

        auto fr = F[rc[u]];

        ll right_ans = fr->lp + y1[fr->d[lo]] + get_slope(fr->d[lo])*(R[q] - x1[fr->d[lo]]);


        ans[q] = min(ans[q], ll(H[u])*(u - L[q] + 1) + right_ans);
    }

    ll left_ct = 1;
    if(lc[u] != -1) left_ct += subtree[lc[u]];



    if(rc[u] != -1)
    {
            F[rc[u]]->inc(ll(H[u])*(u - le[u] + 1));
    }


    ll dp_u;
    if(lc[u] == -1)
    {
        dp_u = H[u];
    }
    else
    {
        dp_u = H[u] + y2[F[lc[u]]->d.back()] + F[lc[u]]->lp;
    }


    func ths;
    ths.d.push_back(new_segment(u, dp_u, u, dp_u));

    if(rc[u] != -1)
    {
        F[rc[u]]->front_AP(dp_u + H[u], H[u]);

    }

    if(lc[u] == -1 && rc[u] == -1)
    {
        F[u]->push_back(ths);
    }
    else if(lc[u] == -1)
    {
        F[u] = F[rc[u]];
        F[u]->push_front(ths);
    }
    else if(rc[u] == -1)
    {
        F[u] = F[lc[u]];
        F[u]->push_back(ths);
    }
    else
    {
        if(subtree[rc[u]] >= subtree[lc[u]])
        {
            F[u] = F[rc[u]];
            F[u]->push_front(ths);
            F[u]->push_front(*F[lc[u]]);
            F[lc[u]]->d.clear();
        }
        else
        {
            F[u] = F[lc[u]];
            F[u]->push_back(ths);
            F[u]->push_back(*F[rc[u]]);
            F[rc[u]]->d.clear();
        }
    }

    // ths->d.clear();
    ths.d.clear();
}




vll minimum_costs(vi H_, vi L_, vi R_)
{
    // for(int f: L_) cerr << "le = " << f << '\n';
//PART 1: PROCESS INPUT

    H = H_;
    L = L_;
    R = R_;

    H_.clear();
    L_.clear();
    R_.clear();

    N = sz(H);
    Q = sz(L);

    // cerr << "queries: \n";
    // for(int j = 0; j < Q; j++) cerr << L_[j] << ' ' << R_[j] << '\n';


//PART 2: DISCRETISE HEIGHTS
    HD = vi(N);
    vector<pii> P;
    for(int i = 0; i < N; i++) P.push_back({H[i], i});
    sort(P.begin(), P.end());
    int ct = 0;
    for(pii p:P)
    {
        ct++;
        HD[p.second] = ct;
    }


    // for(int j = 0; j < Q; j++) cerr << j << " : " << M[j] << '\n';

    ans = vll(Q, INF);

    for(int t = 0; t <= 1; t++)
    {

        if(t == 1)
        {
            reverse(HD.begin(), HD.end());
            reverse(H.begin(), H.end());
            for(int j = 0; j < Q; j++)
            {
                L[j] = N-1 - L[j];
                R[j] = N-1 - R[j];
                swap(L[j], R[j]);
                M[j] = N-1 - M[j];
            }
        }

        for(int i = 0; i < N; i++)
        {
            peak_queries[i].clear();
        }

        ST = segtree(0, N-1, HD);
        for(int j = 0; j < Q; j++)
        {
            if(t == 0)
                M[j] = ST.rangemax(L[j], R[j]).second;
            if(M[j] == R[j])
            {
                ans[j] = min(ans[j], ll(H[M[j]])*(R[j] - L[j] + 1));
            }
            else
                peak_queries[M[j]].push_back(j);
        }

        lc = rc = vi(N, -1);
        le = vi(N, 1'000'000'000);
        re = vi(N, -1);
        subtree = vi(N, 1);
        int rt = build_tree(0, N-1);
        ST.clear_tree();

        for(int i = 0; i < N; i++) F[i] = new func;
        dfs(rt);
    }

    return ans;
}

Compilation message

meetings.cpp: In member function 'void func::front_AP(ll, ll)':
meetings.cpp:182:17: warning: unused variable 'dx1' [-Wunused-variable]
  182 |             int dx1 = x1[d.front()];
      |                 ^~~
meetings.cpp:199:16: warning: unused variable 'dy1' [-Wunused-variable]
  199 |             ll dy1 = y1[d.front()] + lp;
      |                ^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26700 KB Output is correct
2 Correct 16 ms 31180 KB Output is correct
3 Correct 17 ms 31180 KB Output is correct
4 Correct 16 ms 31180 KB Output is correct
5 Correct 17 ms 31216 KB Output is correct
6 Correct 16 ms 31564 KB Output is correct
7 Correct 17 ms 31156 KB Output is correct
8 Correct 17 ms 31684 KB Output is correct
9 Correct 18 ms 31384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26700 KB Output is correct
2 Correct 16 ms 31180 KB Output is correct
3 Correct 17 ms 31180 KB Output is correct
4 Correct 16 ms 31180 KB Output is correct
5 Correct 17 ms 31216 KB Output is correct
6 Correct 16 ms 31564 KB Output is correct
7 Correct 17 ms 31156 KB Output is correct
8 Correct 17 ms 31684 KB Output is correct
9 Correct 18 ms 31384 KB Output is correct
10 Correct 22 ms 34380 KB Output is correct
11 Correct 22 ms 34380 KB Output is correct
12 Correct 24 ms 34372 KB Output is correct
13 Correct 23 ms 34428 KB Output is correct
14 Correct 23 ms 35148 KB Output is correct
15 Correct 25 ms 34544 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26700 KB Output is correct
2 Correct 56 ms 42692 KB Output is correct
3 Correct 1236 ms 219496 KB Output is correct
4 Correct 284 ms 181252 KB Output is correct
5 Correct 1165 ms 217712 KB Output is correct
6 Correct 268 ms 197816 KB Output is correct
7 Correct 276 ms 201732 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26700 KB Output is correct
2 Correct 56 ms 42692 KB Output is correct
3 Correct 1236 ms 219496 KB Output is correct
4 Correct 284 ms 181252 KB Output is correct
5 Correct 1165 ms 217712 KB Output is correct
6 Correct 268 ms 197816 KB Output is correct
7 Correct 276 ms 201732 KB Output is correct
8 Correct 295 ms 183664 KB Output is correct
9 Correct 244 ms 183396 KB Output is correct
10 Correct 295 ms 183644 KB Output is correct
11 Correct 295 ms 180260 KB Output is correct
12 Correct 246 ms 179940 KB Output is correct
13 Correct 277 ms 180308 KB Output is correct
14 Correct 2676 ms 231728 KB Output is correct
15 Correct 269 ms 180740 KB Output is correct
16 Correct 286 ms 195696 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26700 KB Output is correct
2 Correct 16 ms 31180 KB Output is correct
3 Correct 17 ms 31180 KB Output is correct
4 Correct 16 ms 31180 KB Output is correct
5 Correct 17 ms 31216 KB Output is correct
6 Correct 16 ms 31564 KB Output is correct
7 Correct 17 ms 31156 KB Output is correct
8 Correct 17 ms 31684 KB Output is correct
9 Correct 18 ms 31384 KB Output is correct
10 Correct 22 ms 34380 KB Output is correct
11 Correct 22 ms 34380 KB Output is correct
12 Correct 24 ms 34372 KB Output is correct
13 Correct 23 ms 34428 KB Output is correct
14 Correct 23 ms 35148 KB Output is correct
15 Correct 25 ms 34544 KB Output is correct
16 Correct 13 ms 26700 KB Output is correct
17 Correct 56 ms 42692 KB Output is correct
18 Correct 1236 ms 219496 KB Output is correct
19 Correct 284 ms 181252 KB Output is correct
20 Correct 1165 ms 217712 KB Output is correct
21 Correct 268 ms 197816 KB Output is correct
22 Correct 276 ms 201732 KB Output is correct
23 Correct 295 ms 183664 KB Output is correct
24 Correct 244 ms 183396 KB Output is correct
25 Correct 295 ms 183644 KB Output is correct
26 Correct 295 ms 180260 KB Output is correct
27 Correct 246 ms 179940 KB Output is correct
28 Correct 277 ms 180308 KB Output is correct
29 Correct 2676 ms 231728 KB Output is correct
30 Correct 269 ms 180740 KB Output is correct
31 Correct 286 ms 195696 KB Output is correct
32 Runtime error 2292 ms 786436 KB Execution killed with signal 9
33 Halted 0 ms 0 KB -