Submission #1025540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025540		Dzadzo	Meetings (IOI18_meetings)	C++17	100 / 100	3190 ms	594624 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
#define ll long long
#define pb push_back
#define S second
#define F first
#define pii pair<ll,ll>
#define vi vector<ll>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vp vector<pii>
#define vvp vector<vp>
#define vb vector<bool>
#define vvb vector<vb>
#define INF 1000000000000000
#define MOD 1000000007
#define MAXN 750000
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
ll n,q;
ll ql[MAXN+1],qr[MAXN+1];
vector<ll> ans(MAXN+1,INF);
vvp a(MAXN+1,vp(20));
vvi Q(MAXN+1);
vp t(4*MAXN+1);
vp lazy(4*MAXN+1);
pii getmax(ll l,ll r) {
    ll bit=31-__builtin_clz(r-l+1);
    return max(a[l][bit], a[r-(1<<bit)+1][bit]);
}
void apply(ll v, ll tl, ll tr, pii x) {
    if(x.F) {
        t[v] = { tl * x.F , tr * x.F};
        lazy[v] ={ x.F , 0};
    }
    t[v].F += x.S;
    t[v].S += x.S;
    lazy[v].S += x.S;
}
void push(ll v,ll tl,ll tr) {
    apply(v*2,tl,(tl+tr)/2,lazy[v]);
    apply(v*2+1,(tl+tr)/2+1,tr,lazy[v]);
    lazy[v]={0,0};
}
void up(ll v,ll tl,ll tr,ll l,ll r,pii x,bool all) {
    if (l>r)return;
    if (tl==l && tr==r) {
        if (all || tr*x.F+x.S < t[v].S) {
            apply(v,tl,tr,x);
            return;
        }
        if (tl*x.F + x.S >= t[v].F)
            return;
    }
    push(v,tl,tr);
    ll tm=(tl+tr)/2;
    up(v*2,tl,tm,l,min(r,tm),x,all);
    up(v*2+1,tm+1,tr,max(l,tm+1),r,x,all);
    t[v]={t[2*v].F,t[2*v+1].S};
}
ll get(ll v,ll tl,ll tr,ll idx) {
    if (tl==tr)return t[v].F;
    push(v,tl,tr);
    ll tm=(tl+tr)/2;
    if (idx<=tm)return get(v*2,tl,tm,idx);
    return get(v*2+1,tm+1,tr,idx);
}
ll solve(ll l,ll r,bool prnt) {
    if (l>r)return -1;
    ll mid=abs(getmax(l,r).S);
    ll lc=solve(l,mid-1,prnt);
    ll rc=solve(mid+1,r,prnt);
    up(1,0,n-1,mid,mid,{1,-mid},1);
    for (ll x:Q[mid]) {
        ans[x]=min(get(1,0,n-1,qr[x])+(mid-ql[x]+1ll)*a[mid][0].F,ans[x]);
    }
    up(1,0,n-1,mid,r,{0,(mid-l+1ll)*a[mid][0].F},1);
    up(1,0,n-1,mid,r,{a[mid][0].F, (~lc?get(1,0,n-1,mid-1):0) - (mid-1ll)*a[mid][0].F },0);
    return mid;
}
vector <ll> minimum_costs(vector <int> H, vector <int> L, vector <int> R) {
    n=H.size();
    q=L.size();
    for (ll i=0;i<n;i++)
        a[i][0]={H[i],i};
    for (ll bit=1;bit<20;bit++)
        for (ll i=0;i<n-(1<<(bit-1));i++)
            a[i][bit]=max(a[i][bit-1],a[i+(1<<(bit-1))][bit-1]);
    for (ll i=0;i<q;i++) {
        ql[i]=L[i];
        qr[i]=R[i];
        Q[getmax(ql[i],qr[i]).S].pb(i);
    }
    solve(0,n-1,0);
    reverse(Q.begin(),Q.begin()+n);
    t.assign(MAXN+1,{0,0});
    lazy.assign(MAXN+1,{0,0});
    a.assign(MAXN+1,vp(20));
    reverse(H.begin(),H.end());
    for (ll i=0;i<n;i++)
        a[i][0]={H[i],-i};
    for (ll bit=1;bit<20;bit++)
        for (ll i=0;i<n-(1<<(bit-1));i++)
            a[i][bit]=max(a[i][bit-1],a[i+(1<<(bit-1))][bit-1]);
    for (ll i=0;i<q;i++) {
        ql[i]=n-1-R[i];
        qr[i]=n-1-L[i];
    }
    solve(0,n-1,1);
    vector <ll> res;
    for (ll i=0;i<q;i++)res.pb(ans[i]);
    return res;
}
// signed main(){
//     ll n,q;
//     cin>>n>>q;
//     vector <int> H,L,R;
//     while(n--) {
//         ll x;
//         cin>>x;
//         H.pb(x);
//     }
//     while (q--) {
//         ll l,r;
//         cin>>l>>r;
//         L.pb(l);
//         R.pb(r);
//     }
//     vector <ll> wtf=minimum_costs(H,L,R);
//     for (ll x:wtf)cout<<x<<" ";
// }

Compilation message (stderr)

meetings.cpp: In function 'long long int solve(long long int, long long int, bool)':
meetings.cpp:73:8: warning: unused variable 'rc' [-Wunused-variable]
   73 |     ll rc=solve(mid+1,r,prnt);
      |        ^~

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