oj.uz

Submission #497397

# Submission time Handle Problem Language Result Execution time Memory
497397 2021-12-23T04:27:23 Z armashka Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 3000 ms 117904 KB 
#include <bits/stdc++.h>
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define fast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define all(v) v.begin(),v.end()
#define pb push_back
#define sz size()
#define ft first
#define sd second
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef unsigned long long ull;
 
const int N = 1e6 + 5;
const ll M = 1e8;
const ll inf = 1e18;
const ll mod = 1e9;
const double Pi = acos(-1); 
 
ll binpow(ll x, ll ti) { ll res = 1;while (ti){if(ti & 1)res *= x;x *= x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll binmul(ll x, ll ti) { ll res = 0;while (ti){if(ti & 1)res += x;x += x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll nok(ll a, ll b) { return (a*b)/__gcd(abs(a),abs(b)) * (a*b > 0 ? 1 : -1); }
bool odd(ll n) { return (n % 2 == 1); }
bool even(ll n) { return (n % 2 == 0); }            

ll n, q, a[5005], dp[5005][5005];

const void solve(/*Armashka*/) {
	cin >> n >> q;
	for (int i = 1; i <= n; ++ i) cin >> a[i];
	for (int l = 1; l <= n; ++ l) {
		set <ll> st;
		st.insert(a[l]);
		for (int r = l + 1; r <= n; ++ r) {
			dp[l][r] = dp[l][r - 1];
			if (*st.rbegin() > a[r]) dp[l][r] = max(dp[l][r], *st.rbegin() + a[r]);
			st.insert(a[r]);		
		}
	}	
	while (q --) {
		ll l, r, k;
		cin >> l >> r >> k;
		if (dp[l][r] <= k) cout << "1\n";
		else cout << "0\n";
	}
}
            
signed main() {
    fast;
    //freopen("divide.in", "r", stdin);
    //freopen("divide.out", "w", stdout);
    int tt = 1;
    //cin >> tt;
    while (tt --) {                                                
        solve();
    }
}
 
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 2 ms 972 KB Output is correct
4 Correct 1 ms 580 KB Output is correct
5 Correct 2 ms 1228 KB Output is correct
6 Correct 15 ms 3264 KB Output is correct
7 Correct 13 ms 3276 KB Output is correct
8 Correct 12 ms 3292 KB Output is correct
9 Correct 3 ms 1612 KB Output is correct
10 Correct 3 ms 3276 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 2 ms 972 KB Output is correct
4 Correct 1 ms 580 KB Output is correct
5 Correct 2 ms 1228 KB Output is correct
6 Correct 15 ms 3264 KB Output is correct
7 Correct 13 ms 3276 KB Output is correct
8 Correct 12 ms 3292 KB Output is correct
9 Correct 3 ms 1612 KB Output is correct
10 Correct 3 ms 3276 KB Output is correct
11 Correct 119 ms 14320 KB Output is correct
12 Correct 1422 ms 112340 KB Output is correct
13 Correct 1387 ms 112016 KB Output is correct
14 Correct 1504 ms 117592 KB Output is correct
15 Correct 1497 ms 117904 KB Output is correct
16 Correct 1286 ms 117696 KB Output is correct
17 Correct 811 ms 82864 KB Output is correct
18 Correct 134 ms 117448 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 2 ms 972 KB Output is correct
4 Correct 1 ms 580 KB Output is correct
5 Correct 2 ms 1228 KB Output is correct
6 Correct 15 ms 3264 KB Output is correct
7 Correct 13 ms 3276 KB Output is correct
8 Correct 12 ms 3292 KB Output is correct
9 Correct 3 ms 1612 KB Output is correct
10 Correct 3 ms 3276 KB Output is correct
11 Correct 119 ms 14320 KB Output is correct
12 Correct 1422 ms 112340 KB Output is correct
13 Correct 1387 ms 112016 KB Output is correct
14 Correct 1504 ms 117592 KB Output is correct
15 Correct 1497 ms 117904 KB Output is correct
16 Correct 1286 ms 117696 KB Output is correct
17 Correct 811 ms 82864 KB Output is correct
18 Correct 134 ms 117448 KB Output is correct
19 Execution timed out 3043 ms 332 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 2 ms 972 KB Output is correct
4 Correct 1 ms 580 KB Output is correct
5 Correct 2 ms 1228 KB Output is correct
6 Correct 15 ms 3264 KB Output is correct
7 Correct 13 ms 3276 KB Output is correct
8 Correct 12 ms 3292 KB Output is correct
9 Correct 3 ms 1612 KB Output is correct
10 Correct 3 ms 3276 KB Output is correct
11 Correct 119 ms 14320 KB Output is correct
12 Correct 1422 ms 112340 KB Output is correct
13 Correct 1387 ms 112016 KB Output is correct
14 Correct 1504 ms 117592 KB Output is correct
15 Correct 1497 ms 117904 KB Output is correct
16 Correct 1286 ms 117696 KB Output is correct
17 Correct 811 ms 82864 KB Output is correct
18 Correct 134 ms 117448 KB Output is correct
19 Runtime error 4 ms 460 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -