제출 #494504

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
494504		blue	모임들 (IOI18_meetings)	C++17	0 / 100	518 ms	786436 KiB

meetings

#include "meetings.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>
using namespace std;
 
using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using pii = pair<int, int>;
#define sze(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 dq
{
    int cap = 1;
    int sz = 0;
    int* v = new int[1];
    // vector<int> v = vi(1);
 
    int st = 0, en = -1;
 
    void push_back(int f)
    {
        // cerr << "pb ";
        if(sz+1 > cap)
        {
            int* v2 = new int[16*cap];
            for(int y = 0; y < sz; y++) v2[y] = v[(st+y)%cap];
            st = 0;
            en = sz-1;
 
            delete[] v;
            v = v2;
            cap *= 16;
        }
 
        en = (en+1)%cap;
        v[en] = f;
        sz++;
        // cerr << "done\n";
    }
 
    void push_front(int f)
    {
        // cerr << "pf ";
        if(sz+1 > cap)
        {
            int* v2 = new int[16*cap];
            for(int y = 0; y < sz; y++) v2[y] = v[(st+y)%cap];
            st = 0;
            en = sz-1;
 
            delete[] v;
            v = v2;
            cap *= 16;
        }
 
        st = (st-1+cap)%cap;
        v[st] = f;
        sz++;
 
        // cerr << "done\n";
    }
 
    void pop_front()
    {
        // cerr << "pop f ";
        if(sz-1 < cap/32 && sz <= cap/16 && cap/16 >= 1)
        {
            int* v2 = new int[cap/16];
            for(int y = 0; y < sz; y++) v2[y] = v[(st+y)%cap];
            st = 0;
            en = sz-1;
 
            delete[] v;
            v = v2;
            cap /= 16;
        }
 
        st = (st+1)%cap;
        sz--;
        // cerr << "done\n";
    }
 
    vector<int> get_deque()
    {
        // cerr << "get deque\n";
        vector<int> res;
        for(int i = (st)%cap; 1; i = (i+1)%cap)
        {
            res.push_back(v[i]);
            if(i == en) break;
        }
        // cerr << "done\n";
        return res;
    }
 
    bool empty()
    {
        // cerr << "empty\n";
        return sz == 0;
    }
 
    int front()
    {
        // cerr << "front\n";
        return v[st];
    }
 
    int back()
    {
        // cerr << "back\n";
        return v[en];
    }
 
    void clear()
    {
        st = 0;
        en = -1;
        sz = 0;
 
        cap = 1;
        // cerr << "clear\n";
        delete[] v;
        v = new int[1];
    }
 
    int size()
    {
        // cerr << "size\n";
        return sz;
    }
 
    int operator [] (int x)
    {
        return v[(st+x)%cap];
    }
};
 
 
 
 
 
 
const int lg = 20;

int lb[750'001];

struct segtree
{
    // int l;
    // int r;
    vector< vector<pii> > v = vector<vector<pii> >(750'000, vector<pii>(20));
    // pii v[2*e20];

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


    segtree()
    {
        ;
    }

    void build_segtree(int L, int R, vi& Z)
    {
        // cerr << "build segtree " << L << ' ' << R << '\n';
        // for(int i = L; i <= R; i++)
        //     v[e20+i] = {Z[i], i};
        // for(int i = e20-1; i >= 1; i--)
        //     v[i] = max(v[2*i], v[2*i+1]);
        // // cerr << "build done\n";

        for(int i = 0; i < N; i++) v[i][0] = {Z[i], i};
        for(int e = 1; e < lg; e++)
        {
            for(int i = 0; i + (1<<e) <= N; i++)
                v[i][e] = max(v[i][e-1], v[i+(1<<(e-1))][e-1]);
        }
    }

    pii rangemax(int L, int R)
    {
        return max(v[L][lb[R-L+1]], v[R-(1<<lb[R-L+1])+1][lb[R-L+1]]);
    }
};
 
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;
}
vector<int> x1, x2;
vector<ll> y1, y2;
 
 
// struct seg
// {
//     int i;
// };
 
int seg_ct = -1;
 
int new_segment(int X1, ll Y1, int X2, ll Y2)
{
    seg_ct++;
    x1.push_back(X1);
    y1.push_back(Y1);
    x2.push_back(X2);
    y2.push_back(Y2);
    // 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;
    dq d;
 
    void inc(ll W)
    {
        lp += W;
    }
 
    void push_back(func& K)
    {
        vi yz = K.d.get_deque();
        for(int k: yz)
        {
            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());
        vi yz = K.d.get_deque();
        reverse(yz.begin(), yz.end());
        for(int k: yz)
        {
            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);
vector<func*> F2(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 = sze(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
  lb[1] = 0;
    for(int i = 2; i <= 750'000; i++)
    {
        lb[i] = lb[i-1];
        if(2*(1<<lb[i]) <= i) lb[i]++;
    }
 
    H = H_;
    L = L_;
    R = R_;
 
    H_.clear();
    L_.clear();
    R_.clear();
 
    N = sze(H);
    Q = sze(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;
    }
    P.clear();
 
 
    // 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);
        if(t==0)ST.build_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();
 
        if(t == 0)
        {
            for(int i = 0; i < N; i++) F[i] = new func;
            F2 = F;
            ST.v.clear();
        }
        else
        {
            F = F2;
            for(int i = 0; i < N; i++)
            {
                F[i]->lp = 0;
                F[i]->d.clear();
            }
        }
        dfs(rt);
 
        le.clear();
        re.clear();
        lc.clear();
        rc.clear();
        // for(int i = 0; i < N; i++)
        // {
        //     F[i]->d.clear();
        //     // cerr << "A " << sze(F[i]->d) << '\n';
        //     // delete F[i];
        // }
    }
 
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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