oj.uz

답안 #497605

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
497605 2021-12-23T10:38:03 Z armashka Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
34 / 100
 1660 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, pr[N];
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]);
}

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 = 2; i <= n; ++ i) pr[i] = pr[i - 1] + (a[i] < a[i - 1]);
	for (int i = 1; i <= m; ++ i) {
		ll l, r, k;
		cin >> l >> r >> k;
		if (pr[r] - pr[l] > 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

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 13 ms 23820 KB Output is correct
3 Correct 20 ms 24492 KB Output is correct
4 Correct 14 ms 24012 KB Output is correct
5 Correct 15 ms 24796 KB Output is correct
6 Correct 26 ms 26956 KB Output is correct
7 Correct 26 ms 26860 KB Output is correct
8 Correct 24 ms 26948 KB Output is correct
9 Correct 16 ms 25208 KB Output is correct
10 Correct 16 ms 26888 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 13 ms 23820 KB Output is correct
3 Correct 20 ms 24492 KB Output is correct
4 Correct 14 ms 24012 KB Output is correct
5 Correct 15 ms 24796 KB Output is correct
6 Correct 26 ms 26956 KB Output is correct
7 Correct 26 ms 26860 KB Output is correct
8 Correct 24 ms 26948 KB Output is correct
9 Correct 16 ms 25208 KB Output is correct
10 Correct 16 ms 26888 KB Output is correct
11 Correct 134 ms 38196 KB Output is correct
12 Correct 1470 ms 136836 KB Output is correct
13 Correct 1443 ms 136456 KB Output is correct
14 Correct 1556 ms 142124 KB Output is correct
15 Correct 1660 ms 142224 KB Output is correct
16 Correct 1405 ms 142300 KB Output is correct
17 Correct 849 ms 107252 KB Output is correct
18 Correct 158 ms 142012 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 183 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 634 ms 53064 KB Output is correct
2 Correct 509 ms 53292 KB Output is correct
3 Correct 580 ms 53280 KB Output is correct
4 Correct 464 ms 53176 KB Output is correct
5 Correct 374 ms 53136 KB Output is correct
6 Correct 669 ms 52464 KB Output is correct
7 Correct 740 ms 52440 KB Output is correct
8 Correct 198 ms 52832 KB Output is correct
9 Correct 47 ms 27288 KB Output is correct
10 Correct 200 ms 52812 KB Output is correct

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 13 ms 23820 KB Output is correct
3 Correct 20 ms 24492 KB Output is correct
4 Correct 14 ms 24012 KB Output is correct
5 Correct 15 ms 24796 KB Output is correct
6 Correct 26 ms 26956 KB Output is correct
7 Correct 26 ms 26860 KB Output is correct
8 Correct 24 ms 26948 KB Output is correct
9 Correct 16 ms 25208 KB Output is correct
10 Correct 16 ms 26888 KB Output is correct
11 Correct 134 ms 38196 KB Output is correct
12 Correct 1470 ms 136836 KB Output is correct
13 Correct 1443 ms 136456 KB Output is correct
14 Correct 1556 ms 142124 KB Output is correct
15 Correct 1660 ms 142224 KB Output is correct
16 Correct 1405 ms 142300 KB Output is correct
17 Correct 849 ms 107252 KB Output is correct
18 Correct 158 ms 142012 KB Output is correct
19 Incorrect 122 ms 75928 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 13 ms 23820 KB Output is correct
3 Correct 20 ms 24492 KB Output is correct
4 Correct 14 ms 24012 KB Output is correct
5 Correct 15 ms 24796 KB Output is correct
6 Correct 26 ms 26956 KB Output is correct
7 Correct 26 ms 26860 KB Output is correct
8 Correct 24 ms 26948 KB Output is correct
9 Correct 16 ms 25208 KB Output is correct
10 Correct 16 ms 26888 KB Output is correct
11 Correct 134 ms 38196 KB Output is correct
12 Correct 1470 ms 136836 KB Output is correct
13 Correct 1443 ms 136456 KB Output is correct
14 Correct 1556 ms 142124 KB Output is correct
15 Correct 1660 ms 142224 KB Output is correct
16 Correct 1405 ms 142300 KB Output is correct
17 Correct 849 ms 107252 KB Output is correct
18 Correct 158 ms 142012 KB Output is correct
19 Runtime error 183 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -