oj.uz

Submission #112948

# Submission time Handle Problem Language Result Execution time Memory
112948 2019-05-22T18:32:47 Z imaxblue Meetings (IOI18_meetings) C++17
36 / 100
 2787 ms 231120 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define vi vector<int>
#define vpii vector<pii>
#define vp3i vector<p3i>
#define vpll vector<pll>
#define vp3l vector<p3l>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 1LL<<58, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() ((rand() << 14)+rand())
#define scan(X) do{while((X=getchar())<'0'); for(X-='0'; '0'<=(_=getchar()); X=(X<<3)+(X<<1)+_-'0');}while(0)
char _;
#define pi 3.14159265358979323846

int n, q;
ll lft[5005], rit[5005], curr;
vector<ll> ans;
vector<int> h;
void solve(int L, int R){
  vector<pii> hi;
  curr = 0;
  hi.clear();
  hi.pb(mp((1<<30), L-1));
  for (int l = L; l <= R; ++l){
      // << h[l] << ' ' << hi.back().x << endl;
    while(hi.back().x < h[l]){
      curr -= 1LL*(hi.back().y-hi[hi.size()-2].y)*(hi.back().x);
      hi.pop_back();
    }
    curr += 1LL*(l - hi.back().y)*(h[l]);
    hi.pb(mp(h[l], l));
    lft[l] = curr;
    //cout << lft[l] << ' ';
  }
  //cout << endl;
  curr = 0;
  hi.clear();
  hi.pb(mp((1<<30), R+1));
  for (int l = R; l >= L; --l){
    while(hi.back().x < h[l]){
      curr -= 1LL*(hi[hi.size()-2].y-hi.back().y)*(hi.back().x);
      hi.pop_back();
    }
    curr += 1LL*(hi.back().y-l)*(h[l]);
    hi.pb(mp(h[l], l));
    rit[l] = curr;
    //cout << rit[l] << ' ';
  }
  //cout << endl;
  ll res = (1LL<<60);
  for (int l = L; l<= R; ++l){
    res = min(res, lft[l] + rit[l] - h[l]);
  }
  ans.pb(res);
}

int hi[400005];
ll costl[400005], costr[400005];
vector<ll> minl[400005], minr[400005], cntl[400005], cntr[400005];
vector<ll> v, w;
void build(int L, int R, int N){
  if (L == R){
    v.clear(); w.clear();
    fox(l, 21){
      if (h[L] == l) v.pb(h[L]);
      else v.pb((1LL<<58));
      if (h[L] == l) w.pb(1);
      else w.pb(0);
    }
    minl[N] = minr[N] = v;
    cntl[N] = cntr[N] = w;
    fox(l, 21){
      costl[N] += cntl[N][l] * l;
      costr[N] += cntr[N][l] * l;
    }
    hi[N] = h[L];
    return;
    //fox(l, 21){
    //  cout << minl[N][l] << ' ';
    //} cout << endl;
  }
  //cout << N << ' ' << L << ' ' << R << endl;
  build(lseg); build(rseg);
  hi[N] = max(hi[N*2+1], hi[N*2+2]);
  fox(l, 21){
    cntl[N].pb(0);
    cntr[N].pb(0);
  }
  fox(l, 21){
    cntl[N][l] += cntl[N*2+1][l];
    if (l < hi[N*2+1]){
      cntl[N][hi[N*2+1]] += cntl[N*2+2][l];
    } else {
      cntl[N][l] += cntl[N*2+2][l];
    }
  }
  fox(l, 21){
    cntr[N][l] += cntr[N*2+2][l];
    if (l < hi[N*2+2]) cntr[N][hi[N*2+2]] += cntr[N*2+1][l];
    else cntr[N][l] += cntr[N*2+1][l];
  }
  //cout << endl;
  //cout << L << ' ' << R << endl;
  //cout<< hi[N] << ' ' << costl[N] << ' ' << costr[N] << endl;
  //fox(l, 21) cout << cntl[N][l] << ' '; cout << endl;
  //fox(l, 21) cout << cntr[N][l] << ' '; cout << endl;
  //return;
  fox(l, 21){
    costl[N] += cntl[N][l] * l;
    costr[N] += cntr[N][l] * l;
  }

  //return;
  fox(l, 21){
    minl[N].pb(1LL<<58);
    minr[N].pb(1LL<<58);
  }

  ll extra = 0, u = 0;
  fox(l, 21){
    if (l < hi[N*2+1]){
      extra += (hi[N*2+1] - l)*cntl[N*2+2][l];
    }
  }
  fox(l, 21){
    minl[N][l] = min(minl[N][l], minl[N*2+1][l] + extra + costl[N*2+2]);
  }
  extra = 0;
  int p = 0;
  fox(l, 21){
    minl[N][max(l, hi[N*2+1])] = min(minl[N][max(l, hi[N*2+1])], minl[N*2+2][l] + extra + costr[N*2+1]);
    u += cntr[N*2+1][l];
    extra += u;
  }


  extra = 0, u = 0;
  fox(l, 21){
    if (l < hi[N*2+2]){
      extra += (hi[N*2+2] - l)*cntr[N*2+1][l];
    }
  }
  fox(l, 21){
    minr[N][l] = min(minr[N][l], minr[N*2+2][l] + extra + costr[N*2+1]);
  }
  extra = 0;
  p = 0;
  fox(l, 21){
    minr[N][max(l, hi[N*2+2])] = min(minr[N][max(l, hi[N*2+2])], minr[N*2+1][l] + extra + costl[N*2+2]);
    u += cntl[N*2+2][l];
    extra += u;
  }
  //fox(l, 21) cout << (minl[N][l]==(1LL<<58)?-1:minl[N][l]) << ' '; cout << endl;
  //fox(l, 21) cout << (minr[N][l]==(1LL<<58)?-1:minr[N][l]) << ' '; cout << endl;
}
int gl, gr;

