oj.uz

Submission #75001

# Submission time Handle Problem Language Result Execution time Memory
75001 2018-09-08T02:53:19 Z Benq Meetings (IOI18_meetings) C++14
60 / 100
 5500 ms 308008 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[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;

struct DSU {
    int par[SZ], left[SZ], right[SZ];
    DSU() {
      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;
    }
    
    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));
    
    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;
    }

    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 = RMQ(); 
    D = DSU();
    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;
}

/*
namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 219740 KB Output is correct
2 Correct 318 ms 219860 KB Output is correct
3 Correct 318 ms 219852 KB Output is correct
4 Correct 330 ms 219820 KB Output is correct
5 Correct 316 ms 219860 KB Output is correct
6 Correct 320 ms 219772 KB Output is correct
7 Correct 320 ms 219768 KB Output is correct
8 Correct 319 ms 219812 KB Output is correct
9 Correct 317 ms 219844 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 219740 KB Output is correct
2 Correct 318 ms 219860 KB Output is correct
3 Correct 318 ms 219852 KB Output is correct
4 Correct 330 ms 219820 KB Output is correct
5 Correct 316 ms 219860 KB Output is correct
6 Correct 320 ms 219772 KB Output is correct
7 Correct 320 ms 219768 KB Output is correct
8 Correct 319 ms 219812 KB Output is correct
9 Correct 317 ms 219844 KB Output is correct
10 Correct 331 ms 220340 KB Output is correct
11 Correct 332 ms 220328 KB Output is correct
12 Correct 333 ms 220244 KB Output is correct
13 Correct 328 ms 220264 KB Output is correct
14 Correct 339 ms 220316 KB Output is correct
15 Correct 330 ms 220260 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 219736 KB Output is correct
2 Correct 383 ms 223576 KB Output is correct
3 Correct 796 ms 231356 KB Output is correct
4 Correct 721 ms 231012 KB Output is correct
5 Correct 787 ms 231496 KB Output is correct
6 Correct 788 ms 231444 KB Output is correct
7 Correct 804 ms 231212 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 219736 KB Output is correct
2 Correct 383 ms 223576 KB Output is correct
3 Correct 796 ms 231356 KB Output is correct
4 Correct 721 ms 231012 KB Output is correct
5 Correct 787 ms 231496 KB Output is correct
6 Correct 788 ms 231444 KB Output is correct
7 Correct 804 ms 231212 KB Output is correct
8 Correct 811 ms 231188 KB Output is correct
9 Correct 769 ms 230908 KB Output is correct
10 Correct 817 ms 231332 KB Output is correct
11 Correct 790 ms 231012 KB Output is correct
12 Correct 752 ms 230804 KB Output is correct
13 Correct 796 ms 231332 KB Output is correct
14 Correct 842 ms 231688 KB Output is correct
15 Correct 697 ms 231060 KB Output is correct
16 Correct 776 ms 231316 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 219740 KB Output is correct
2 Correct 318 ms 219860 KB Output is correct
3 Correct 318 ms 219852 KB Output is correct
4 Correct 330 ms 219820 KB Output is correct
5 Correct 316 ms 219860 KB Output is correct
6 Correct 320 ms 219772 KB Output is correct
7 Correct 320 ms 219768 KB Output is correct
8 Correct 319 ms 219812 KB Output is correct
9 Correct 317 ms 219844 KB Output is correct
10 Correct 331 ms 220340 KB Output is correct
11 Correct 332 ms 220328 KB Output is correct
12 Correct 333 ms 220244 KB Output is correct
13 Correct 328 ms 220264 KB Output is correct
14 Correct 339 ms 220316 KB Output is correct
15 Correct 330 ms 220260 KB Output is correct
16 Correct 309 ms 219736 KB Output is correct
17 Correct 383 ms 223576 KB Output is correct
18 Correct 796 ms 231356 KB Output is correct
19 Correct 721 ms 231012 KB Output is correct
20 Correct 787 ms 231496 KB Output is correct
21 Correct 788 ms 231444 KB Output is correct
22 Correct 804 ms 231212 KB Output is correct
23 Correct 811 ms 231188 KB Output is correct
24 Correct 769 ms 230908 KB Output is correct
25 Correct 817 ms 231332 KB Output is correct
26 Correct 790 ms 231012 KB Output is correct
27 Correct 752 ms 230804 KB Output is correct
28 Correct 796 ms 231332 KB Output is correct
29 Correct 842 ms 231688 KB Output is correct
30 Correct 697 ms 231060 KB Output is correct
31 Correct 776 ms 231316 KB Output is correct
32 Execution timed out 5534 ms 308008 KB Time limit exceeded
33 Halted 0 ms 0 KB -