제출 #604080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
604080		AlperenT	모임들 (IOI18_meetings)	C++17	36 / 100	140 ms	12368 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
 
using namespace std;
 
const long long N = 1e5 + 5, INF = (long long)2e18 + 5;
 
long long n, q;
 
vector<long long> h, predp, sufdp, prenext, sufnext, ans; 

struct Node{
    int ans, pre, suf, len;
};

struct SegTree{
    Node tree[N * 4];

    Node merge(Node a, Node b){
        Node c;

        c.pre = a.pre;
        if(a.pre == a.len) c.pre = a.len + b.pre;

        c.suf = b.suf;
        if(b.suf == b.len) c.suf = a.suf + b.len;

        c.ans = max({a.ans, b.ans, c.pre, c.suf, a.suf + b.pre});
        c.len = a.len + b.len;

        // cout << a.ans << " " << a.pre << " " << a.suf << " " << a.len << "\n";
        // cout << b.ans << " " << b.pre << " " << b.suf << " " << b.len << "\n";
        // cout << c.ans << " " << c.pre << " " << c.suf << " " << c.len << "\n\n\n";

        return c;
    }

    void build(int v = 1, int l = 1, int r = n){
        if(l == r) tree[v] = {h[l] == 1, h[l] == 1, h[l] == 1, 1};
        else{
            int m = l + (r - l) / 2;

            build(v * 2, l, m);
            build(v * 2 + 1, m + 1, r);

            tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
        }
    }

    Node query(int l, int r, int v = 1, int tl = 1, int tr = n){
        if(l > r) return {0, 0, 0, 0};
        else if(l == tl && r == tr) return tree[v];
        else{
            int tm = tl + (tr - tl) / 2;

            return merge(query(l, min(tm, r), v * 2, tl, tm), query(max(tm + 1, l), r, v * 2 + 1, tm + 1, tr));
        }
    }
};

SegTree sgt;
 
vector<long long> minimum_costs(vector<int> H, vector<int> l, vector<int> r){
    n = H.size(), q = l.size();
 
    h = {0};
    for(auto x : H) h.push_back(x);
 
    predp.assign(n + 5, 0), sufdp.assign(n + 5, 0), prenext.assign(n + 5, 0), sufnext.assign(n + 5, 0), ans.assign(q, INF);
 
    for(auto &x : l) x++;
    for(auto &x : r) x++;
 
    stack<pair<long long, long long>> stk;
 
    stk.push({INF, -INF});
 
    for(int i = 1; i <= n; i++){
        while(stk.top().first <= h[i]) stk.pop();
 
        prenext[i] = stk.top().second;
 
        stk.push({h[i], i});
    }
 
    stk = {};
 
    stk.push({INF, INF});
 
    for(int i = n; i >= 1; i--){
        while(stk.top().first <= h[i]) stk.pop();
 
        sufnext[i] = stk.top().second;
 
        stk.push({h[i], i});
    }
 
    if(n <= 5000 && q <= 5000){  // Subtask 1 & 2
        for(int qq = 0; qq < q; qq++){
            predp[l[qq] - 1] = sufdp[r[qq] + 1] = 0; 
 
            predp[l[qq]] = h[l[qq]];
 
            for(int i = l[qq] + 1; i <= r[qq]; i++){
                if(h[i] <= h[i - 1]) predp[i] = predp[i - 1] + h[i];
                else{
                    int prv = max(prenext[i], (long long)l[qq] - 1);
 
                    predp[i] = predp[prv] + 1ll * (i - prv) * h[i];
                }
            }
 
            sufdp[r[qq]] = h[r[qq]];
 
            for(int i = r[qq] - 1; i >= l[qq]; i--){
                if(h[i] <= h[i + 1]) sufdp[i] = sufdp[i + 1] + h[i];
                else{
                    int prv = min(sufnext[i], (long long)r[qq] + 1);
 
                    sufdp[i] = sufdp[prv] + 1ll * (prv - i) * h[i];
                }
            }
 
            for(int i = l[qq]; i <= r[qq]; i++) ans[qq] = min(ans[qq], predp[i] + sufdp[i] - h[i]);
        }
    }
    else{  // Subtask 3
        sgt.build();

        for(int qq = 0; qq < q; qq++){
            ans[qq] = (r[qq] - l[qq] + 1) * 2 - sgt.query(l[qq], r[qq]).ans;
        }
    }
 
    return ans;
}

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