int hi_q, hi_n;
ll costl_q, costr_q, costl_n, costr_n;
vector<ll> minl_q, minr_q, cntl_q, cntr_q;
vector<ll> minl_n, minr_n, cntl_n, cntr_n;
void mrg(int N){
  hi_n = max(hi_q, hi[N]);
  cntl_n.clear();
  cntr_n.clear();
  minl_n.clear();
  minr_n.clear();
  costl_n = costr_n = 0;
  fox(l, 21){
    cntl_n.pb(0);
    cntr_n.pb(0);
  }
  fox(l, 21){
    cntl_n[l] += cntl_q[l];
    if (l < hi_q){
      cntl_n[hi_q] += cntl[N][l];
    } else {
      cntl_n[l] += cntl[N][l];
    }
  }
  fox(l, 21){
    cntr_n[l] += cntr[N][l];
    if (l < hi[N]) cntr_n[hi[N]] += cntr_q[l];
    else cntr_n[l] += cntr_q[l];
  }
  //return;
  fox(l, 21){
    costl_n += cntl_n[l] * l;
    costr_n += cntr_n[l] * l;
  }

  //return;
  fox(l, 21){
    minl_n.pb(1LL<<58);
    minr_n.pb(1LL<<58);
  }

  ll extra = 0, u = 0;
  fox(l, 21){
    if (l < hi_q){
      extra += (hi_q - l)*cntl[N][l];
    }
  }
  fox(l, 21){
    minl_n[l] = min(minl_n[l], minl_q[l] + extra + costl[N]);
  }
  extra = 0;
  int p = 0;
  fox(l, 21){
    minl_n[max(l, hi_q)] = min(minl_n[max(l, hi_q)], minl[N][l] + extra + costr_q);
    u += cntr_q[l];
    extra += u;
  }


  extra = 0, u = 0;
  fox(l, 21){
    if (l < hi[N]){
      extra += (hi[N] - l)*cntr_q[l];
    }
  }
  fox(l, 21){
    minr_n[l] = min(minr_n[l], minr[N][l] + extra + costr_q);
  }
  extra = 0;
  p = 0;
  fox(l, 21){
    minr_n[max(l, hi[N])] = min(minr_n[max(l, hi[N])], minr_q[l] + extra + costl[N]);
    u += cntl[N][l];
    extra += u;
  }
  hi_q = hi_n;
  costl_q = costl_n;
  costr_q = costr_n;
  minl_q = minl_n;
  cntl_q = cntl_n;
  minr_q = minr_n;
  cntr_q = cntr_n;
}
void query(int L, int R, int N){
  if (L >gr || R <gl) return;
  if (gl <= L && R <= gr){
    mrg(N);
    return;
  }
  query(lseg); query(rseg);
}
void solve2(int L, int R){
  gl = L; gr = R;
  hi_q = 0;
  costl_q = costr_q = 0;
  cntl_q = cntr_q = vector<ll>(21, 0LL);
  minl_q = minr_q = vector<ll>(21, 0LL);
  query(0, n-1, 0);
  ll res = (1LL<<58);
  fox(l, 21){
    res = min(res, min(minl_q[l], minr_q[l]));
  }
  ans.pb(res);
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
  n = H.size();
  q = L.size();
  h = H;
  if (n <= 5000 && q <= 5000){
    fox(l, q){
      solve(L[l], R[l]);
    }
    return ans;
  }
  //cout << "*" << ans.size() << endl;
  build(0, n-1, 0);
  fox(l, q){
    solve2(L[l], R[l]);
  }
  return ans;
}
/*
int main(){
  int n, q, h, x, y;
  vector<int> H, L, R;
  cin >> n >> q;
  fox(l, n){
    cin >> h;
    H.pb(h);
  }
  fox(l, q){
    cin >> x >> y;
    L.pb(x);
    R.pb(y);
  }
  vector<ll> res = minimum_costs(H, L, R);
  fox(l, res.size()) cout << res[l] << ' '; cout << endl;
  return 0;
}*/
/*
4 6
2 4 3 5
0 2
1 3
0 3
1 1
1 3
0 2

6 5
1 5 2 4 3 6
0 4
0 2
0 5
1 4
2 3
*/

