oj.uz

Submission #242472

# Submission time Handle Problem Language Result Execution time Memory
242472 2020-06-27T19:00:30 Z SorahISA Fire (JOI20_ho_t5) C++17
7 / 100
 1000 ms 33232 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;
    }
    
    if (fl_sub3) {
        int st[18][n];
        for (int i = 0; i < n; ++i) st[0][i] = v[i];
        for (int lay = 1; lay < 18; ++lay) {
            for (int i = 0; i+(1<<lay-1) < n; ++i) {
                st[lay][i] = max(st[lay - 1][i], st[lay - 1][i + (1 << lay-1)]);
            }
        }
        
        for (int i = 0; i < q; ++i) {
            int _l = max(0LL, l[i] - t[i]), _r = l[i];
            
        }
    }
    
    for (int i = 0; i < q; ++i) {
        int ans = 0;
        while (l[i] <= r[i]) ans += Query_Max(max(0LL, l[i] - t[i]), l[i]), ++l[i];
        cout << ans << "\n";
    }
    
    return 0;
}

Compilation message

ho_t5.cpp: In function 'int32_t main()':
ho_t5.cpp:79:38: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
             for (int i = 0; i+(1<<lay-1) < n; ++i) {
                                   ~~~^~
ho_t5.cpp:80:75: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
                 st[lay][i] = max(st[lay - 1][i], st[lay - 1][i + (1 << lay-1)]);
                                                                        ~~~^~
ho_t5.cpp:85:17: warning: unused variable '_l' [-Wunused-variable]
             int _l = max(0LL, l[i] - t[i]), _r = l[i];
                 ^~
ho_t5.cpp:85:45: warning: unused variable '_r' [-Wunused-variable]
             int _l = max(0LL, l[i] - t[i]), _r = l[i];
                                             ^~
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;
                                   ^~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 6 ms 304 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 6 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 6 ms 384 KB Output is correct
17 Correct 6 ms 384 KB Output is correct
18 Correct 6 ms 384 KB Output is correct
19 Correct 6 ms 384 KB Output is correct
20 Correct 6 ms 384 KB Output is correct
21 Correct 6 ms 384 KB Output is correct
22 Correct 6 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 5 ms 384 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 127 ms 9336 KB Output is correct
3 Correct 131 ms 9336 KB Output is correct
4 Correct 119 ms 9464 KB Output is correct
5 Correct 121 ms 9208 KB Output is correct
6 Correct 168 ms 9336 KB Output is correct
7 Correct 119 ms 9544 KB Output is correct
8 Correct 125 ms 9464 KB Output is correct
9 Correct 135 ms 9592 KB Output is correct
10 Correct 128 ms 9336 KB Output is correct
11 Correct 119 ms 9464 KB Output is correct
12 Correct 121 ms 9208 KB Output is correct
13 Correct 124 ms 9336 KB Output is correct
14 Correct 115 ms 9208 KB Output is correct
15 Correct 119 ms 9336 KB Output is correct
16 Correct 126 ms 9208 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 Execution timed out 1096 ms 33232 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 6392 KB Time limit exceeded
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 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 6 ms 304 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 6 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 6 ms 384 KB Output is correct
17 Correct 6 ms 384 KB Output is correct
18 Correct 6 ms 384 KB Output is correct
19 Correct 6 ms 384 KB Output is correct
20 Correct 6 ms 384 KB Output is correct
21 Correct 6 ms 384 KB Output is correct
22 Correct 6 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 5 ms 384 KB Output is correct
33 Execution timed out 1079 ms 10104 KB Time limit exceeded
34 Halted 0 ms 0 KB -