Submission #492083

#	Time	Username	Problem	Language	Result	Execution time	Memory
492083		blue	모임들 (IOI18_meetings)	C++17	0 / 100	90 ms	45000 KiB

meetings

#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;

void pc(int c)
{
    // cerr << "case: " << c << '\n';
    ;
}

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));
    }
};

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;
}


struct seg
{
    int x1;
    ll y1;

    int x2;
    ll y2;

    ll get_slope()
    {
        // cerr << "querying slope: ";
        if(x2 == x1) return 0;
        else return (y2-y1)/(x2-x1);
    }
};

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

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

    void push_back(func K)
    {
        for(seg k: K.d)
        {
            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(seg k: K.d)
        {
            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)
    {
        // cerr << "call front AP " << ' ' << a << ' ' << sl << '\n';
        int xf = d.front().x1;
        // cerr << "xf = " << xf << '\n';
        int xb = -1;
        // cerr << "Q " << sz(d) << '\n';
        while(!d.empty())
        {
            ll dy2 = d.front().y2 + lp;
            int dx2 = d.front().x2;

            ll new_y2 = a + sl*(dx2 - xf);
            if(new_y2 > dy2) break;
            else
            {
                xb = max(xb, d.front().x2);
                d.pop_front();
            }
        }
        // cerr << ""
        // cerr << "W " << sz(d) << '\n';

        // cerr << xf << ' ' << xb << '\n';
        // cerr << "ap = " << a << ' ' << sl << '\n';


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

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

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

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

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

                d.push_front({xf, a - lp, lo-1, a+sl*(lo-1-xf) - lp});
            }
        }
        else if(xf <= xb)
        {
            // cerr << "case Y\n";
            d.push_front({xf, a - lp, xb, a+sl*(xb-xf) - lp});
            // cerr << xf << ' ' << a << ' ' << xb << ' ' << a+sl*(xb-xf) << '\n';
        }
        // cerr << "E " << sz(d) << '\n';
    }
};



vector<func*> F(mx);