Compilation message

meetings.cpp: In function 'void build(int, int, int)':
meetings.cpp:149:7: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   int p = 0;
       ^
meetings.cpp: In function 'void mrg(int)':
meetings.cpp:228:7: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   int p = 0;
       ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 37960 KB Output is correct
2 Correct 38 ms 37932 KB Output is correct
3 Correct 40 ms 37932 KB Output is correct
4 Correct 39 ms 37972 KB Output is correct
5 Correct 40 ms 38024 KB Output is correct
6 Correct 38 ms 38036 KB Output is correct
7 Correct 38 ms 37948 KB Output is correct
8 Correct 41 ms 38024 KB Output is correct
9 Correct 38 ms 38008 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 37960 KB Output is correct
2 Correct 38 ms 37932 KB Output is correct
3 Correct 40 ms 37932 KB Output is correct
4 Correct 39 ms 37972 KB Output is correct
5 Correct 40 ms 38024 KB Output is correct
6 Correct 38 ms 38036 KB Output is correct
7 Correct 38 ms 37948 KB Output is correct
8 Correct 41 ms 38024 KB Output is correct
9 Correct 38 ms 38008 KB Output is correct
10 Correct 330 ms 38324 KB Output is correct
11 Correct 923 ms 38280 KB Output is correct
12 Correct 331 ms 38272 KB Output is correct
13 Correct 938 ms 38304 KB Output is correct
14 Correct 267 ms 38268 KB Output is correct
15 Correct 277 ms 38324 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 37864 KB Output is correct
2 Correct 681 ms 54620 KB Output is correct
3 Correct 2717 ms 230036 KB Output is correct
4 Correct 2787 ms 229976 KB Output is correct
5 Correct 872 ms 229972 KB Output is correct
6 Correct 2140 ms 230064 KB Output is correct
7 Correct 2682 ms 230020 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 37864 KB Output is correct
2 Correct 681 ms 54620 KB Output is correct
3 Correct 2717 ms 230036 KB Output is correct
4 Correct 2787 ms 229976 KB Output is correct
5 Correct 872 ms 229972 KB Output is correct
6 Correct 2140 ms 230064 KB Output is correct
7 Correct 2682 ms 230020 KB Output is correct
8 Incorrect 2769 ms 231120 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 37960 KB Output is correct
2 Correct 38 ms 37932 KB Output is correct
3 Correct 40 ms 37932 KB Output is correct
4 Correct 39 ms 37972 KB Output is correct
5 Correct 40 ms 38024 KB Output is correct
6 Correct 38 ms 38036 KB Output is correct
7 Correct 38 ms 37948 KB Output is correct
8 Correct 41 ms 38024 KB Output is correct
9 Correct 38 ms 38008 KB Output is correct
10 Correct 330 ms 38324 KB Output is correct
11 Correct 923 ms 38280 KB Output is correct
12 Correct 331 ms 38272 KB Output is correct
13 Correct 938 ms 38304 KB Output is correct
14 Correct 267 ms 38268 KB Output is correct
15 Correct 277 ms 38324 KB Output is correct
16 Correct 57 ms 37864 KB Output is correct
17 Correct 681 ms 54620 KB Output is correct
18 Correct 2717 ms 230036 KB Output is correct
19 Correct 2787 ms 229976 KB Output is correct
20 Correct 872 ms 229972 KB Output is correct
21 Correct 2140 ms 230064 KB Output is correct
22 Correct 2682 ms 230020 KB Output is correct
23 Incorrect 2769 ms 231120 KB Output isn't correct
24 Halted 0 ms 0 KB -