Submission #1085290

#TimeUsernameProblemLanguageResultExecution timeMemory
1085290vladiliusMeetings (IOI18_meetings)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") using namespace std; using ll = long long; using pii = pair<int, int>; using pil = pair<int, ll>; using pll = pair<ll, ll>; #define pb push_back #define ff first #define ss second #define ins insert #define arr3 array<int, 3> const ll inf = 1e18; const int N = 7.5e5; struct DS{ struct line{ int k; ll b; ll operator ()(int x){ return 1LL * k * x + b; } line(int ks, ll bs){ k = ks; b = bs; } }; pil t[4 * N]; pil p[4 * N]; int n; DS(int ns){ n = ns; for (int i = 0; i < 4 * n; i++){ t[i] = {0, inf}; p[i] = {0, 0}; } } void apply(int v, pil x){ t[v].ff += x.ff; t[v].ss += x.ss; p[v].ff += x.ff; p[v].ss += x.ss; } void push1(int& v, int& tl, int& tr){ int vv = 2 * v; apply(vv, p[v]); apply(vv + 1, p[v]); p[v] = {0, 0}; } void insert(int v, int tl, int tr, pil f){ if (tl == tr){ if ((1LL * t[v].ff * tl + t[v].ss) > (1LL * f.ff * tl + f.ss)) t[v] = f; return; } int tm = (tl + tr) / 2, vv = 2 * v; push1(v, tl, tr); if (t[v].ff > f.ff) swap(t[v], f); if ((1LL * f.ff * tm + f.ss) <= (1LL * t[v].ff * tm + t[v].ss)){ swap(t[v], f); insert(vv + 1, tm + 1, tr, f); } else { insert(vv, tl, tm, f); } } void chmin(int v, int tl, int tr, int& l, int& r, pil& f){ if (l > tr || r < tl) return; if (l <= tl && tr <= r){ insert(v, tl, tr, f); return; } int tm = (tl + tr) / 2, vv = 2 * v; push1(v, tl, tr); chmin(vv, tl, tm, l, r, f); chmin(vv + 1, tm + 1, tr, l, r, f); } void chmin(int l, int r, int k, ll b){ pil f = {k, b}; chmin(1, 1, n, l, r, f); } void add(int v, int tl, int tr, int& l, int& r, line& f){ if (l > tr || r < tl) return; if (l <= tl && tr <= r){ apply(v, {f.k, f.b}); return; } int tm = (tl + tr) / 2, vv = 2 * v; push1(v, tl, tr); add(vv, tl, tm, l, r, f); add(vv + 1, tm + 1, tr, l, r, f); } void add(int l, int r, int k, ll b){ line f(k, b); add(1, 1, n, l, r, f); } ll get(int v, int tl, int tr, int& x){ if (tl == tr) return (1LL * t[v].ff * x + t[v].ss); int tm = (tl + tr) / 2, vv = 2 * v; push1(v, tl, tr); if (x <= tm){ return min((1LL * t[v].ff * x + t[v].ss), get(vv, tl, tm, x)); } return min((1LL * t[v].ff * x + t[v].ss), get(vv + 1, tm + 1, tr, x)); } ll get(int x){ return get(1, 1, n, x); } }; vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){ const int A = 1e9; int n = (int) H.size(), q = (int) L.size(); vector<int> h(n + 1), aa; for (int i = 1; i <= n; i++){ h[i] = H[i - 1]; aa.pb(h[i]); } sort(aa.begin(), aa.end()); vector<int> vv; int i = 0; while (i < n){ int j = i; while (j < n && aa[i] == aa[j]){ j++; } vv.pb(aa[i]); i = j; } vector<int> :: iterator it; auto pos = [&](int x){ it = lower_bound(vv.begin(), vv.end(), x); int j = (int) (it - vv.begin()); return j; }; vector<int> d[(int) vv.size()]; for (int i = 1; i <= n; i++){ d[pos(h[i])].pb(i); } vector<int> log(n + 1); for (int i = 2; i <= n; i++) log[i] = log[i / 2] + 1; const int lg = log[n]; int pw[n + 1][lg + 1], pw1[n + 1][lg + 1]; for (int i = 1; i <= n; i++) pw[i][0] = pw1[i][0] = h[i]; for (int j = 1; j <= lg; j++){ for (int i = 1; i + (1 << j) <= n + 1; i++){ pw[i][j] = max(pw[i][j - 1], pw[i + (1 << (j - 1))][j - 1]); pw1[i][j] = min(pw1[i][j - 1], pw1[i + (1 << (j - 1))][j - 1]); } } auto get = [&](int l, int r){ int k = log[r - l + 1]; return max(pw[l][k], pw[r - (1 << k) + 1][k]); }; auto getm = [&](int l, int r){ int k = log[r - l + 1]; return min(pw1[l][k], pw1[r - (1 << k) + 1][k]); }; int f[n + 1], fs = 0; auto pp = [&](int x, int l, int r){ fs = 0; int X = pos(x); it = lower_bound(d[X].begin(), d[X].end(), l); while (it != d[X].end() && (*it) <= r){ f[fs++] = (*it); it++; } }; pii all1[n + 1]; int s1 = 0; auto gp = [&](int x, int l, int r){ pp(x, l, r); s1 = 0; int pre = l; for (int j = 0; j < fs; j++){ int i = f[j]; if (pre < i){ all1[s1++] = {pre, i - 1}; } pre = i + 1; } if (pre <= r) all1[s1++] = {pre, r}; }; vector<pii> mp[(int) vv.size()]; function<void(int, int)> build1 = [&](int l, int r){ int m = get(l, r); mp[pos(m)].pb({l, r}); gp(m, l, r); vector<pii> all(s1); for (int i = 0; i < s1; i++) all[i] = all1[i]; for (auto [l1, r1]: all){ build1(l1, r1); } }; build1(1, n); vector<ll> out(q + 1); vector<vector<arr3>> qs[(int) vv.size()]; for (int i = 0; i < vv.size(); i++){ qs[i].resize(mp[i].size()); } for (int i = 1; i <= q; i++){ int l, r; l = L[i - 1]; r = R[i - 1]; l++; r++; if (get(l, r) == getm(l, r)){ out[i] = 1LL * h[l] * (r - l + 1); continue; } int k = pos(get(l, r)), l1 = 0, r1 = (int) mp[k].size() - 1; while (l1 + 1 < r1){ int m = (l1 + r1) / 2; if (mp[k][m].ff <= l){ l1 = m; } else { r1 = m - 1; } } if (mp[k][r1].ff <= l) l1 = r1; qs[k][l1].pb({l, r, i}); } DS T1(n), T2(n); for (int i = 1; i <= n; i++){ T1.add(i, i, 0, -inf); T2.add(i, i, 0, -inf); } vector<int> :: iterator it1, it2; ll sp[n + 1][lg + 1]; function<void(int, int)> build = [&](int l, int r){ int m = get(l, r); gp(m, l, r); vector<pii> all(s1); for (int i = 0; i < s1; i++) all[i] = all1[i]; for (auto [l1, r1]: all) build(l1, r1); if (all.empty()){ T1.add(l, r, m, -1LL * m * (l - 1)); T2.add(l, r, -m, 1LL * m * (r + 1)); } for (auto [l1, r1]: all){ int m1 = get(l1, r1); gp(m1, l1, r1); ll mn = inf; for (int i = 0; i < s1; i++){ // f(l1, i) = min(mn + m1 * (i - l1), f(l2, i) + m1 * (l2 - l1)); auto [l2, r2] = all1[i]; ll F = T1.get(r2); T1.add(l2, r2, 0, 1LL * m1 * (l2 - l1)); if (mn != inf) T1.chmin(l2, r2, m1, mn - 1LL * m1 * l1); mn = min(mn, F - 1LL * m1 * (r2 - l2)); } mn = inf; for (int i = s1 - 1; i >= 0; i--){ // f(i, r1) = min(mn + m1 * (r1 - i), f(i, r2) + m1 * (r1 - r2)); auto [l2, r2] = all1[i]; ll F = T2.get(l2); T2.add(l2, r2, 0, 1LL * m1 * (r1 - r2)); if (mn != inf) T2.chmin(l2, r2, -m1, mn + 1LL * m1 * r1); mn = min(mn, F - 1LL * m1 * (r2 - l2)); } for (int j = 0; j < fs; j++){ int i = f[j]; ll mn = 1LL * m1 * (i - l1 + 1); if (i > l1) mn = min(mn, T1.get(i - 1) + m1); T1.add(i, i, 0, mn - T1.get(i)); } for (int j = fs - 1; j >= 0; j--){ int i = f[j]; ll mn = 1LL * m1 * (r1 - i + 1); if (i < r1) mn = min(mn, T2.get(i + 1) + m1); T2.add(i, i, 0, mn - T2.get(i)); } } if (all.empty()) return; vector<int> x1, y1; for (auto [l1, r1]: all){ x1.pb(l1); y1.pb(r1); } int N = (int) all.size(), LG = log2(N); for (int i = 1; i <= N; i++) sp[i][0] = (T1.get(all[i - 1].ss) - 1LL * m * (all[i - 1].ss - all[i - 1].ff)); for (int j = 1; j <= LG; j++){ for (int i = 1; i + (1 << j) <= N + 1; i++){ sp[i][j] = min(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]); } } auto gets = [&](int l, int r){ if (l > r) return inf; int k = log[r - l + 1]; return min(sp[l][k], sp[r - (1 << k) + 1][k]); }; int M = pos(m); int l1 = 0, r1 = (int) mp[M].size() - 1; while (l1 + 1 < r1){ int m1 = (l1 + r1) / 2; if (mp[M][m1].ff < l){ l1 = m1 + 1; } else { r1 = m1; } } if (mp[M][r1].ff == l) l1 = r1; for (auto [ql, qr, i]: qs[M][l1]){ it1 = lower_bound(x1.begin(), x1.end(), ql); it2 = upper_bound(y1.begin(), y1.end(), qr); it2--; int i1 = (int) (it1 - x1.begin()), i2 = (int) (it2 - y1.begin()); out[i] = gets(i1 + 1, i2 + 1); if (out[i] != inf) out[i] += 1LL * m * (qr - ql); if (i1 > 0){ i1--; if (all[i1].ss >= ql){ out[i] = min(out[i], T2.get(ql) + 1LL * m * (qr - all[i1].ss)); } } if (i2 + 1 < all.size()){ i2++; if (all[i2].ff <= qr){ out[i] = min(out[i], T1.get(qr) + 1LL * m * (all[i2].ff - ql)); } } } }; build(1, n); vector<ll> ret; for (int i = 1; i <= q; i++) ret.pb(out[i]); return ret; }

