Submission #75280

#	Time	Username	Problem	Language	Result	Execution time	Memory
75280		admin	Meetings (IOI18_meetings)	C++17	100 / 100	5456 ms	291672 KiB

meetings

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>
 
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
 
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 1<<20;
const int SZ = 750001;
 
#include "meetings.h"
 
pl operator*(const pl& l, const ll& r) { return {l.f*r,l.s*r}; }
pl operator+(const pl& l, const pl& r) { return {l.f+r.f,l.s+r.s}; }
pl operator+=(pl& l, const pl& r) { return l = {l.f+r.f,l.s+r.s}; }
 
int N;
vpi hei;
 
void checkmn(ll& x, ll y) { x = min(x,y); }
 
struct RMQ {
    int mx[21][SZ];
    
    int bet(int a, int b) {
      return hei[a] > hei[b] ? a : b;
    }
 
    void clear() {
        F0R(i,N) mx[0][i] = i;
        FOR(j,1,21) F0R(i,N-(1<<j)+1) 
          mx[j][i] = bet(mx[j-1][i],mx[j-1][i+(1<<(j-1))]);
    }
    
    int query(int L, int R) {
        int x = 31-__builtin_clz(R-L+1);
        return bet(mx[x][L],mx[x][R-(1<<x)+1]);
    }
};
 
RMQ RM;
 
struct DSU {
    int par[SZ], left[SZ], right[SZ];
    void clear() {
      F0R(i,SZ) par[i] = left[i] = right[i] = i;
    }
    
    int get(int x) {
      if (par[x] != x) return par[x] = get(par[x]);
      return x;
    }
    
    inline void unite(int a, int b) {
      a = get(a), b = get(b);
      if (right[a]-left[a] < right[b]-left[b]) swap(a,b);
      par[b] = a; 
      left[a] = min(left[a],left[b]); 
      right[a] = max(right[a],right[b]);
    }
};
 
ll ans[SZ];
vector<array<int,3>> tmp[SZ];
 
struct Seg {
    ll val[2*MX];
    pair<int,pl> lazy[2*MX], done = mp(1,mp(0,0));
    
    inline void push(int ind, int L, int R) {
        if (lazy[ind] == done) return;
        val[ind] = val[ind]*lazy[ind].f+lazy[ind].s.f*R+lazy[ind].s.s;
        
        if (L != R) {
            if (lazy[ind].f == 0) lazy[2*ind] = lazy[ind];
            else lazy[2*ind].s += lazy[ind].s;
            
            if (lazy[ind].f == 0) lazy[2*ind+1] = lazy[ind];
            else lazy[2*ind+1].s += lazy[ind].s;
        }
        
        lazy[ind] = done;
    }
 
    inline void pull(int ind) { val[ind] = val[2*ind+1]; }
 
    void upd(int lo, int hi, pair<int,pl> A, int ind = 1, int L = 0, int R = SZ-1) {
        push(ind,L,R);
        if (R < lo || hi < L) return;
        if (lo <= L && R <= hi) {
            lazy[ind] = A;
            push(ind,L,R);
            return;
        }
        int M = (L+R)/2;
        upd(lo,hi,A,2*ind,L,M); upd(lo,hi,A,2*ind+1,M+1,R);
        pull(ind);
    }
 
    ll get(int pos, int ind = 1, int L = 0, int R = SZ-1) {
        push(ind,L,R);
        if (L == R) return val[ind];
        int M = (L+R)/2;
        if (pos <= M) return get(pos,2*ind,L,M);
        return get(pos,2*ind+1,M+1,R);
    }
 
    int getFst(int x, int lo, int hi, ll ori, int ind = 1, int L = 0, int R = SZ-1) {
        push(ind,L,R);
        
        int M = (L+R)/2;
        if (R <= hi) {
            if (R <= x) return -1;
            ll val1 = (ll)hei[x].f*(R-x+1)+ori;
            ll val2 = (ll)hei[x].f*(x-lo+1)+val[ind]; // first one such that 2nd is less
            if (val1 < val2) return -1;
        }
        if (L == R) return L;
        
        int z = getFst(x,lo,hi,ori,2*ind,L,M); if (z != -1) return z;
        return getFst(x,lo,hi,ori,2*ind+1,M+1,R);
    }
};
 
Seg S;
DSU D;
 
void tri(int x) {
    if (x < N-1 && hei[x] > hei[x+1]) D.unite(x,x+1);
    if (x > 0 && hei[x] > hei[x-1]) D.unite(x-1,x);
    
    int L = D.left[D.get(x)], R = D.right[D.get(x)];
    ll preVal = (L == x ? 0 : S.get(x-1));
    
    
    for (auto y: tmp[x]) checkmn(ans[y[2]],(ll)(x-y[0]+1)*hei[x].f+S.get(y[1]));
    
    int ind = S.getFst(x,L,R,preVal); if (ind == -1) ind = R+1;
    S.upd(x,ind-1,{0,{hei[x].f,preVal-(ll)(x-1)*hei[x].f}}); 
    S.upd(ind,R,{1,{0,(ll)(x-L+1)*hei[x].f}});
}
 
void solve(vi L, vi R) {
    RM.clear();
    D.clear();
    S = Seg();
    vi h; F0R(i,N) h.pb(i);
    sort(all(h),[](int a, int b) { return hei[a] < hei[b]; });
    F0R(i,SZ) tmp[i].clear();
    
    F0R(i,sz(L)) tmp[RM.query(L[i],R[i])].pb({L[i],R[i],i});
    F0R(i,sz(h)) tri(h[i]);
}
 
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    N = sz(H);
    F0R(i,N) hei.pb({H[i],i});
    F0R(i,sz(L)) ans[i] = INF;
 
    solve(L,R);
 
    reverse(all(hei));
    F0R(i,sz(L)) {
        L[i] = sz(H)-1-L[i];
        R[i] = sz(H)-1-R[i];
        swap(L[i],R[i]);
    }
    
    solve(L,R);
    vl ret; F0R(i,sz(L)) ret.pb(ans[i]);
    return ret;
}

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