Submission #82831

#	Time	Username	Problem	Language	Result	Execution time	Memory
82831		Benq	Meetings (IOI18_meetings)	C++14	100 / 100	2763 ms	324788 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[SZ][21];
    
    int bet(int a, int b) {
      return hei[a] > hei[b] ? a : b;
    }
 
    RMQ() {
        F0R(i,N) mx[i][0] = i;
        FOR(j,1,21) F0R(i,N-(1<<j)+1) 
          mx[i][j] = bet(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
    }
    
    int query(int L, int R) {
        int x = 31-__builtin_clz(R-L+1);
        return bet(mx[L][x],mx[R-(1<<x)+1][x]);
    }
};
 
RMQ RM;
 
ll ans[SZ];
vector<array<int,3>> tmp[SZ];
 
struct line {
    int s,e;
    ll m,b;
    line() {}
    line(int _s, int _e, ll _m, ll _b) { s = _s, e = _e, m = _m, b = _b; }
    ll eval(int x) { return m*x+b; }
};

line d[SZ];

struct lineContain {
    int s,e;
    ll lazy = 0;
    lineContain(int _s, int _e) {
        s = _s, e = _e;
    }
    ll evalBack() {
        if (!size()) return 0;
        return d[e].eval(d[e].e)+lazy;
    }
    line front() {
        line l = d[s]; l.b += lazy;
        return l;
    }
    line back() {
        line l = d[e]; l.b += lazy;
        return l;
    }
    line pop_front() {
        line l = front(); s ++; 
        return l;
    }
    line pop_back() {
        line l = back(); e --;
        return l;
    }
    ll get(int m) {
        if (size() == 0 || m < d[s].s) return 0;
        int lo = s, hi = e;
        while (lo < hi) {
            int mid = (lo+hi+1)/2;
            if (d[mid].s <= m) lo = mid;
            else hi = mid-1;
        }
        return d[lo].eval(m)+lazy;
    }
    ll evalFront(ll x) {
        return d[s].eval(x)+lazy;
    }
    void push_back(line l) {
        l.b -= lazy;
        d[++e] = l;
    }
    void push_front(line l) {
        l.b -= lazy;
        d[--s] = l;
    }
    int size() { return e-s+1; }
};

lineContain divi(int lo, int hi) {
    if (lo > hi) return lineContain(lo,lo-1);
    
    ll x = RM.query(lo,hi); 
    auto l = divi(lo,x-1); auto r = divi(x+1,hi); 
    for (auto y: tmp[x]) checkmn(ans[y[2]],(ll)(x-y[0]+1)*hei[x].f+r.get(y[1]));
    
    r.lazy += (x-lo+1)*hei[x].f;
    int right = x;
    ll lst = l.evalBack();
    
    while (sz(r)) {
        ll e = r.front().e;
        ll a = lst+(e-x+1)*hei[x].f;
        ll b = r.evalFront(e);
        if (a <= b) {
            right = e; r.pop_front();
            continue;
        } else {
            ll s = r.front().s;
            while (s < e) {
                ll m = (s+e)/2;
                a = lst+(m-x+1)*hei[x].f;
                b = r.evalFront(m);
                if (a <= b) s = m+1;
                else e = m;
            }
            right = s-1;
            auto a = r.pop_front(); a.s = s; r.push_front(a);
            break;
            // binary search
        }
    }
    
    
    l.pb(line(x,right,hei[x].f,lst-hei[x].f*(x-1)));
    if (sz(l) > sz(r)) {
        while (sz(r)) l.pb(r.pop_front());
        return l;
    } else {
        while (sz(l)) r.push_front(l.pop_back());
        return r;
    }
}
 
void solve(vi L, vi R) {
    RM = RMQ(); 
    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});
    divi(0,N-1);
}
 
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]);
    }
    
    // cout << "\n";
    solve(L,R);
    vl ret; F0R(i,sz(L)) ret.pb(ans[i]);
    return ret;
}
 /*
int main() {
    int N,Q; cin >> N >> Q;// N = Q = 750000;
    vi H(N), L(Q), R(Q);
    F0R(i,N) {
        // H[i] = rand() % 1000000000;
        cin >> H[i];
    }
    F0R(i,Q) {
        L[i] = rand() % N, R[i] = rand() % N;
        if (L[i] > R[i]) swap(L[i],R[i]);
        cin >> L[i] >> R[i];
    }
    vl C = minimum_costs(H, L, R);
    for (auto a: C) cout << a << " ";
}*/

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