void dfs(int u)
{
    // cerr << "\n-----------------\n";
    // cerr << "dfs entry " << u << '\n';
    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]];
    }
    // cerr << "\n\n";
    // cerr << "returning to node " << u << '\n';
    // cerr << "hello\n";

    for(int q: peak_queries[u])
    {
        // cerr << "AAAAA\n";
        // cerr << u << " : answering query " << q << '\n';
        int lo = 0;
        int hi = sz(F[rc[u]]->d) - 1;
        while(lo != hi)
        {
            // cerr << "binary search: lo = " << lo << ", hi = " << hi << '\n';
            int mid = (lo+hi)/2;
            // cerr << "mid = " << mid << ' ' << F[rc[u]]->d[mid].x2 << '\n';
            if(F[rc[u]]->d[mid].x2 < R[q])
                lo = mid+1;
            else
                hi = mid;
        }

        auto fr = F[rc[u]];

        // cerr << "lo = " << lo << '\n';

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

        // for(auto g1: fr->d) cerr << "seg = " << g1.x1 << ' ' << g1.y1 + fr->lp << ' ' << g1.x2 << ' ' << g1.y2 + fr->lp << '\n';

        // cerr << "right endpoints = " << u+1 << ' ' << R[q] << " : answer = " << right_ans << '\n';

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

        // cerr << "????? " << H[u] << ' ' << L[q] << ' ' << u << ' ' << right_ans << '\n';
    }

    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));
                // cerr << "rc u = " << rc[u] << " inc \n";
                // for(auto fv: F[rc[u]]->d) cerr << fv.x1 << ' ' << F[rc[u]]->lp + fv.y1 << ' ' << fv.x2 << ' ' << F[rc[u]]->lp + fv.y2 << " | ";
                // cerr << '\n';
    }


    ll dp_u;
    if(lc[u] == -1)
    {
        dp_u = H[u];
        // cerr << "case u\n";
    }
    else
    {
        // cerr << "case v\n";
        // cerr << "lc u = " << lc[u] << " inc \n";
        // for(auto fv: F[lc[u]]->d) cerr << fv.x1 << ' ' << F[lc[u]]->lp + fv.y1 << ' ' << fv.x2 << ' ' << F[rc[u]]->lp + fv.y2 << " | ";
        // cerr << '\n';
        // cerr << F[lc[u]]->d.back().y2 << '\n';
        dp_u = H[u] + F[lc[u]]->d.back().y2 + F[lc[u]]->lp;
    }

    // cerr << "left dp = " << F[lc[u]]->d.back().y2 << '\n';

    func ths;
    ths.d.push_back(seg{u, dp_u, u, dp_u});

    if(rc[u] != -1)
    {
        // for(auto fv: F[rc[u]]->d) cerr << fv.x1 << ' ' << F[rc[u]]->lp + fv.y1 << ' ' << fv.x2 << ' ' << F[rc[u]]->lp + fv.y2 << " | ";
        // cerr << '\n';
        F[rc[u]]->front_AP(dp_u + H[u], H[u]);
        // cerr << "rc u = " << rc[u] << " AP \n";
        // for(auto fv: F[rc[u]]->d) cerr << fv.x1 << ' ' << F[rc[u]]->lp + fv.y1 << ' ' << fv.x2 << ' ' << F[rc[u]]->lp + fv.y2 << " | ";
        // cerr << '\n';

    }

    if(lc[u] == -1 && rc[u] == -1)
    {
        pc(0);
        F[u]->push_back(ths);
    }
    else if(lc[u] == -1)
    {
        pc(1);
        // cerr << rc[u] << " -> " << sz(F[rc[u]]->d) << '\n';
        F[u] = F[rc[u]]; //BUG IS HERE!!!!!
        // cerr << "YT " << sz(F[u]->d) << '\n';
        F[u]->push_front(ths);
    }
    else if(rc[u] == -1)
    {
        pc(2);
        F[u] = F[lc[u]];
        F[u]->push_back(ths);
    }
    else
    {
        if(subtree[rc[u]] >= subtree[lc[u]])
        {
            pc(3);
            F[u] = F[rc[u]];
            F[u]->push_front(ths);
            F[u]->push_front(*F[lc[u]]);
        }
        else
        {
            pc(4);
            F[u] = F[lc[u]];
            F[u]->push_back(ths);
            F[u]->push_back(*F[rc[u]]);
        }
    }

    // cerr << "func at " << u << " = ";
    // for(auto fv: F[u]->d) cerr << fv.x1 << ' ' << F[u]->lp + fv.y1 << ' ' << fv.x2 << ' ' << F[u]->lp + fv.y2 << " | ";
    // cerr << '\n';
    //
    // cerr << "dfs exit " << u << '\n';
    // cerr << "u size = " << sz(F[u]->d) << '\n';
}










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_;

    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++)
    {
        // cerr << "\n\n\n\n\n";
        // cerr << "\n\n==================================\n\ntype = " << t << "\n";

//PART 3: IDENTIFY PEAK OF EACH QUERY
        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];
                // cerr << "j = " << j << " : " << L[j] << ' ' << R[j] << ", " << M[j] << '\n';
            }
        }

                // cerr << "height array = ";
                // for(int h:H) cerr << h << ' ';
                // cerr << '\n';

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

        // cerr << "HD = ";
        // for(int hd: HD) cerr << hd << ' ';
        // cerr << '\n';

        ST = segtree(0, N-1, HD);
        for(int j = 0; j < Q; j++)
        {
            // cerr << "prev ans = " << ans[j] << '\n';
            // cerr << "L R = " << L[j] << ' ' << R[j] << '\n';
            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));
                // cerr << "! " << H[M[j]] << ' ' << R[j] - L[j] + 1 << '\n';
            }
            else
                peak_queries[M[j]].push_back(j);

            // cerr << "query = " << j << " : " << "M = " << M[j] << '\n';
        }

        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);
        // cerr << "root of tree = " << rt << '\n';

        // cerr << lc[0] << ' ' << rc[0] << ' ' << rt << '\n';

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



        // cerr << "rt = " << rt << '\n';
        // cerr << sz(F[rt]->d) << '\n';
        // for(auto f: F[rt]->d) cerr << f.x1 << ' ' << f.x2 << ' ' << F[rt]->lp + f.y1 << ' ' << F[rt]->lp + f.y2 << '\n';








        // cerr << "new ans = " << ans[0] << '\n';
    }

    return ans;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40