제출 #1141773

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141773		Issa	송신탑 (IOI22_towers)	C++17	17 / 100	576 ms	68176 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 1e5 + 100;
const ll INF = (ll)1e18 + 100;
const int inf = 1e9 + 100;
const ll MOD = 998244353;
const int maxl = 20;
const ll P = 31;

int n;
int a[maxn];
int l[maxn];
int r[maxn];
int f[maxn];
int p[maxl][maxn];
int q[maxl][maxn];
int mn[maxl][maxn];
int lg[maxn];

struct asd{
    int mn, mx, ld, rd;
} t[maxn * 4];
asd asdf(asd a, asd b){
    return {min(a.mn, b.mn), max(a.mx, b.mx),
            max({a.ld, b.ld, b.mx - a.mn}),
            max({a.rd, b.rd, a.mx - b.mn})};
} void asdbuild(int v = 1, int tl = 1, int tr = n){
    if(tl == tr){
        t[v] = {a[tl], a[tl], 0, 0};
    } else{
        int mid = (tl + tr) >> 1;
        asdbuild(v<<1, tl, mid);
        asdbuild(v<<1|1, mid+1, tr);
        t[v] = asdf(t[v<<1], t[v<<1|1]);
    }
} asd get(int l, int r, int v = 1, int tl = 1, int tr = n){
    if(tl > r || tr < l) return {inf, 0, 0};
    if(l <= tl && tr <= r) return t[v];
    int mid = (tl + tr) >> 1;
    return asdf(get(l, r, v<<1, tl, mid)
    , get(l, r, v<<1|1, mid+1, tr));
}

int sz;
struct sdf{
    int l, r, cnt;
} d[maxn * 60];
int L[maxn * 60];
int R[maxn * 60];
int root[maxn];
sdf sdff(sdf a, sdf b){
    if(!a.cnt) return b;
    if(!b.cnt) return a;
    return {a.l, b.r, a.cnt + b.cnt};
}
int sdfbuild(int tl = 1, int tr = n){
    int v = ++sz;
    d[v] = {0, 0, 0};
    if(tl < tr){
        int mid = (tl + tr) >> 1;
        L[v] = sdfbuild(tl, mid);
        R[v] = sdfbuild(mid+1, tr);
    } return v;
} int copy(int v){
    int u = ++sz;
    d[u] = d[v];
    L[u] = L[v];
    R[u] = R[v];
    return u;
} int upd(int i, int v, int tl = 1, int tr = n){
    v = copy(v);
    if(tl == tr){
        d[v] = {i, i, 1};
    } else{
        int mid = (tl + tr) >> 1;
        if(i <= mid) L[v] = upd(i, L[v], tl, mid);
        else R[v] = upd(i, R[v], mid+1, tr);
        d[v] = sdff(d[L[v]], d[R[v]]);
    } return v;
} sdf get1(int l, int r, int v, int tl = 1, int tr = n){
    if(tl > r || tr < l) return {0, 0, 0};
    if(l <= tl && tr <= r) return d[v];
    int mid = (tl + tr) >> 1;
    return sdff(get1(l, r, L[v], tl, mid),
    get1(l, r, R[v], mid+1, tr));
}

void init(int N, std::vector<int> H) {
    n = N;
    for(int i = 1; i <= n; i++){
        a[i] = H[i-1]; root[i] = i;
        if(i > 1) lg[i] = lg[i >> 1] + 1;
    } vector<int> v;
    for(int i = 1; i <= n; i++){
        while(v.size() && a[v.back()] > a[i]){
            l[i] = max({l[i], l[v.back()], a[v.back()]});
            v.pop_back();
        } if(v.empty()) l[i] = inf * 2;
        v.push_back(i);
    } v.clear();
    for(int i = n; i > 0; i--){
        while(v.size() && a[v.back()] > a[i]){
            r[i] = max({r[i], r[v.back()], a[v.back()]});
            v.pop_back();
        } if(v.empty()) r[i] = inf * 2;
        v.push_back(i);
        f[i] = min(l[i], r[i]) - a[i];
    } sort(root + 1, root + n + 1, [](int i, int j){
        return f[i] > f[j];
    }); sort(f + 1, f + n + 1, greater<int>());
    root[0] = sdfbuild();
    for(int i = 1; i <= n; i++){
        root[i] = upd(root[i], root[i-1]);
    } asdbuild();
    a[0] = a[n+1] = inf * 2;
    for(int i = 1; i <= n; i++){
        p[0][i] = i-1;
        while(a[p[0][i]] < a[i]){
            p[0][i] = p[0][p[0][i]];
        }
    } for(int i = n; i > 0; i--){
        q[0][i] = i+1;
        while(a[q[0][i]] < a[i]){
            q[0][i] = q[0][q[0][i]];
        } mn[0][i] = i;
    } for(int k = 1; k < maxl; k++){
        for(int i = 1; i <= n; i++){
            p[k][i] = p[k-1][p[k-1][i]];
            q[k][i] = q[k-1][q[k-1][i]];
            if(i + (1<<k) - 1 <= n){
                mn[k][i] = mn[k-1][i+(1<<(k-1))];
                if(a[mn[k][i]] > a[mn[k-1][i]]){
                    mn[k][i] = mn[k-1][i];
                }
            }
        }
    }
}

bool ok(int i, int j, int D){
    if(i > j){
        int r = i;
        for(int k = maxl-1; k >= 0; k--){
            if(a[p[k][r]] - a[i] < D){
                r = p[k][r];
            }
        } r = p[0][r];
        // cout << i << ' ' << j << ' ' << r << ' ' << get(j, r).d << ent;
        return get(j, r).ld >= D;
    } else{
        int l = i;
        for(int k = maxl-1; k >= 0; k--){
            if(a[q[k][l]] - a[i] < D){
                l = q[k][l];
            }
        } l = q[0][l];
        // cout << i << ' ' << j << ' ' << l << ' ' << get(l, j).d << ent;
        return get(l, j).rd >= D;
    }
}

int max_towers(int L, int R, int D) {
    L++; R++;
    int ans = 1;
    for(int l = 2, r = n; l <= r; ){
        int mid = (l + r) >> 1;
        if(f[mid] < D) r = mid - 1;
        else l = mid + 1, ans = mid;
    }
    auto [l, r, cnt] = get1(L, R, root[ans]);
    if(!cnt) return 1;
    // cout << l << ' ' << r << ' ' << cnt << ":\n"; 
    return cnt + ok(l, L, D) + ok(r, R, D);
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 17 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23