oj.uz

답안 #492217

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
492217 2021-12-06T01:50:14 Z blue 모임들 (IOI18_meetings) C++17
60 / 100
 2732 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));
    }
};

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[2'000'000];
int x2[2'000'000];
ll y1[2'000'000];
ll y2[2'000'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();
        }
    }
}




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++)
    {

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

        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:171:17: warning: unused variable 'dx1' [-Wunused-variable]
  171 |             int dx1 = x1[d.front()];
      |                 ^~~
meetings.cpp:188:16: warning: unused variable 'dy1' [-Wunused-variable]
  188 |             ll dy1 = y1[d.front()] + lp;
      |                ^~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 26704 KB Output is correct
2 Correct 18 ms 31740 KB Output is correct
3 Correct 19 ms 31744 KB Output is correct
4 Correct 19 ms 31740 KB Output is correct
5 Correct 20 ms 31748 KB Output is correct
6 Correct 19 ms 32176 KB Output is correct
7 Correct 18 ms 31700 KB Output is correct
8 Correct 18 ms 32312 KB Output is correct
9 Correct 17 ms 31968 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 26704 KB Output is correct
2 Correct 18 ms 31740 KB Output is correct
3 Correct 19 ms 31744 KB Output is correct
4 Correct 19 ms 31740 KB Output is correct
5 Correct 20 ms 31748 KB Output is correct
6 Correct 19 ms 32176 KB Output is correct
7 Correct 18 ms 31700 KB Output is correct
8 Correct 18 ms 32312 KB Output is correct
9 Correct 17 ms 31968 KB Output is correct
10 Correct 23 ms 35532 KB Output is correct
11 Correct 22 ms 35440 KB Output is correct
12 Correct 25 ms 35556 KB Output is correct
13 Correct 22 ms 35524 KB Output is correct
14 Correct 23 ms 36300 KB Output is correct
15 Correct 24 ms 35476 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 26740 KB Output is correct
2 Correct 60 ms 44408 KB Output is correct
3 Correct 1250 ms 238332 KB Output is correct
4 Correct 273 ms 200048 KB Output is correct
5 Correct 1167 ms 236672 KB Output is correct
6 Correct 263 ms 216632 KB Output is correct
7 Correct 286 ms 220712 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 26740 KB Output is correct
2 Correct 60 ms 44408 KB Output is correct
3 Correct 1250 ms 238332 KB Output is correct
4 Correct 273 ms 200048 KB Output is correct
5 Correct 1167 ms 236672 KB Output is correct
6 Correct 263 ms 216632 KB Output is correct
7 Correct 286 ms 220712 KB Output is correct
8 Correct 297 ms 202424 KB Output is correct
9 Correct 247 ms 202152 KB Output is correct
10 Correct 285 ms 202424 KB Output is correct
11 Correct 281 ms 198932 KB Output is correct
12 Correct 240 ms 198860 KB Output is correct
13 Correct 273 ms 199096 KB Output is correct
14 Correct 2732 ms 250260 KB Output is correct
15 Correct 257 ms 201552 KB Output is correct
16 Correct 279 ms 216380 KB Output is correct

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 26704 KB Output is correct
2 Correct 18 ms 31740 KB Output is correct
3 Correct 19 ms 31744 KB Output is correct
4 Correct 19 ms 31740 KB Output is correct
5 Correct 20 ms 31748 KB Output is correct
6 Correct 19 ms 32176 KB Output is correct
7 Correct 18 ms 31700 KB Output is correct
8 Correct 18 ms 32312 KB Output is correct
9 Correct 17 ms 31968 KB Output is correct
10 Correct 23 ms 35532 KB Output is correct
11 Correct 22 ms 35440 KB Output is correct
12 Correct 25 ms 35556 KB Output is correct
13 Correct 22 ms 35524 KB Output is correct
14 Correct 23 ms 36300 KB Output is correct
15 Correct 24 ms 35476 KB Output is correct
16 Correct 12 ms 26740 KB Output is correct
17 Correct 60 ms 44408 KB Output is correct
18 Correct 1250 ms 238332 KB Output is correct
19 Correct 273 ms 200048 KB Output is correct
20 Correct 1167 ms 236672 KB Output is correct
21 Correct 263 ms 216632 KB Output is correct
22 Correct 286 ms 220712 KB Output is correct
23 Correct 297 ms 202424 KB Output is correct
24 Correct 247 ms 202152 KB Output is correct
25 Correct 285 ms 202424 KB Output is correct
26 Correct 281 ms 198932 KB Output is correct
27 Correct 240 ms 198860 KB Output is correct
28 Correct 273 ms 199096 KB Output is correct
29 Correct 2732 ms 250260 KB Output is correct
30 Correct 257 ms 201552 KB Output is correct
31 Correct 279 ms 216380 KB Output is correct
32 Runtime error 2157 ms 786436 KB Execution killed with signal 9
33 Halted 0 ms 0 KB -