Submission #1025521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025521		Dzadzo	Meetings (IOI18_meetings)	C++17	0 / 100	187 ms	389708 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<int>
#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")
int n,q;
int 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(int l,int r) {
    int bit=31-__builtin_clz(r-l+1);
    return max(a[l][bit], a[r-(1<<bit)+1][bit]);
}
void apply(int v, int tl, int 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(int v,int tl,int 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(int v,int tl,int tr,int l,int 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);
    int 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(int v,int tl,int tr,int idx) {
    if (tl==tr)return t[v].F;
    push(v,tl,tr);
    int tm=(tl+tr)/2;
    if (idx<=tm)return get(v*2,tl,tm,idx);
    return get(v*2+1,tm+1,tr,idx);
}
int solve(int l,int r) {
    if (l>r)return -1;
    int mid=getmax(l,r).S;
    int lc=solve(l,mid-1);
    int rc=solve(mid+1,r);
    up(1,0,n-1,mid,mid,{1,-mid},1);
    for (int x:Q[mid]) {
        // cout<<x<<" "<<mid<<" "<<get(1,0,n-1,qr[x])<<'\n';
        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);
    // cout<<((~lc?get(1,0,n-1,mid-1):0) - (mid-1ll)*a[mid][0].F)<<"\n";
    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(vi H, vi L, vi R) {
    n=H.size();
    q=L.size();
    for (int i=0;i<n;i++)
        a[i][0]={H[i],i};
    for (int bit=1;bit<20;bit++)
        for (int i=0;i<n-(1<<(bit-1));i++)
            a[i][bit]=max(a[i][bit-1],a[i+(1<<(bit-1))][bit-1]);
    for (int 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);
    Q.assign(MAXN+1,{});
    reverse(H.begin(),H.end());
    for (int i=0;i<n;i++)
        a[i][0]={H[i],i};
    for (int bit=1;bit<20;bit++)
        for (int i=0;i<n-(1<<(bit-1));i++)
            a[i][bit]=max(a[i][bit-1],a[i+(1<<(bit-1))][bit-1]);
    for (int i=0;i<q;i++) {
        ql[i]=n-1-R[i];
        qr[i]=n-1-L[i];
        Q[getmax(ql[i],qr[i]).S].pb(i);
    }
    solve(0,n-1);
    vector <ll> res;
    for (int i=0;i<q;i++)res.pb(ans[i]);
    return res;
}
/*signed main(){
    vector <ll> awdq=minimum_costs({2,4,3,5},{0,1},{2,3});
    for (int x:awdq)cout<<x<<" ";
}*/

Compilation message (stderr)

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

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