Submission #112951

# Submission time Handle Problem Language Result Execution time Memory
112951 2019-05-22T18:38:26 Z imaxblue Meetings (IOI18_meetings) C++17
36 / 100
2999 ms 231488 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
#define int ll

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<int32_t> H, vector<int32_t> L, vector<int32_t> R){
  n = H.size();
  q = L.size();
  fox(l, n) h.pb(H[l]);
  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;
}
/*
int32_t 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(long long int, long long int, long long int)':
meetings.cpp:150:7: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   int p = 0;
       ^
meetings.cpp: In function 'void mrg(long long int)':
meetings.cpp:229:7: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   int p = 0;
       ^
# Verdict Execution time Memory Grader output
1 Correct 38 ms 37880 KB Output is correct
2 Correct 39 ms 38084 KB Output is correct
3 Correct 39 ms 37972 KB Output is correct
4 Correct 39 ms 37980 KB Output is correct
5 Correct 40 ms 38080 KB Output is correct
6 Correct 39 ms 38008 KB Output is correct
7 Correct 37 ms 38008 KB Output is correct
8 Correct 39 ms 38012 KB Output is correct
9 Correct 39 ms 38100 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 38 ms 37880 KB Output is correct
2 Correct 39 ms 38084 KB Output is correct
3 Correct 39 ms 37972 KB Output is correct
4 Correct 39 ms 37980 KB Output is correct
5 Correct 40 ms 38080 KB Output is correct
6 Correct 39 ms 38008 KB Output is correct
7 Correct 37 ms 38008 KB Output is correct
8 Correct 39 ms 38012 KB Output is correct
9 Correct 39 ms 38100 KB Output is correct
10 Correct 375 ms 38324 KB Output is correct
11 Correct 1047 ms 38292 KB Output is correct
12 Correct 373 ms 38380 KB Output is correct
13 Correct 1047 ms 38376 KB Output is correct
14 Correct 293 ms 38364 KB Output is correct
15 Correct 297 ms 38360 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 37 ms 37852 KB Output is correct
2 Correct 742 ms 54652 KB Output is correct
3 Correct 2801 ms 231368 KB Output is correct
4 Correct 2796 ms 231464 KB Output is correct
5 Correct 900 ms 231444 KB Output is correct
6 Correct 2320 ms 231464 KB Output is correct
7 Correct 2822 ms 231488 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 37 ms 37852 KB Output is correct
2 Correct 742 ms 54652 KB Output is correct
3 Correct 2801 ms 231368 KB Output is correct
4 Correct 2796 ms 231464 KB Output is correct
5 Correct 900 ms 231444 KB Output is correct
6 Correct 2320 ms 231464 KB Output is correct
7 Correct 2822 ms 231488 KB Output is correct
8 Incorrect 2999 ms 231468 KB Output isn't correct
9 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 38 ms 37880 KB Output is correct
2 Correct 39 ms 38084 KB Output is correct
3 Correct 39 ms 37972 KB Output is correct
4 Correct 39 ms 37980 KB Output is correct
5 Correct 40 ms 38080 KB Output is correct
6 Correct 39 ms 38008 KB Output is correct
7 Correct 37 ms 38008 KB Output is correct
8 Correct 39 ms 38012 KB Output is correct
9 Correct 39 ms 38100 KB Output is correct
10 Correct 375 ms 38324 KB Output is correct
11 Correct 1047 ms 38292 KB Output is correct
12 Correct 373 ms 38380 KB Output is correct
13 Correct 1047 ms 38376 KB Output is correct
14 Correct 293 ms 38364 KB Output is correct
15 Correct 297 ms 38360 KB Output is correct
16 Correct 37 ms 37852 KB Output is correct
17 Correct 742 ms 54652 KB Output is correct
18 Correct 2801 ms 231368 KB Output is correct
19 Correct 2796 ms 231464 KB Output is correct
20 Correct 900 ms 231444 KB Output is correct
21 Correct 2320 ms 231464 KB Output is correct
22 Correct 2822 ms 231488 KB Output is correct
23 Incorrect 2999 ms 231468 KB Output isn't correct
24 Halted 0 ms 0 KB -