oj.uz

답안 #963839

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
963839 2024-04-15T19:10:26 Z EJIC_B_KEDAX Fire (JOI20_ho_t5) C++17
6 / 100
 331 ms 244612 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 = 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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 83040 KB Output is correct
2 Correct 12 ms 83292 KB Output is correct
3 Correct 10 ms 81244 KB Output is correct
4 Correct 9 ms 77148 KB Output is correct
5 Correct 9 ms 79196 KB Output is correct
6 Correct 9 ms 79196 KB Output is correct
7 Incorrect 9 ms 79196 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 83040 KB Output is correct
2 Correct 232 ms 236996 KB Output is correct
3 Correct 248 ms 236856 KB Output is correct
4 Incorrect 227 ms 237316 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 83040 KB Output is correct
2 Incorrect 228 ms 236740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 313 ms 237888 KB Output is correct
2 Correct 314 ms 240580 KB Output is correct
3 Correct 300 ms 244612 KB Output is correct
4 Correct 320 ms 237968 KB Output is correct
5 Correct 302 ms 239136 KB Output is correct
6 Correct 304 ms 241052 KB Output is correct
7 Correct 320 ms 244356 KB Output is correct
8 Correct 304 ms 241984 KB Output is correct
9 Correct 312 ms 239028 KB Output is correct
10 Correct 326 ms 242620 KB Output is correct
11 Correct 331 ms 239668 KB Output is correct
12 Correct 329 ms 240740 KB Output is correct
13 Correct 322 ms 239868 KB Output is correct
14 Correct 307 ms 240344 KB Output is correct

Subtask #5
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 83040 KB Output is correct
2 Correct 12 ms 83292 KB Output is correct
3 Correct 10 ms 81244 KB Output is correct
4 Correct 9 ms 77148 KB Output is correct
5 Correct 9 ms 79196 KB Output is correct
6 Correct 9 ms 79196 KB Output is correct
7 Incorrect 9 ms 79196 KB Output isn't correct
8 Halted 0 ms 0 KB -