oj.uz

Submission #75281

# Submission time Handle Problem Language Result Execution time Memory
75281 2018-09-09T05:36:06 Z admin Meetings (IOI18_meetings) C++17
60 / 100
 5500 ms 287500 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];
    
    inline int bet(int a, int b) {
      return hei[a] > hei[b] ? a : b;
    }
 
    inline 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))]);
    }
    
    inline 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 211 ms 158044 KB Output is correct
2 Correct 225 ms 158428 KB Output is correct
3 Correct 226 ms 158428 KB Output is correct
4 Correct 221 ms 158428 KB Output is correct
5 Correct 219 ms 158436 KB Output is correct
6 Correct 220 ms 158368 KB Output is correct
7 Correct 230 ms 158436 KB Output is correct
8 Correct 225 ms 158356 KB Output is correct
9 Correct 220 ms 158428 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 158044 KB Output is correct
2 Correct 225 ms 158428 KB Output is correct
3 Correct 226 ms 158428 KB Output is correct
4 Correct 221 ms 158428 KB Output is correct
5 Correct 219 ms 158436 KB Output is correct
6 Correct 220 ms 158368 KB Output is correct
7 Correct 230 ms 158436 KB Output is correct
8 Correct 225 ms 158356 KB Output is correct
9 Correct 220 ms 158428 KB Output is correct
10 Correct 234 ms 158944 KB Output is correct
11 Correct 230 ms 158972 KB Output is correct
12 Correct 237 ms 158896 KB Output is correct
13 Correct 233 ms 158988 KB Output is correct
14 Correct 234 ms 158952 KB Output is correct
15 Correct 231 ms 158952 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 158116 KB Output is correct
2 Correct 284 ms 162308 KB Output is correct
3 Correct 679 ms 173916 KB Output is correct
4 Correct 604 ms 173620 KB Output is correct
5 Correct 662 ms 174108 KB Output is correct
6 Correct 649 ms 174052 KB Output is correct
7 Correct 672 ms 173772 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 158116 KB Output is correct
2 Correct 284 ms 162308 KB Output is correct
3 Correct 679 ms 173916 KB Output is correct
4 Correct 604 ms 173620 KB Output is correct
5 Correct 662 ms 174108 KB Output is correct
6 Correct 649 ms 174052 KB Output is correct
7 Correct 672 ms 173772 KB Output is correct
8 Correct 695 ms 173880 KB Output is correct
9 Correct 642 ms 173608 KB Output is correct
10 Correct 682 ms 173916 KB Output is correct
11 Correct 676 ms 173608 KB Output is correct
12 Correct 664 ms 173520 KB Output is correct
13 Correct 658 ms 173996 KB Output is correct
14 Correct 717 ms 174368 KB Output is correct
15 Correct 614 ms 173736 KB Output is correct
16 Correct 657 ms 173956 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 158044 KB Output is correct
2 Correct 225 ms 158428 KB Output is correct
3 Correct 226 ms 158428 KB Output is correct
4 Correct 221 ms 158428 KB Output is correct
5 Correct 219 ms 158436 KB Output is correct
6 Correct 220 ms 158368 KB Output is correct
7 Correct 230 ms 158436 KB Output is correct
8 Correct 225 ms 158356 KB Output is correct
9 Correct 220 ms 158428 KB Output is correct
10 Correct 234 ms 158944 KB Output is correct
11 Correct 230 ms 158972 KB Output is correct
12 Correct 237 ms 158896 KB Output is correct
13 Correct 233 ms 158988 KB Output is correct
14 Correct 234 ms 158952 KB Output is correct
15 Correct 231 ms 158952 KB Output is correct
16 Correct 212 ms 158116 KB Output is correct
17 Correct 284 ms 162308 KB Output is correct
18 Correct 679 ms 173916 KB Output is correct
19 Correct 604 ms 173620 KB Output is correct
20 Correct 662 ms 174108 KB Output is correct
21 Correct 649 ms 174052 KB Output is correct
22 Correct 672 ms 173772 KB Output is correct
23 Correct 695 ms 173880 KB Output is correct
24 Correct 642 ms 173608 KB Output is correct
25 Correct 682 ms 173916 KB Output is correct
26 Correct 676 ms 173608 KB Output is correct
27 Correct 664 ms 173520 KB Output is correct
28 Correct 658 ms 173996 KB Output is correct
29 Correct 717 ms 174368 KB Output is correct
30 Correct 614 ms 173736 KB Output is correct
31 Correct 657 ms 173956 KB Output is correct
32 Correct 5220 ms 285316 KB Output is correct
33 Correct 4805 ms 281920 KB Output is correct
34 Correct 5104 ms 287500 KB Output is correct
35 Execution timed out 5548 ms 275396 KB Time limit exceeded
36 Halted 0 ms 0 KB -