Submission #1022447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022447		hotboy2703	Meetings (IOI18_meetings)	C++17	60 / 100	3994 ms	84920 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define MP make_pair
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
ll n,q;
const ll MAXN = 7.5e5+100;
const ll INF = 1e18;
ll c[MAXN];
ll a[MAXN];
ll INF1 = 1e9+7;
namespace seg{
    ll tree[MAXN*4],lazy[MAXN*4];
    void build(ll id = 1,ll l = 1,ll r = n){
        if (l == r)tree[id] = c[l];
        else{
            ll mid = (l + r) >> 1;
            build(id<<1,l,mid);
            build(id<<1|1,mid+1,r);
            tree[id] = min(tree[id<<1],tree[id<<1|1]);
        }
    }
    void push(ll id,ll val){
        tree[id]+=val;
        lazy[id]+=val;
    }
    void lz(ll id){
        if (lazy[id]){
            push(id<<1,lazy[id]);
            push(id<<1|1,lazy[id]);
            lazy[id] = 0;
        }
    }
    void update(ll id,ll l,ll r,ll l1,ll r1,ll val){
        if (l > r1 || l1 > r || l1 > r1)return;
        if (l1 <= l && r <= r1){
            push(id,val);
            return;
        }
        lz(id);
        ll mid = (l + r) >> 1;
        update(id << 1,l,mid,l1,r1,val);
        update(id<<1|1,mid+1,r,l1,r1,val);
        tree[id] = min(tree[id<<1],tree[id<<1|1]);
    }
    ll get(ll id,ll l,ll r,ll l1,ll r1){
        if (l > r1 || l1 > r)return INF;
        if (l1 <= l && r <= r1)return tree[id];
        ll mid = (l + r) >> 1;
        lz(id);
        return min(get(id<<1,l,mid,l1,r1),get(id<<1|1,mid+1,r,l1,r1));
    }
}
ll solve(ll l,ll r){
    vector <ll> all;
    ll cur = 0;
    all.push_back(l-1);
    swap(INF1,a[l-1]);
    for (ll i = l;i <= r;i ++){
        while (a[all.back()] < a[i]){
            cur -= (all[sz(all) - 1] - all[sz(all) - 2]) * a[all[sz(all) - 1]];
            all.pop_back();
        }
        all.push_back(i);
        cur += (all[sz(all) - 1] - all[sz(all) - 2]) * a[all[sz(all) - 1]];
        c[i] = cur;
    }
    swap(INF1,a[l-1]);

    cur = 0;
    all.clear();
    all.push_back(r+1);
    swap(INF1,a[r+1]);
    for (ll i = r;i >= l;i --){
        while (a[all.back()] < a[i]){
            cur -= (- all[sz(all) - 1] + all[sz(all) - 2]) * a[all[sz(all) - 1]];
            all.pop_back();
        }
        all.push_back(i);
        cur += (- all[sz(all) - 1] +  all[sz(all) - 2]) * a[all[sz(all) - 1]];
        c[i] += cur;
    }
    swap(INF1,a[r+1]);
    ll res = 1e18;
    for (ll i = l;i <= r;i ++){c[i] -= a[i];res = min(res,c[i]);}
    return res;
}
set <int> s[21];
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R){
    n = sz(H);
    q = sz(L);
    ll max_ai = 0;
    for (ll i = 1;i <= n;i ++){
        a[i] = H[i-1];
        max_ai = max(max_ai,a[i]);
    }

    vector <ll> res(q);
    if (max_ai <= 20){
        for (ll j = 1;j <= 20;j ++){
            s[j].insert(0);
            s[j].insert(n+1);
        }
        for (ll i = 1;i <= n;i ++){
            for (ll j = 1;j <= a[i];j ++)s[j].insert(i);
        }
        solve(1,n);
        seg::build();
//        cout<<"OK"<<endl;
    }
    if (max_ai <= 20){
        vector <pair <pll,ll> > all;
        for (ll i = 0;i < q;i ++)all.push_back(MP(MP(L[i]+1,R[i]+1),i));
        sort(all.begin(),all.end());
        for (ll i = 1,ptr = 0;i <= n;i ++){
            if (i >= 2){
                for (ll j = 1;j <= 20;j ++){
                    auto l1 = s[j].lower_bound(i-1);
                    seg::update(1,1,n,*l1,n,-1);
                }
            }
            while (ptr < sz(all) && all[ptr].fi.fi == i){
                ll r = all[ptr].fi.se,l = all[ptr].fi.fi;
                for (ll j = 1;j <= 20;j ++){
                    auto r1 = s[j].upper_bound(r);
                    seg::update(1,1,n,l,r,          -(n-*r1+1));
                    seg::update(1,1,n,l,*prev(r1),  -(*r1-r-1));
                }
                res[all[ptr].se] = seg::get(1,1,n,l,r);
                for (ll j = 1;j <= 20;j ++){
                    auto r1 = s[j].upper_bound(r);
                    seg::update(1,1,n,l,r,          +(n-*r1+1));
                    seg::update(1,1,n,l,*prev(r1),  +(*r1-r-1));
                }
                ptr++;
            }
        }
    }
    else{
        for (ll i = 0;i < q;i ++){
            ll l = L[i] + 1,r = R[i] + 1;
            if (n <= 5000 && q <= 5000){
                res[i] = solve(l,r);
            }
        }
    }
    return res;
}

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