oj.uz

Submission #497598

# Submission time Handle Problem Language Result Execution time Memory
497598 2021-12-23T10:32:35 Z armashka Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
34 / 100
 1770 ms 262148 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, m, a[N], q[N], mx[N][30], lg[N], ans[N], dp[5005][5005], maaax, t[N * 4];
vector <pair<pll, ll>> pos[N]; 

ll get(ll l, ll r) {
	ll len = (r - l + 1);
	ll k = lg[len];
	return max(mx[l][k], mx[r - (1 << k) + 1][k]);
}

void upd(ll pos, ll val, ll v = 1, ll tl = 1, ll tr = n) {
	if (tl == tr) {
		t[v] = val;
		return;
	}
	ll tm = (tl + tr) / 2;
	if (pos <= tm) upd(pos, val, v + v, tl, tm);
	else upd(pos, val, v + v + 1, tm + 1, tr);
	t[v] = t[v + v] + t[v + v + 1];
}

ll get_tree(ll l, ll r, ll v = 1, ll tl = 1, ll tr = n) {
	if (r < tl || tr < l) return 0;
	if (l <= tl && tr <= r) return t[v];
	ll tm = (tl + tr) / 2;
	return get_tree(l, r, v + v, tl, tm) + get_tree(l, r, v + v + 1, tm + 1, tr); 
}

const void solve(/*Armashka*/) {
	cin >> n >> m;
	for (int i = 2; i <= n; ++ i) lg[i] = lg[i / 2] + 1;
	for (int i = 1; i <= n; ++ i) {
		cin >> a[i];
		maaax = max(maaax, a[i]);
		mx[i][0] = a[i];                                 
	}
	if (n <= 5000) {
		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 (m --) {
			ll l, r, k;
			cin >> l >> r >> k;
			if (dp[l][r] <= k) cout << "1\n";
			else cout << "0\n";
		}
		return;
	}
	if (maaax <= 1000) {
		for (int i = 1; i <= 25; ++ i) {
			for (int j = 1; j + (1 << (i - 1)) - 1 <= n; ++ j) {
				mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1))][i - 1]); 
			}
		}
		for (int i = 1; i <= m; ++ i) {
			ll l, r, k;
			cin >> l >> r >> k;
			pos[r].pb({{l, k}, i});
		}	
		for (int i = 1; i <= n; ++ i) {
			q[a[i]] = i;
			while (pos[i].sz) {
				ll l = pos[i].back().ft.ft, k = pos[i].back().ft.sd, id = pos[i].back().sd;
				pos[i].pop_back();
				ll res = 0;
				for (int j = 1; j <= 1000; ++ j) {
					if (q[j] <= l) continue;
					ll cur = get(l, q[j]);	
					if (cur > j) res = max(res, cur + j);			
				}
				if (res <= k) ans[id] = 1;						
			}
		}	
		for (int i = 1; i <= m; ++ i) cout << ans[i] << "\n";
		return;
	}
	for (int i = 1; i < n; ++ i) upd(i, (a[i] > a[i + 1]));
	for (int i = 1; i <= m; ++ i) {
		ll ll, rr, k;
		cin >> ll >> rr >> k;
		if (get_tree(ll + 1, rr) > 0) cout << "0\n";
		else cout << "1\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 13 ms 23756 KB Output is correct
2 Correct 13 ms 23752 KB Output is correct
3 Correct 15 ms 24516 KB Output is correct
4 Correct 14 ms 24064 KB Output is correct
5 Correct 15 ms 24704 KB Output is correct
6 Correct 35 ms 26948 KB Output is correct
7 Correct 26 ms 26972 KB Output is correct
8 Correct 27 ms 26908 KB Output is correct
9 Correct 27 ms 25200 KB Output is correct
10 Correct 20 ms 26976 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 13 ms 23752 KB Output is correct
3 Correct 15 ms 24516 KB Output is correct
4 Correct 14 ms 24064 KB Output is correct
5 Correct 15 ms 24704 KB Output is correct
6 Correct 35 ms 26948 KB Output is correct
7 Correct 26 ms 26972 KB Output is correct
8 Correct 27 ms 26908 KB Output is correct
9 Correct 27 ms 25200 KB Output is correct
10 Correct 20 ms 26976 KB Output is correct
11 Correct 130 ms 38148 KB Output is correct
12 Correct 1614 ms 136852 KB Output is correct
13 Correct 1526 ms 136580 KB Output is correct
14 Correct 1612 ms 142288 KB Output is correct
15 Correct 1770 ms 142408 KB Output is correct
16 Correct 1477 ms 142404 KB Output is correct
17 Correct 940 ms 107308 KB Output is correct
18 Correct 153 ms 142080 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 220 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 53076 KB Output is correct
2 Correct 537 ms 54320 KB Output is correct
3 Correct 507 ms 54536 KB Output is correct
4 Correct 438 ms 55068 KB Output is correct
5 Correct 358 ms 55132 KB Output is correct
6 Correct 762 ms 54252 KB Output is correct
7 Correct 774 ms 54216 KB Output is correct
8 Correct 188 ms 54408 KB Output is correct
9 Correct 48 ms 28552 KB Output is correct
10 Correct 186 ms 54408 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 13 ms 23752 KB Output is correct
3 Correct 15 ms 24516 KB Output is correct
4 Correct 14 ms 24064 KB Output is correct
5 Correct 15 ms 24704 KB Output is correct
6 Correct 35 ms 26948 KB Output is correct
7 Correct 26 ms 26972 KB Output is correct
8 Correct 27 ms 26908 KB Output is correct
9 Correct 27 ms 25200 KB Output is correct
10 Correct 20 ms 26976 KB Output is correct
11 Correct 130 ms 38148 KB Output is correct
12 Correct 1614 ms 136852 KB Output is correct
13 Correct 1526 ms 136580 KB Output is correct
14 Correct 1612 ms 142288 KB Output is correct
15 Correct 1770 ms 142408 KB Output is correct
16 Correct 1477 ms 142404 KB Output is correct
17 Correct 940 ms 107308 KB Output is correct
18 Correct 153 ms 142080 KB Output is correct
19 Incorrect 197 ms 79328 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 13 ms 23752 KB Output is correct
3 Correct 15 ms 24516 KB Output is correct
4 Correct 14 ms 24064 KB Output is correct
5 Correct 15 ms 24704 KB Output is correct
6 Correct 35 ms 26948 KB Output is correct
7 Correct 26 ms 26972 KB Output is correct
8 Correct 27 ms 26908 KB Output is correct
9 Correct 27 ms 25200 KB Output is correct
10 Correct 20 ms 26976 KB Output is correct
11 Correct 130 ms 38148 KB Output is correct
12 Correct 1614 ms 136852 KB Output is correct
13 Correct 1526 ms 136580 KB Output is correct
14 Correct 1612 ms 142288 KB Output is correct
15 Correct 1770 ms 142408 KB Output is correct
16 Correct 1477 ms 142404 KB Output is correct
17 Correct 940 ms 107308 KB Output is correct
18 Correct 153 ms 142080 KB Output is correct
19 Runtime error 220 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -