oj.uz

Submission #497602

# Submission time Handle Problem Language Result Execution time Memory
497602 2021-12-23T10:35:00 Z ergagan Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
30 / 100
 1026 ms 18388 KB 
//я так много думал, что опять попал
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define f first
#define s second
#define left(v) v + v
#define right(v) v + v + 1
#define ub upper_bound
#define lb lower_bound
#define pll pair<ll,ll>


//17 SEVENTEEN
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;

const long double Pi = acos(-1.0);
const ll dx[] = {0,0,1,-1};
const ll dy[] = {1,-1,0,0};
const ll N = (ll) 1e6 + 17;
const ll M = (ll) 5e3 + 69;
const ll inf = (ll) 1e14 + 3;
const ll mod = (ll) 1e9 + 7;
ll sq(ll x) { return x * x; }

ll zxc = 1, k, a[N], b[N], p[N];

void solve() {
    ll n, q;
    cin >> n >> q;
    for(ll i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(ll i = 1; i <= n; i++) {
        p[i] = p[i - 1];
        if(a[i] > a[i + 1]) p[i]++;
//        cout << p[i] << " ";
    }
    if(n <= M) {
        while(q--) {
            ll l, r, k;
            cin >> l >> r >> k;

            ll ok = 1;
            set<ll> st;
            st.insert(a[l]);
            for(ll i = l + 1; i <= r; i++) {
                if(*st.rbegin() > a[i] && *st.rbegin() + a[i] > k) { ok = 0; break; }
                st.insert(a[i]);
            }

            cout << ok << "\n";
        }
        return;
    }
    while(q--) {
        ll l, r, k;
        cin >> l >> r >> k;
        cout << !(p[r - 1] - p[l - 1]) << "\n";
    }
}

int main(/*Уверенно*/) {
ios_base::sync_with_stdio(0);
    cin.tie(0);
/*
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
*/
//    cin >> zxc;
    while(zxc--) {
        solve();
    }
  	return 0;
}
// さよならさ いかなくちゃ

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 9 ms 332 KB Output is correct
9 Correct 6 ms 348 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 9 ms 332 KB Output is correct
9 Correct 6 ms 348 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 5 ms 464 KB Output is correct
12 Correct 7 ms 588 KB Output is correct
13 Correct 6 ms 536 KB Output is correct
14 Correct 11 ms 736 KB Output is correct
15 Correct 7 ms 588 KB Output is correct
16 Correct 1026 ms 860 KB Output is correct
17 Correct 969 ms 620 KB Output is correct
18 Correct 63 ms 468 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 17904 KB Output is correct
2 Correct 531 ms 18180 KB Output is correct
3 Correct 492 ms 18152 KB Output is correct
4 Correct 483 ms 18100 KB Output is correct
5 Correct 488 ms 18388 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 9 ms 332 KB Output is correct
9 Correct 6 ms 348 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 5 ms 464 KB Output is correct
12 Correct 7 ms 588 KB Output is correct
13 Correct 6 ms 536 KB Output is correct
14 Correct 11 ms 736 KB Output is correct
15 Correct 7 ms 588 KB Output is correct
16 Correct 1026 ms 860 KB Output is correct
17 Correct 969 ms 620 KB Output is correct
18 Correct 63 ms 468 KB Output is correct
19 Incorrect 90 ms 3836 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 9 ms 332 KB Output is correct
9 Correct 6 ms 348 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 5 ms 464 KB Output is correct
12 Correct 7 ms 588 KB Output is correct
13 Correct 6 ms 536 KB Output is correct
14 Correct 11 ms 736 KB Output is correct
15 Correct 7 ms 588 KB Output is correct
16 Correct 1026 ms 860 KB Output is correct
17 Correct 969 ms 620 KB Output is correct
18 Correct 63 ms 468 KB Output is correct
19 Correct 461 ms 17904 KB Output is correct
20 Correct 531 ms 18180 KB Output is correct
21 Correct 492 ms 18152 KB Output is correct
22 Correct 483 ms 18100 KB Output is correct
23 Correct 488 ms 18388 KB Output is correct
24 Incorrect 37 ms 2136 KB Output isn't correct
25 Halted 0 ms 0 KB -