Submission #963839

#	Time	Username	Problem	Language	Result	Execution time	Memory
963839		EJIC_B_KEDAX	Fire (JOI20_ho_t5)	C++17	6 / 100	331 ms	244612 KiB

ho_t5

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

#ifndef LOCAL
    // #pragma GCC optimize("O3")
    // #pragma GCC optimize("Ofast")
    // #pragma GCC optimize("unroll-loops")
    // #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
using ll = long long;
using ld = long double;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

mt19937 mt(123);

void solve();
void init();

int32_t main() {
#ifndef LOCAL
    cin.tie(nullptr)->sync_with_stdio(false);
#endif
    cout << fixed << setprecision(30);
    init();
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

void init() {}

const int N = 200200, K = 150;
int a[N];
ll sm[K][N];

void solve() {
    int n, q;
    cin >> n >> q;
    vector<pair<int, pair<int, int>>> st;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sm[0][i + 1] = a[i];
        if (st.empty() || a[i] >= st.back().x) {
            st.emplace_back(a[i], make_pair(i, 0));
        }
    }
    vector<pair<ll, int>> good(1, {0, -1});
    vector<pair<int, int>> bad;
    for (int i = 0; i < st.size(); i++) {
        if (i + 1 < st.size()) {
            st[i].y.y = st[i + 1].y.x - st[i].y.x;
        } else {
            st[i].y.y = n - st[i].y.x;
        }
        if (st[i].y.y < K) {
            good.emplace_back(1ll * st[i].y.y * st[i].x, st[i].y.x);
        } else {
            bad.push_back(st[i].y);
        }
    }
    for (int i = 1; i < good.size(); i++) {
        good[i].x += good[i - 1].x;
    }
    for (int l = 1; l < K; l++) {
        for (int i = 1; i <= n; i++) {
            sm[l][i] = max(sm[l - 1][i], sm[l - 1][i - 1]);
        }
    }
    for (int l = 0; l < K; l++) {
        for (int i = 1; i <= n; i++) {
            sm[l][i] += sm[l][i - 1];
        }
    }
    while (q--) {
        int t, l, r;
        cin >> t >> l >> r; l--; r--;
        if (t < K) {
            cout << sm[t][r + 1] - sm[t][l] << '\n';
            continue;
        }
        ll res = 0;
        int left = 0, right = good.size();
        while (right - left > 1) {
            int mid = (right + left) / 2;
            if (good[mid].y >= l) {
                right = mid;
            } else {
                left = mid;
            }
        }
        int lg = left;
        left = 0, right = good.size();
        while (right - left > 1) {
            int mid = (right + left) / 2;
            if (good[mid].y > r) {
                right = mid;
            } else {
                left = mid;
            }
        }
        int rg = left - 1;
        if (lg < rg) {
            res += good[rg].x - good[lg].x;
        }
        for (int i = 0; i < bad.size(); i++) {
            lg = bad[i].x;
            rg = bad[i].x + bad[i].y - 1;
            int mg = bad[i].x + t;
            if (mg >= rg) {
                lg = max(lg, l);
                rg = min(rg, r);
                if (lg <= rg) {
                    res += 1ll * (rg - lg + 1) * a[bad[i].x];
                }
            } else {
                int trg = rg;
                lg = max(lg, l);
                rg = min(mg, r);
                if (lg <= rg) {
                    res += 1ll * (rg - lg + 1) * a[bad[i].x];
                }
                lg = max(mg + 1, l);
                rg = min(trg, r);
                if (lg <= rg) {
                    res += sm[0][rg + 1] - sm[0][lg];
                }
            }
        }
        left = 0, right = good.size();
        while (right - left > 1) {
            int mid = (right + left) / 2;
            if (good[mid].y >= l) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (left > 0) {
            lg = good[left].y;
            rg = good[left].y + ((good[left].x - good[left - 1].x) / a[good[left].y]) - 1;
            lg = max(lg, l);
            rg = min(rg, r);
            if (lg <= rg) {
                res += 1ll * (rg - lg + 1) * a[good[left].y];
            }
        }
        int oldleft = left;
        left = 0, right = good.size();
        while (right - left > 1) {
            int mid = (right + left) / 2;
            if (good[mid].y > r) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (left > 0 && left != oldleft) {
            lg = good[left].y;
            rg = good[left].y + ((good[left].x - good[left - 1].x) / a[good[left].y]) - 1;
            lg = max(lg, l);
            rg = min(rg, r);
            if (lg <= rg) {
                res += 1ll * (rg - lg + 1) * a[good[left].y];
            }
        }
        cout << res << '\n';
    }
}

Compilation message (stderr)

ho_t5.cpp: In function 'void solve()':
ho_t5.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i = 0; i < st.size(); i++) {
      |                     ~~^~~~~~~~~~~
ho_t5.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         if (i + 1 < st.size()) {
      |             ~~~~~~^~~~~~~~~~~
ho_t5.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (int i = 1; i < good.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
ho_t5.cpp:113:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         for (int i = 0; i < bad.size(); i++) {
      |                         ~~^~~~~~~~~~~~

• Subtask 1: 0 / 1
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 6 / 6
• Subtask 5: 0 / 80