oj.uz

Submission #112947

# Submission time Handle Problem Language Result Execution time Memory
112947 2019-05-22T18:22:01 Z imaxblue Meetings (IOI18_meetings) C++17
19 / 100
 931 ms 54540 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][hi[N*2+1]] = min(minl[N][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][hi[N*2+2]] = min(minr[N][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[hi_q] = min(minl_n[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[hi[N]] = min(minr_n[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
*/

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 37852 KB Output is correct
2 Correct 38 ms 37944 KB Output is correct
3 Correct 39 ms 38040 KB Output is correct
4 Correct 39 ms 38036 KB Output is correct
5 Correct 39 ms 37996 KB Output is correct
6 Correct 39 ms 38028 KB Output is correct
7 Correct 38 ms 37880 KB Output is correct
8 Correct 38 ms 38008 KB Output is correct
9 Correct 39 ms 38008 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 37852 KB Output is correct
2 Correct 38 ms 37944 KB Output is correct
3 Correct 39 ms 38040 KB Output is correct
4 Correct 39 ms 38036 KB Output is correct
5 Correct 39 ms 37996 KB Output is correct
6 Correct 39 ms 38028 KB Output is correct
7 Correct 38 ms 37880 KB Output is correct
8 Correct 38 ms 38008 KB Output is correct
9 Correct 39 ms 38008 KB Output is correct
10 Correct 344 ms 38264 KB Output is correct
11 Correct 931 ms 38328 KB Output is correct
12 Correct 329 ms 38236 KB Output is correct
13 Correct 928 ms 38296 KB Output is correct
14 Correct 260 ms 38220 KB Output is correct
15 Correct 259 ms 38304 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 37968 KB Output is correct
2 Incorrect 692 ms 54540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 37968 KB Output is correct
2 Incorrect 692 ms 54540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 37852 KB Output is correct
2 Correct 38 ms 37944 KB Output is correct
3 Correct 39 ms 38040 KB Output is correct
4 Correct 39 ms 38036 KB Output is correct
5 Correct 39 ms 37996 KB Output is correct
6 Correct 39 ms 38028 KB Output is correct
7 Correct 38 ms 37880 KB Output is correct
8 Correct 38 ms 38008 KB Output is correct
9 Correct 39 ms 38008 KB Output is correct
10 Correct 344 ms 38264 KB Output is correct
11 Correct 931 ms 38328 KB Output is correct
12 Correct 329 ms 38236 KB Output is correct
13 Correct 928 ms 38296 KB Output is correct
14 Correct 260 ms 38220 KB Output is correct
15 Correct 259 ms 38304 KB Output is correct
16 Correct 37 ms 37968 KB Output is correct
17 Incorrect 692 ms 54540 KB Output isn't correct
18 Halted 0 ms 0 KB -