oj.uz

Submission #82829

# Submission time Handle Problem Language Result Execution time Memory
82829 2018-11-02T00:29:48 Z Benq Meetings (IOI18_meetings) C++14
60 / 100
 5500 ms 289500 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;
        z = getFst(x,lo,hi,ori,2*ind+1,M+1,R); assert(z != -1); return z;
    } 
};
 
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 306 ms 219748 KB Output is correct
2 Correct 319 ms 219760 KB Output is correct
3 Correct 326 ms 219844 KB Output is correct
4 Correct 326 ms 219820 KB Output is correct
5 Correct 322 ms 219764 KB Output is correct
6 Correct 317 ms 219780 KB Output is correct
7 Correct 323 ms 219836 KB Output is correct
8 Correct 318 ms 219776 KB Output is correct
9 Correct 312 ms 219744 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 219748 KB Output is correct
2 Correct 319 ms 219760 KB Output is correct
3 Correct 326 ms 219844 KB Output is correct
4 Correct 326 ms 219820 KB Output is correct
5 Correct 322 ms 219764 KB Output is correct
6 Correct 317 ms 219780 KB Output is correct
7 Correct 323 ms 219836 KB Output is correct
8 Correct 318 ms 219776 KB Output is correct
9 Correct 312 ms 219744 KB Output is correct
10 Correct 324 ms 220284 KB Output is correct
11 Correct 395 ms 220216 KB Output is correct
12 Correct 398 ms 220280 KB Output is correct
13 Correct 325 ms 220320 KB Output is correct
14 Correct 343 ms 220252 KB Output is correct
15 Correct 323 ms 220260 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 219752 KB Output is correct
2 Correct 376 ms 223516 KB Output is correct
3 Correct 769 ms 229272 KB Output is correct
4 Correct 709 ms 228984 KB Output is correct
5 Correct 770 ms 229456 KB Output is correct
6 Correct 763 ms 229408 KB Output is correct
7 Correct 773 ms 229200 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 219752 KB Output is correct
2 Correct 376 ms 223516 KB Output is correct
3 Correct 769 ms 229272 KB Output is correct
4 Correct 709 ms 228984 KB Output is correct
5 Correct 770 ms 229456 KB Output is correct
6 Correct 763 ms 229408 KB Output is correct
7 Correct 773 ms 229200 KB Output is correct
8 Correct 818 ms 229268 KB Output is correct
9 Correct 751 ms 229464 KB Output is correct
10 Correct 785 ms 229740 KB Output is correct
11 Correct 798 ms 229600 KB Output is correct
12 Correct 749 ms 229528 KB Output is correct
13 Correct 784 ms 229948 KB Output is correct
14 Correct 818 ms 230268 KB Output is correct
15 Correct 699 ms 229668 KB Output is correct
16 Correct 772 ms 229900 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 219748 KB Output is correct
2 Correct 319 ms 219760 KB Output is correct
3 Correct 326 ms 219844 KB Output is correct
4 Correct 326 ms 219820 KB Output is correct
5 Correct 322 ms 219764 KB Output is correct
6 Correct 317 ms 219780 KB Output is correct
7 Correct 323 ms 219836 KB Output is correct
8 Correct 318 ms 219776 KB Output is correct
9 Correct 312 ms 219744 KB Output is correct
10 Correct 324 ms 220284 KB Output is correct
11 Correct 395 ms 220216 KB Output is correct
12 Correct 398 ms 220280 KB Output is correct
13 Correct 325 ms 220320 KB Output is correct
14 Correct 343 ms 220252 KB Output is correct
15 Correct 323 ms 220260 KB Output is correct
16 Correct 307 ms 219752 KB Output is correct
17 Correct 376 ms 223516 KB Output is correct
18 Correct 769 ms 229272 KB Output is correct
19 Correct 709 ms 228984 KB Output is correct
20 Correct 770 ms 229456 KB Output is correct
21 Correct 763 ms 229408 KB Output is correct
22 Correct 773 ms 229200 KB Output is correct
23 Correct 818 ms 229268 KB Output is correct
24 Correct 751 ms 229464 KB Output is correct
25 Correct 785 ms 229740 KB Output is correct
26 Correct 798 ms 229600 KB Output is correct
27 Correct 749 ms 229528 KB Output is correct
28 Correct 784 ms 229948 KB Output is correct
29 Correct 818 ms 230268 KB Output is correct
30 Correct 699 ms 229668 KB Output is correct
31 Correct 772 ms 229900 KB Output is correct
32 Execution timed out 5558 ms 289500 KB Time limit exceeded
33 Halted 0 ms 0 KB -