Compilation message (stderr)

meetings.cpp: In lambda function:
meetings.cpp:155:20: sorry, unimplemented: capture of variably-modified type 'int [(n + 1)][(((int)lg) + 1)]' that is not an N3639 array of runtime bound
  155 |         return max(pw[l][k], pw[r - (1 << k) + 1][k]);
      |                    ^~
meetings.cpp:155:20: note: because the array element type 'int [(((int)lg) + 1)]' has variable size
meetings.cpp:155:30: sorry, unimplemented: capture of variably-modified type 'int [(n + 1)][(((int)lg) + 1)]' that is not an N3639 array of runtime bound
  155 |         return max(pw[l][k], pw[r - (1 << k) + 1][k]);
      |                              ^~
meetings.cpp:155:30: note: because the array element type 'int [(((int)lg) + 1)]' has variable size
meetings.cpp: In lambda function:
meetings.cpp:160:20: sorry, unimplemented: capture of variably-modified type 'int [(n + 1)][(((int)lg) + 1)]' that is not an N3639 array of runtime bound
  160 |         return min(pw1[l][k], pw1[r - (1 << k) + 1][k]);
      |                    ^~~
meetings.cpp:160:20: note: because the array element type 'int [(((int)lg) + 1)]' has variable size
meetings.cpp:160:31: sorry, unimplemented: capture of variably-modified type 'int [(n + 1)][(((int)lg) + 1)]' that is not an N3639 array of runtime bound
  160 |         return min(pw1[l][k], pw1[r - (1 << k) + 1][k]);
      |                               ^~~
meetings.cpp:160:31: note: because the array element type 'int [(((int)lg) + 1)]' has variable size
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:206:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |     for (int i = 0; i < vv.size(); i++){
      |                     ~~^~~~~~~~~~~
meetings.cpp:219:16: error: 'l1' was not declared in this scope; did you mean 'l'?
  219 |         while (l1 + 1 < r1){
      |                ^~
      |                l
meetings.cpp:219:25: error: 'r1' was not declared in this scope; did you mean 'r'?
  219 |         while (l1 + 1 < r1){
      |                         ^~
      |                         r
meetings.cpp:228:19: error: 'r1' was not declared in this scope; did you mean 'r'?
  228 |         if (mp[k][r1].ff <= l) l1 = r1;
      |                   ^~
      |                   r
meetings.cpp:228:32: error: 'l1' was not declared in this scope; did you mean 'l'?
  228 |         if (mp[k][r1].ff <= l) l1 = r1;
      |                                ^~
      |                                l
meetings.cpp:230:15: error: 'l1' was not declared in this scope; did you mean 'l'?
  230 |         qs[k][l1].pb({l, r, i});
      |               ^~
      |               l
meetings.cpp: In lambda function:
meetings.cpp:303:38: sorry, unimplemented: capture of variably-modified type 'll [(n + 1)][(((int)lg) + 1)]' {aka 'long long int [(n + 1)][(((int)lg) + 1)]'} that is not an N3639 array of runtime bound
  303 |         for (int i = 1; i <= N; i++) sp[i][0] = (T1.get(all[i - 1].ss) - 1LL * m * (all[i - 1].ss - all[i - 1].ff));
      |                                      ^~
meetings.cpp:303:38: note: because the array element type 'll [(((int)lg) + 1)]' {aka 'long long int [(((int)lg) + 1)]'} has variable size
meetings.cpp:306:17: sorry, unimplemented: capture of variably-modified type 'll [(n + 1)][(((int)lg) + 1)]' {aka 'long long int [(n + 1)][(((int)lg) + 1)]'} that is not an N3639 array of runtime bound
  306 |                 sp[i][j] = min(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
      |                 ^~
meetings.cpp:306:17: note: because the array element type 'll [(((int)lg) + 1)]' {aka 'long long int [(((int)lg) + 1)]'} has variable size
meetings.cpp:306:32: sorry, unimplemented: capture of variably-modified type 'll [(n + 1)][(((int)lg) + 1)]' {aka 'long long int [(n + 1)][(((int)lg) + 1)]'} that is not an N3639 array of runtime bound
  306 |                 sp[i][j] = min(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
      |                                ^~
meetings.cpp:306:32: note: because the array element type 'll [(((int)lg) + 1)]' {aka 'long long int [(((int)lg) + 1)]'} has variable size
meetings.cpp:306:46: sorry, unimplemented: capture of variably-modified type 'll [(n + 1)][(((int)lg) + 1)]' {aka 'long long int [(n + 1)][(((int)lg) + 1)]'} that is not an N3639 array of runtime bound
  306 |                 sp[i][j] = min(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
      |                                              ^~
meetings.cpp:306:46: note: because the array element type 'll [(((int)lg) + 1)]' {aka 'long long int [(((int)lg) + 1)]'} has variable size
meetings.cpp: In lambda function:
meetings.cpp:313:24: sorry, unimplemented: capture of variably-modified type 'll [(n + 1)][(((int)lg) + 1)]' {aka 'long long int [(n + 1)][(((int)lg) + 1)]'} that is not an N3639 array of runtime bound
  313 |             return min(sp[l][k], sp[r - (1 << k) + 1][k]);
      |                        ^~
meetings.cpp:313:24: note: because the array element type 'll [(((int)lg) + 1)]' {aka 'long long int [(((int)lg) + 1)]'} has variable size
meetings.cpp:313:34: sorry, unimplemented: capture of variably-modified type 'll [(n + 1)][(((int)lg) + 1)]' {aka 'long long int [(n + 1)][(((int)lg) + 1)]'} that is not an N3639 array of runtime bound
  313 |             return min(sp[l][k], sp[r - (1 << k) + 1][k]);
      |                                  ^~
meetings.cpp:313:34: note: because the array element type 'll [(((int)lg) + 1)]' {aka 'long long int [(((int)lg) + 1)]'} has variable size
meetings.cpp: In lambda function:
meetings.cpp:343:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  343 |             if (i2 + 1 < all.size()){
      |                 ~~~~~~~^~~~~~~~~~~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:108:15: warning: unused variable 'A' [-Wunused-variable]
  108 |     const int A = 1e9;
      |               ^