oj.uz

Submission #242469

# Submission time Handle Problem Language Result Execution time Memory
242469 2020-06-27T18:54:59 Z SorahISA Fire (JOI20_ho_t5) C++17
6 / 100
 130 ms 15352 KB 
// #pragma GCC target("avx2")
#pragma GCC optimize("O3", "unroll-loops")

// #include <bits/extc++.h>
// using namespace __gnu_pbds;

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
// template <typename T>
// using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using pii = pair<int, int>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using Prior = priority_queue<T>;

#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back

#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define RANDOM() random_device __rd; \
                 mt19937 __gen = mt19937(__rd()); \
                 uniform_int_distribution<int> __dis(1, 1E8); \
                 auto rnd = bind(__dis, __gen)

const int INF = 1E18;
const int mod = 1E9 + 7;

int32_t main() {
    fastIO();
    
    int n, q;
    cin >> n >> q;
    
    int v[n];
    for (int i = 0; i < n; ++i) cin >> v[i];
    
    auto Query_Max = [&](int L, int R) -> int {
        return *max_element(v + L, v + R + 1);
    };
    
    int t[q], l[q], r[q];
    for (int i = 0; i < q; ++i) cin >> t[i] >> l[i] >> r[i], --l[i], --r[i];
    
    int fl_sub2 = 1, fl_sub3 = 1, fl_sub4 = 1;
    for (int i = 0; i < q; ++i) {
        if (t[i] != t[0]) fl_sub2 = 0;
        if (l[i] != r[i]) fl_sub3 = 0;
    }
    for (int i = 0; i < n; ++i) {
        if (v[i] > 2) fl_sub4 = 0;
    }
    
    if (fl_sub2) {
        deque<pii> deq; /// (val, time)
        for (int i = 0; i < n; ++i) {
            while (!deq.empty() and deq.back().X <= v[i]) deq.pop_back();
            deq.push_back({v[i], i});
            if (deq.front().Y == i - t[0] - 1) deq.pop_front();
            v[i] = deq.front().X;
        }
        partial_sum(v, v + n, v);
        for (int i = 0; i < q; ++i) {
            cout << v[r[i]] - (l[i] == 0 ? 0LL : v[l[i] - 1]) << "\n";
        }
        return 0;
    }
    
    for (int i = 0; i < q; ++i) {
        int l, r, t, ans = 0;
        while (l <= r) ans += Query_Max(max(0LL, l-t), l), ++l;
        cout << ans << "\n";
    }
    
    return 0;
}

Compilation message

ho_t5.cpp: In function 'int32_t main()':
ho_t5.cpp:51:22: warning: variable 'fl_sub3' set but not used [-Wunused-but-set-variable]
     int fl_sub2 = 1, fl_sub3 = 1, fl_sub4 = 1;
                      ^~~~~~~
ho_t5.cpp:51:35: warning: variable 'fl_sub4' set but not used [-Wunused-but-set-variable]
     int fl_sub2 = 1, fl_sub3 = 1, fl_sub4 = 1;
                                   ^~~~~~~
ho_t5.cpp:76:16: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
         int l, r, t, ans = 0;
                ^
ho_t5.cpp:76:19: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
         int l, r, t, ans = 0;
                   ^
ho_t5.cpp:76:13: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
         int l, r, t, ans = 0;
             ^

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 128 ms 13092 KB Output is correct
3 Correct 119 ms 14968 KB Output is correct
4 Correct 130 ms 15096 KB Output is correct
5 Correct 126 ms 15096 KB Output is correct
6 Correct 121 ms 14712 KB Output is correct
7 Correct 124 ms 15224 KB Output is correct
8 Correct 123 ms 14968 KB Output is correct
9 Correct 122 ms 15096 KB Output is correct
10 Correct 120 ms 14968 KB Output is correct
11 Correct 129 ms 15352 KB Output is correct
12 Correct 119 ms 14840 KB Output is correct
13 Correct 126 ms 14840 KB Output is correct
14 Correct 126 ms 14712 KB Output is correct
15 Correct 124 ms 14840 KB Output is correct
16 Correct 128 ms 14840 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 112 ms 10232 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 10232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -