oj.uz

답안 #702518

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
702518 2023-02-24T09:12:08 Z qwerasdfzxcl 모임들 (IOI18_meetings) C++17
100 / 100
 1833 ms 315756 KB 
#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

constexpr int MAXN = 750750;
constexpr ll INF = 4e18;

int n, q;
int a[MAXN], L[MAXN], R[MAXN], C[MAXN];
vector<int> Q[MAXN];
ll ans[MAXN];

struct Seg{
    pair<int, int> tree[MAXN*2];
    int sz;
    bool inv;
    void init(int n, int a[], bool INV){
        inv = INV;
        sz = n;
        for (int i=sz;i<sz*2;i++) tree[i] = {a[i-sz], inv?(sz-i):(i-sz)};
        for (int i=sz-1;i;i--) tree[i] = max(tree[i<<1], tree[i<<1|1]);
    }
    int query(int l, int r){
        ++r;
        pair<int, int> ret = {-1, 0};
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1) ret = max(ret, tree[l++]);
            if (r&1) ret = max(ret, tree[--r]);
        }

        assert(ret.second);
        return inv?-ret.second:ret.second;
    }
}tree, tree2;

struct Line{
    ll a, b;
    Line(){}
    Line(ll _a, ll _b): a(_a), b(_b) {}

    ll operator()(ll x){return a*x + b;}
};

ll cross(const Line &f, const Line &g){
    assert(f.a > g.a);
    ll ret = (g.b - f.b) / (f.a - g.a) + 1;
    assert(ret <= n+1);
    return ret;
}

template<typename T>
struct Deque{
    vector<T> a;
    int s, e, sz;

    Deque(){s = e = sz = 0;}

    void resize(){
        if (a.empty()) a.resize(2);
        else{
            vector<T> b(a.size()*2);
            int j = 0;
            for (int i=s;i!=e;i++,j++){
                if (i==(int)a.size()) i = 0;
                if (i==e) break;
                b[j] = a[i];
            }

            swap(a, b);
            s = 0;
            e = j;
        }
    }

    void push_front(T x){
        if (sz>=(int)a.size()-1) resize();
        --s;
        if (s<0) s = (int)a.size()-1;
        a[s] = x;

        ++sz;
    }

    void push_back(T x){
        if (sz>=(int)a.size()-1) resize();
        a[e] = x;
        e++;
        if (e==(int)a.size()) e = 0;

        ++sz;
    }

    void pop_front(){
        s++;
        if (s==(int)a.size()) s = 0;

        --sz;
    }

    T front(){return a[s];}
    void frontd(){a[s]--;}

    T back(){
        if (!e) return a.back();
        return a[e-1];
    }

    T operator [](int x){
        if (s+x<(int)a.size()) return a[s+x];
        return a[s+x-(int)a.size()];
    }

    int size(){return sz;}

    bool empty(){return sz == 0;}

    void clear(){a.clear(); s = e = sz = 0;}
};

int _search(Deque<int> &dq, int target){
    int l = 0, r = (int)dq.size()-1, ret = dq.size();

    while(l<=r){
        int m = (l+r)>>1;
        if (target < dq[m]) r = m-1, ret = m;
        else l = m+1;
    }

    return ret;
}

struct DS{
    Deque<Line> L;
    Deque<int> p;
    ll ofs;

    void clear(){L.clear(); p.clear(); ofs = 0;}

    void init(int x, int y){
        assert(L.empty() && p.empty() && ofs==0);
        L.push_back(Line(0, y));
        p.push_back(x);
        p.push_back(x+1);
    }

    void push_front(ll a, ll b, int x){
        L.push_front(Line(a, b-ofs));
        p.push_front(x);
    }

    void push_back(ll a, ll b, int x){
        L.push_back(Line(a, b-ofs));
        p.push_back(x);
    }

    void add(ll x){ofs += x;}

    void insert(ll a, ll b){
        int s = p.front(); p.pop_front();
        int e = p.back();
        int prv = s;
        Line f(a, b-ofs);

        while(!L.empty()){
            if (f(p.front()-1) > L.front()(p.front()-1)){
                p.push_front(max((ll)prv, cross(f, L.front())));
                p.push_front(s);

                L.push_front(f);

                return;
            }

            prv = p.front();
            L.pop_front(); p.pop_front();
        }

        assert(L.empty() && p.empty());
        L.push_front(f);
        p.push_front(e);
        p.push_front(s);
    }

    ll back(){return L.back()(p.back()-1) + ofs;}
    int size(){return L.size();}

    ll operator()(int x){
        assert(p.front()<=x && x<p.back());
        int idx = _search(p, x) - 1;
        return L[idx](x) + ofs;
    }
}D[MAXN];

void merge(int x, int y){
    assert(D[x].p.back() + 1 == D[y].p.front());
    if (D[x].size() >= D[y].size()){
        int sz = D[y].size();
        for (int i=0;i<sz;i++){
            D[x].push_back(D[y].L[i].a, D[y].L[i].b + D[y].ofs, D[y].p[i+1]);
        }
    }
    else{
        swap(D[x], D[y]);
        D[x].p.frontd();
        int sz = D[y].size();
        for (int i=sz-1;i>=0;i--){
            D[x].push_front(D[y].L[i].a, D[y].L[i].b + D[y].ofs, D[y].p[i]);
        }
    }
}

void dnc(int l, int r){
    if (l>r) return;

    int m = tree.query(l, r);
    //printf("dnc: %d %d (mid = %d)\n", l, r, m);
    dnc(l, m-1); dnc(m+1, r);

    for (auto &i:Q[m]){
        assert(L[i] <= m);

        if (m < R[i]) ans[i] = min(ans[i], D[m+1](R[i]) + (ll)a[m] * (m-L[i]+1));
        else if (m == R[i]) ans[i] = min(ans[i], (ll)a[m] * (m-L[i]+1));
        else assert(0);
    }

    if (l==r){
        D[l].init(l, a[l]);
    }
    else if (m==r){
        D[l].push_back(0, D[l].back() + a[m], m+1);
    }
    else if (l==m){
        D[m+1].add((ll)a[m] * (m-l+1));
        D[m+1].insert(a[m], - (ll)a[m]*(m-1));
        D[m+1].p.frontd();

        assert(D[m+1].p.front()==m);
        swap(D[m], D[m+1]);
    }
    else{
        ll t = D[l].back();

        D[m+1].add((ll)a[m] * (m-l+1));
        D[m+1].insert(a[m], t - (ll)a[m]*(m-1));
        merge(l, m+1);
    }

    /*printf("\nDS %d %d (mid = %d)\n", l, r, m);
    for (int i=0;i<D[l].L.size();i++) {auto [a, b] = D[l].L[i]; printf(" (%lld, %lld)", a, b+D[l].ofs);}
    printf("\n");
    for (int i=0;i<D[l].p.size();i++) printf(" %d", D[l].p[i]);
    printf("\n");

    printf("end: %d %d\n", l, r);*/
}

int cnt;
void dnc0(int l, int r){
    if (l>r) return;
    //printf("dnc0: %d %d\n", l, r);

    int m = tree.query(l, r);
    C[m] = cnt--;
    dnc0(l, m-1); dnc0(m+1, r);
}

void solve(vector<int> H, vector<int> _L, vector<int> _R, bool INV){
    /*printf("-------------------------------\n");
    for (auto &x:H) printf(" %d", x);
    printf("\n");*/

    for (int i=1;i<=n;i++){
        a[i] = H[i-1];
        Q[i].clear();
        D[i].clear();
    }

    for (int i=1;i<=q;i++){
        L[i] = _L[i-1] + 1;
        R[i] = _R[i-1] + 1;
    }

    tree.init(n+1, a, INV);
    cnt = n;
    dnc0(1, n);
    tree2.init(n+1, C, INV);

    for (int i=1;i<=q;i++){
        Q[tree2.query(L[i], R[i])].push_back(i);
    }

    dnc(1, n);
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    n = H.size();
    q = L.size();
    fill(ans+1, ans+q+1, INF);

    solve(H, L, R, 0);

    reverse(H.begin(), H.end());
    for (auto &x:L) x = n-1-x;
    for (auto &x:R) x = n-1-x;

    solve(H, R, L, 1);

    vector<ll> rans;
    for (int i=1;i<=q;i++) rans.push_back(ans[i]);
    return rans;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 106064 KB Output is correct
2 Correct 50 ms 106336 KB Output is correct
3 Correct 50 ms 106444 KB Output is correct
4 Correct 50 ms 106352 KB Output is correct
5 Correct 50 ms 106436 KB Output is correct
6 Correct 49 ms 106620 KB Output is correct
7 Correct 49 ms 106368 KB Output is correct
8 Correct 48 ms 106412 KB Output is correct
9 Correct 54 ms 106268 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 106064 KB Output is correct
2 Correct 50 ms 106336 KB Output is correct
3 Correct 50 ms 106444 KB Output is correct
4 Correct 50 ms 106352 KB Output is correct
5 Correct 50 ms 106436 KB Output is correct
6 Correct 49 ms 106620 KB Output is correct
7 Correct 49 ms 106368 KB Output is correct
8 Correct 48 ms 106412 KB Output is correct
9 Correct 54 ms 106268 KB Output is correct
10 Correct 57 ms 107160 KB Output is correct
11 Correct 52 ms 107068 KB Output is correct
12 Correct 60 ms 107100 KB Output is correct
13 Correct 52 ms 107084 KB Output is correct
14 Correct 54 ms 107468 KB Output is correct
15 Correct 61 ms 107116 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 105988 KB Output is correct
2 Correct 79 ms 110132 KB Output is correct
3 Correct 183 ms 125508 KB Output is correct
4 Correct 152 ms 116700 KB Output is correct
5 Correct 163 ms 126560 KB Output is correct
6 Correct 170 ms 124316 KB Output is correct
7 Correct 174 ms 126084 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 105988 KB Output is correct
2 Correct 79 ms 110132 KB Output is correct
3 Correct 183 ms 125508 KB Output is correct
4 Correct 152 ms 116700 KB Output is correct
5 Correct 163 ms 126560 KB Output is correct
6 Correct 170 ms 124316 KB Output is correct
7 Correct 174 ms 126084 KB Output is correct
8 Correct 182 ms 122868 KB Output is correct
9 Correct 165 ms 122884 KB Output is correct
10 Correct 168 ms 123188 KB Output is correct
11 Correct 179 ms 122952 KB Output is correct
12 Correct 166 ms 122688 KB Output is correct
13 Correct 159 ms 123016 KB Output is correct
14 Correct 179 ms 130492 KB Output is correct
15 Correct 155 ms 124632 KB Output is correct
16 Correct 174 ms 124364 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 106064 KB Output is correct
2 Correct 50 ms 106336 KB Output is correct
3 Correct 50 ms 106444 KB Output is correct
4 Correct 50 ms 106352 KB Output is correct
5 Correct 50 ms 106436 KB Output is correct
6 Correct 49 ms 106620 KB Output is correct
7 Correct 49 ms 106368 KB Output is correct
8 Correct 48 ms 106412 KB Output is correct
9 Correct 54 ms 106268 KB Output is correct
10 Correct 57 ms 107160 KB Output is correct
11 Correct 52 ms 107068 KB Output is correct
12 Correct 60 ms 107100 KB Output is correct
13 Correct 52 ms 107084 KB Output is correct
14 Correct 54 ms 107468 KB Output is correct
15 Correct 61 ms 107116 KB Output is correct
16 Correct 48 ms 105988 KB Output is correct
17 Correct 79 ms 110132 KB Output is correct
18 Correct 183 ms 125508 KB Output is correct
19 Correct 152 ms 116700 KB Output is correct
20 Correct 163 ms 126560 KB Output is correct
21 Correct 170 ms 124316 KB Output is correct
22 Correct 174 ms 126084 KB Output is correct
23 Correct 182 ms 122868 KB Output is correct
24 Correct 165 ms 122884 KB Output is correct
25 Correct 168 ms 123188 KB Output is correct
26 Correct 179 ms 122952 KB Output is correct
27 Correct 166 ms 122688 KB Output is correct
28 Correct 159 ms 123016 KB Output is correct
29 Correct 179 ms 130492 KB Output is correct
30 Correct 155 ms 124632 KB Output is correct
31 Correct 174 ms 124364 KB Output is correct
32 Correct 1148 ms 232168 KB Output is correct
33 Correct 911 ms 250224 KB Output is correct
34 Correct 1058 ms 251848 KB Output is correct
35 Correct 1202 ms 253092 KB Output is correct
36 Correct 950 ms 250896 KB Output is correct
37 Correct 1084 ms 252320 KB Output is correct
38 Correct 1520 ms 304560 KB Output is correct
39 Correct 1524 ms 305428 KB Output is correct
40 Correct 1198 ms 243076 KB Output is correct
41 Correct 1628 ms 314600 KB Output is correct
42 Correct 1803 ms 315756 KB Output is correct
43 Correct 1833 ms 315668 KB Output is correct
44 Correct 1745 ms 304364 KB Output is correct