oj.uz

Submission #498175

# Submission time Handle Problem Language Result Execution time Memory
498175 2021-12-24T13:55:35 Z kingline Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 1394 ms 98336 KB 
/*#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")*/
#include <bits/stdc++.h>
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
//#define file(data) freopen(data".in", "r", stdin); freopen(data".out", "w", stdout);
#define pb push_back
//#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(data) data.begin() , data.end()
#define endl '\n'
//freopen("nenokku_easy.in", "r", stdin);
//freopen("nenokku_easy.out", "w", stdout);
#define int long long
#define pii pair < int, int >
#define pll pair < long long, long long >

using namespace std;

typedef long long ll;
const int N = 1e6 + 5;
const int M = 305;
const int mod = 1e9 + 7;

int n, m, a[N], L[N], t[4 * N], ans[N];
vector < pair < int, pii > > pos[N];

void update(int v, int l, int r, int pos, int val) {
    if(l == r) {
        t[v] = max(t[v], val);
        return;
    }
    int md = (l + r) / 2;
    if(pos <= md) update(v * 2, l, md, pos, val);
    else update(v * 2 + 1, md + 1, r, pos, val);
    t[v] = max(t[v * 2], t[v * 2 + 1]);
}

int get(int v, int l, int r, int tl, int tr) {
    if(tl <= l && r <= tr) {
        return t[v];
    }
    if(r < tl || tr < l) return -1;
    int md = (l + r) / 2;
    return max(get(v * 2, l, md, tl, tr),
               get(v * 2 + 1, md + 1, r, tl, tr));
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //file("pieaters");
    cin >> n >> m;
    stack < pii > st;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        while(st.size() && (st.top()).first <= a[i]) {
            st.pop();
        }
        if(st.size()) L[i] = (st.top()).second;
        st.push({a[i], i});
    }
    for(int i = 1; i <= m; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        pos[r].pb({l, {k, i}});
    }
    for(int i = 1; i <= n; i++) {
        sort(all(pos[i]));
    }
    for(int i = 1; i <= n; i++) {
        update(1, 1, n, L[i], a[i] + a[L[i]]);
        for(int j = 0; j < pos[i].size(); j++) {
            int lef = pos[i][j].first, kk = pos[i][j].second.first, query = pos[i][j].second.second;
            if(get(1, 1, n, lef, i) > kk) {
                ans[query] = 0;
            } else {
                ans[query] = 1;
            }
        }
    }
    for(int i = 1; i <= m; i++) {
        cout << ans[i] << endl;
    }
}

Compilation message

sortbooks.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main() {
      | ^~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:76:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(int j = 0; j < pos[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Output is correct
2 Correct 12 ms 23812 KB Output is correct
3 Correct 12 ms 23756 KB Output is correct
4 Correct 13 ms 23792 KB Output is correct
5 Correct 13 ms 23800 KB Output is correct
6 Correct 13 ms 23944 KB Output is correct
7 Correct 13 ms 23884 KB Output is correct
8 Correct 13 ms 23772 KB Output is correct
9 Correct 12 ms 23792 KB Output is correct
10 Correct 12 ms 23884 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Output is correct
2 Correct 12 ms 23812 KB Output is correct
3 Correct 12 ms 23756 KB Output is correct
4 Correct 13 ms 23792 KB Output is correct
5 Correct 13 ms 23800 KB Output is correct
6 Correct 13 ms 23944 KB Output is correct
7 Correct 13 ms 23884 KB Output is correct
8 Correct 13 ms 23772 KB Output is correct
9 Correct 12 ms 23792 KB Output is correct
10 Correct 12 ms 23884 KB Output is correct
11 Correct 15 ms 24012 KB Output is correct
12 Correct 15 ms 24220 KB Output is correct
13 Correct 16 ms 24208 KB Output is correct
14 Correct 17 ms 24260 KB Output is correct
15 Correct 18 ms 24336 KB Output is correct
16 Correct 17 ms 24272 KB Output is correct
17 Correct 15 ms 24116 KB Output is correct
18 Correct 17 ms 24140 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1343 ms 98264 KB Output is correct
2 Correct 1335 ms 98232 KB Output is correct
3 Correct 1394 ms 98188 KB Output is correct
4 Correct 1346 ms 98336 KB Output is correct
5 Incorrect 1230 ms 74000 KB Output isn't correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 31556 KB Output is correct
2 Correct 94 ms 32420 KB Output is correct
3 Incorrect 100 ms 29360 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Output is correct
2 Correct 12 ms 23812 KB Output is correct
3 Correct 12 ms 23756 KB Output is correct
4 Correct 13 ms 23792 KB Output is correct
5 Correct 13 ms 23800 KB Output is correct
6 Correct 13 ms 23944 KB Output is correct
7 Correct 13 ms 23884 KB Output is correct
8 Correct 13 ms 23772 KB Output is correct
9 Correct 12 ms 23792 KB Output is correct
10 Correct 12 ms 23884 KB Output is correct
11 Correct 15 ms 24012 KB Output is correct
12 Correct 15 ms 24220 KB Output is correct
13 Correct 16 ms 24208 KB Output is correct
14 Correct 17 ms 24260 KB Output is correct
15 Correct 18 ms 24336 KB Output is correct
16 Correct 17 ms 24272 KB Output is correct
17 Correct 15 ms 24116 KB Output is correct
18 Correct 17 ms 24140 KB Output is correct
19 Correct 236 ms 39984 KB Output is correct
20 Correct 235 ms 40080 KB Output is correct
21 Correct 182 ms 40512 KB Output is correct
22 Correct 185 ms 40484 KB Output is correct
23 Correct 186 ms 40516 KB Output is correct
24 Incorrect 164 ms 34976 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Output is correct
2 Correct 12 ms 23812 KB Output is correct
3 Correct 12 ms 23756 KB Output is correct
4 Correct 13 ms 23792 KB Output is correct
5 Correct 13 ms 23800 KB Output is correct
6 Correct 13 ms 23944 KB Output is correct
7 Correct 13 ms 23884 KB Output is correct
8 Correct 13 ms 23772 KB Output is correct
9 Correct 12 ms 23792 KB Output is correct
10 Correct 12 ms 23884 KB Output is correct
11 Correct 15 ms 24012 KB Output is correct
12 Correct 15 ms 24220 KB Output is correct
13 Correct 16 ms 24208 KB Output is correct
14 Correct 17 ms 24260 KB Output is correct
15 Correct 18 ms 24336 KB Output is correct
16 Correct 17 ms 24272 KB Output is correct
17 Correct 15 ms 24116 KB Output is correct
18 Correct 17 ms 24140 KB Output is correct
19 Correct 1343 ms 98264 KB Output is correct
20 Correct 1335 ms 98232 KB Output is correct
21 Correct 1394 ms 98188 KB Output is correct
22 Correct 1346 ms 98336 KB Output is correct
23 Incorrect 1230 ms 74000 KB Output isn't correct