oj.uz

Submission #75280

# Submission time Handle Problem Language Result Execution time Memory
75280 2018-09-09T05:34:39 Z admin Meetings (IOI18_meetings) C++17
100 / 100
 5456 ms 291672 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 158008 KB Output is correct
2 Correct 226 ms 158364 KB Output is correct
3 Correct 226 ms 158332 KB Output is correct
4 Correct 227 ms 158352 KB Output is correct
5 Correct 222 ms 158328 KB Output is correct
6 Correct 223 ms 158348 KB Output is correct
7 Correct 225 ms 158424 KB Output is correct
8 Correct 220 ms 158424 KB Output is correct
9 Correct 221 ms 158432 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 158008 KB Output is correct
2 Correct 226 ms 158364 KB Output is correct
3 Correct 226 ms 158332 KB Output is correct
4 Correct 227 ms 158352 KB Output is correct
5 Correct 222 ms 158328 KB Output is correct
6 Correct 223 ms 158348 KB Output is correct
7 Correct 225 ms 158424 KB Output is correct
8 Correct 220 ms 158424 KB Output is correct
9 Correct 221 ms 158432 KB Output is correct
10 Correct 238 ms 158988 KB Output is correct
11 Correct 230 ms 158964 KB Output is correct
12 Correct 230 ms 158932 KB Output is correct
13 Correct 231 ms 158944 KB Output is correct
14 Correct 232 ms 158944 KB Output is correct
15 Correct 233 ms 158896 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 158116 KB Output is correct
2 Correct 283 ms 162352 KB Output is correct
3 Correct 691 ms 173880 KB Output is correct
4 Correct 607 ms 173648 KB Output is correct
5 Correct 660 ms 174120 KB Output is correct
6 Correct 668 ms 174076 KB Output is correct
7 Correct 671 ms 173880 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 158116 KB Output is correct
2 Correct 283 ms 162352 KB Output is correct
3 Correct 691 ms 173880 KB Output is correct
4 Correct 607 ms 173648 KB Output is correct
5 Correct 660 ms 174120 KB Output is correct
6 Correct 668 ms 174076 KB Output is correct
7 Correct 671 ms 173880 KB Output is correct
8 Correct 697 ms 173888 KB Output is correct
9 Correct 642 ms 175440 KB Output is correct
10 Correct 702 ms 175804 KB Output is correct
11 Correct 687 ms 175500 KB Output is correct
12 Correct 642 ms 175408 KB Output is correct
13 Correct 667 ms 175784 KB Output is correct
14 Correct 726 ms 176248 KB Output is correct
15 Correct 592 ms 175604 KB Output is correct
16 Correct 665 ms 175800 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 158008 KB Output is correct
2 Correct 226 ms 158364 KB Output is correct
3 Correct 226 ms 158332 KB Output is correct
4 Correct 227 ms 158352 KB Output is correct
5 Correct 222 ms 158328 KB Output is correct
6 Correct 223 ms 158348 KB Output is correct
7 Correct 225 ms 158424 KB Output is correct
8 Correct 220 ms 158424 KB Output is correct
9 Correct 221 ms 158432 KB Output is correct
10 Correct 238 ms 158988 KB Output is correct
11 Correct 230 ms 158964 KB Output is correct
12 Correct 230 ms 158932 KB Output is correct
13 Correct 231 ms 158944 KB Output is correct
14 Correct 232 ms 158944 KB Output is correct
15 Correct 233 ms 158896 KB Output is correct
16 Correct 213 ms 158116 KB Output is correct
17 Correct 283 ms 162352 KB Output is correct
18 Correct 691 ms 173880 KB Output is correct
19 Correct 607 ms 173648 KB Output is correct
20 Correct 660 ms 174120 KB Output is correct
21 Correct 668 ms 174076 KB Output is correct
22 Correct 671 ms 173880 KB Output is correct
23 Correct 697 ms 173888 KB Output is correct
24 Correct 642 ms 175440 KB Output is correct
25 Correct 702 ms 175804 KB Output is correct
26 Correct 687 ms 175500 KB Output is correct
27 Correct 642 ms 175408 KB Output is correct
28 Correct 667 ms 175784 KB Output is correct
29 Correct 726 ms 176248 KB Output is correct
30 Correct 592 ms 175604 KB Output is correct
31 Correct 665 ms 175800 KB Output is correct
32 Correct 5422 ms 286216 KB Output is correct
33 Correct 4744 ms 282716 KB Output is correct
34 Correct 5035 ms 288416 KB Output is correct
35 Correct 5346 ms 286336 KB Output is correct
36 Correct 4917 ms 288488 KB Output is correct
37 Correct 5212 ms 288748 KB Output is correct
38 Correct 5231 ms 291672 KB Output is correct
39 Correct 4355 ms 291380 KB Output is correct
40 Correct 3725 ms 290236 KB Output is correct
41 Correct 4569 ms 285304 KB Output is correct
42 Correct 4788 ms 284176 KB Output is correct
43 Correct 4849 ms 284136 KB Output is correct
44 Correct 5456 ms 290760 KB Output is correct