Submission #289879

#	Time	Username	Problem	Language	Result	Execution time	Memory
289879		dandrozavr	Meetings (IOI18_meetings)	C++14	19 / 100	1062 ms	786436 KiB

meetings

/*
Uruchamiamy samolot zwiadowczy ( + 500% do wzlamaniej )

/▄/  /█/  /◐/  /▐/   /▌/ /▀/ /░/ /  / choose your own style!

***IT'S OUR LONG WAY TO THE OIILLLL***


░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀  ░░░░░░░░███░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░█▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▀██████████████████████████████████████████████████
░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▄████▄████████ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █████
░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█████████▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀  ░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████░░░░░░░░░░░░░░░
*/
//#pragma GCC target("avx2")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;template <typename T> using ordered_set = tree <T, null_type, less< T >, rb_tree_tag,tree_order_statistics_node_update>;
namespace fastio {template <class T> ostream &operator<<(ostream &os, const vector<T> &container) {for (auto &u : container)os << u << " ";return os;} template<class T1, class T2> ostream& operator << (ostream& os, const pair<T1, T2>& p) {return os << p.first << " " << p.second;}template <class T> ostream &operator<<(ostream &os, set<T> const& con) {    for (auto &u : con)        os << u << " ";return os;} void pr() {} template <typename T, typename... args> void pr(T x, args... tail) {cout << x << " ";pr(tail...);}} using namespace fastio;
#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define F first
#define S second
#define pii pair < int , int >
#define _ <<" "<<
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
mt19937_64 gen(chrono::high_resolution_clock::now().time_since_epoch().count());

vector < int > H;
ll solve(int l, int r, int i){
    int mx1 = -1e9;
    ll otv = 0;
    for (int j = i; j >= l; --j){
        mx1 = max(mx1, H[j]);
        otv += mx1;
    }
    int mx2 = H[i];
    for (int j = i + 1; j <= r; ++j){
        mx2 = max(mx2, H[j]);
        otv += mx2;
    }
    return otv;
}
const int N = 2e5 + 5;
const int cnst = 18;

//int upl[N][18], upr[N][18];
//ll suml[N][18], sumr[N][18];

int t[N * 4], l[N * 4], r[N * 4];

void build(int v, int tl, int tr){
//    cout << v _ tl _ tr << endl;
    if (tl == tr){
        t[v] = H[tl];
        l[v] = H[tl];
        r[v] = H[tl];
        return;
    }
    int tm = (tl + tr) >> 1;
    build(v << 1, tl, tm);
    build(v << 1 | 1, tm + 1, tr);
    t[v] = max(t[v << 1], t[v << 1 | 1]);
    t[v] = max(t[v], r[v << 1] + l[v << 1 | 1]);
    l[v] = l[v << 1];
    if(l[v] >= tm - tl + 1) l[v] += l[v << 1 | 1];
    r[v] = r[v << 1 | 1];
    if(r[v] >= tr - tm) r[v] += r[v << 1];
//    cout << tl _ tr _ t[v] _ l[v] _ r[v]  << endl;
}

pair < int, pii > solve(int v, int tl, int tr, int l, int r){
    if (l > r)  return {0, {0, 0}};
//    cout << tl _ tr _ t[v] << endl;
    if (tl == l && tr == r) return {t[v], {::l[v], ::r[v]}};
    int tm = (tl + tr) >> 1;
    auto f = solve(v << 1, tl, tm, l, min(tm, r));
    auto s = solve(v << 1 | 1, tm + 1, tr, max(tm + 1, l), r);
    pair < int , pii > ans = {max(f.F, s.F), {f.S.F, s.S.S}};
    ans.F = max(ans.F, f.S.S + s.S.F);
    if (ans.S.F >= tm - tl + 1) ans.S.F += s.S.F;
    if (ans.S.S >= tr - tm) ans.S.S += f.S.S;
    return ans;
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    int n = H.size();
    int q = L.size();
    if (n <= 5e5){
        ::H = H;
        vector < ll > res;
        ll dpr[n][n] = {}, dpl[n][n] = {};
        for (int i = 0; i < n; ++i){
            int mx1 = 0;
            ll sum = 0;
            for (int j = i; j < n; ++j){
                mx1 = max(mx1, H[j]);
                sum += mx1;
                dpr[i][j] = sum;
            }
            mx1 = H[i];
            sum = 0;
            for (int j = i - 1; j >= 0; --j){
                mx1 = max(mx1, H[j]);
                sum += mx1;
                dpl[i][j] = sum;
            }
        }

        for (int i = 0; i < q; ++i){
            ll ans = 1e18;
            for (int j = L[i]; j <= R[i]; ++j){
                ll otv = dpr[j][R[i]] + dpl[j][L[i]];
                ans = min(ans, otv);
            }
            res.pb(ans);
        }
        return res;
    }
    for (int i = 0; i < n; ++i)
        H[i] = 2 - H[i];
    ::H = H;
    build(1, 0, n - 1);
    vector < ll > res;
    for (int i = 0; i < q; ++i){
        auto kol = solve(1, 0, n - 1, L[i], R[i]);
        int len = R[i] - L[i] + 1;
        ll ans = kol.F + (len - kol.F) * 2;
        res.pb(ans);
    }
    return res;
}


#ifdef Estb_probitie
int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
int N = read_int();
  int Q = read_int();
  std::vector<int> H(N);
  for (int i = 0; i < N; ++i) {
    H[i] = read_int();
  }
  std::vector<int> L(Q), R(Q);
  for (int j = 0; j < Q; ++j) {
    L[j] = read_int();
    R[j] = read_int();
  }

  std::vector<long long> C = minimum_costs(H, L, R);
  for (size_t j = 0; j < C.size(); ++j) {
    printf("%lld\n", C[j]);
  }
  return 0;
}
#endif // Estb_probitie

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40