oj.uz

Submission #963817

# Submission time Handle Problem Language Result Execution time Memory
963817 2024-04-15T18:30:20 Z EJIC_B_KEDAX Fire (JOI20_ho_t5) C++17
1 / 100
 199 ms 262144 KB 
#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 = 400;
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 = right - 1;
        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 = st.size();
        while (right - left > 1) {
            int mid = (right + left) / 2;
            if (st[mid].y.x >= l) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (st[left].y.y < K) {
            lg = st[left].y.x;
            rg = st[left].y.x + st[left].y.y - 1;
            lg = max(lg, l);
            rg = min(rg, r);
            if (lg <= rg) {
                res += 1ll * (rg - lg + 1) * st[left].x;
            }
        }
        left = 0, right = st.size();
        while (right - left > 1) {
            int mid = (right + left) / 2;
            if (st[mid].y.x > r) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (st[left].y.y < K) {
            lg = st[left].y.x;
            rg = st[left].y.x + st[left].y.y - 1;
            lg = max(lg, l);
            rg = min(rg, r);
            if (lg <= rg) {
                res += 1ll * (rg - lg + 1) * st[left].x;
            }
        }
        cout << res << '\n';
    }
}

Compilation message

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
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 42072 KB Output is correct
2 Correct 7 ms 42588 KB Output is correct
3 Correct 6 ms 42512 KB Output is correct
4 Correct 6 ms 42588 KB Output is correct
5 Correct 6 ms 42496 KB Output is correct
6 Correct 6 ms 42588 KB Output is correct
7 Correct 6 ms 42456 KB Output is correct
8 Correct 6 ms 42448 KB Output is correct
9 Correct 6 ms 44632 KB Output is correct
10 Correct 6 ms 42588 KB Output is correct
11 Correct 6 ms 42588 KB Output is correct
12 Correct 6 ms 42584 KB Output is correct
13 Correct 6 ms 42504 KB Output is correct
14 Correct 6 ms 42588 KB Output is correct
15 Correct 6 ms 42452 KB Output is correct
16 Correct 6 ms 42588 KB Output is correct
17 Correct 6 ms 42588 KB Output is correct
18 Correct 6 ms 42588 KB Output is correct
19 Correct 6 ms 42588 KB Output is correct
20 Correct 6 ms 42588 KB Output is correct
21 Correct 6 ms 42588 KB Output is correct
22 Correct 6 ms 42584 KB Output is correct
23 Correct 6 ms 42588 KB Output is correct
24 Correct 6 ms 42584 KB Output is correct
25 Correct 6 ms 44888 KB Output is correct
26 Correct 7 ms 42588 KB Output is correct
27 Correct 6 ms 42584 KB Output is correct
28 Correct 6 ms 42584 KB Output is correct
29 Correct 6 ms 42588 KB Output is correct
30 Correct 6 ms 42588 KB Output is correct
31 Correct 6 ms 42656 KB Output is correct
32 Correct 7 ms 44636 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 42072 KB Output is correct
2 Runtime error 136 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 42072 KB Output is correct
2 Runtime error 199 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 107 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 42072 KB Output is correct
2 Correct 7 ms 42588 KB Output is correct
3 Correct 6 ms 42512 KB Output is correct
4 Correct 6 ms 42588 KB Output is correct
5 Correct 6 ms 42496 KB Output is correct
6 Correct 6 ms 42588 KB Output is correct
7 Correct 6 ms 42456 KB Output is correct
8 Correct 6 ms 42448 KB Output is correct
9 Correct 6 ms 44632 KB Output is correct
10 Correct 6 ms 42588 KB Output is correct
11 Correct 6 ms 42588 KB Output is correct
12 Correct 6 ms 42584 KB Output is correct
13 Correct 6 ms 42504 KB Output is correct
14 Correct 6 ms 42588 KB Output is correct
15 Correct 6 ms 42452 KB Output is correct
16 Correct 6 ms 42588 KB Output is correct
17 Correct 6 ms 42588 KB Output is correct
18 Correct 6 ms 42588 KB Output is correct
19 Correct 6 ms 42588 KB Output is correct
20 Correct 6 ms 42588 KB Output is correct
21 Correct 6 ms 42588 KB Output is correct
22 Correct 6 ms 42584 KB Output is correct
23 Correct 6 ms 42588 KB Output is correct
24 Correct 6 ms 42584 KB Output is correct
25 Correct 6 ms 44888 KB Output is correct
26 Correct 7 ms 42588 KB Output is correct
27 Correct 6 ms 42584 KB Output is correct
28 Correct 6 ms 42584 KB Output is correct
29 Correct 6 ms 42588 KB Output is correct
30 Correct 6 ms 42588 KB Output is correct
31 Correct 6 ms 42656 KB Output is correct
32 Correct 7 ms 44636 KB Output is correct
33 Runtime error 136 ms 262144 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -