oj.uz

Submission #890022

# Submission time Handle Problem Language Result Execution time Memory
890022 2023-12-20T10:57:43 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
30 / 100
 3000 ms 234068 KB 
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
//#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define len(x) (int)x.size()
#define ull unsigned long long
#define F first
#define S second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
// #define int long long
#define ld long double
#define pii pair<int,int>
#define mii map<int,int>

using namespace std;
using namespace __gnu_pbds;
using ll = long long;

const int N = 1e6 + 5;

int n,q,a[N],c[N],lg[N],sp[21][N],s[21][N];
vector <int> p[1005];

signed main(){
	// freopen("txt.in", "r", stdin);
	// freopen("txt.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	lg[2] = 1;
	for (int i=1;i<=n;i++){
		if (!lg[i]) lg[i] = lg[i-1];
		if (i*2<=n) lg[i*2] = lg[i] + 1;
	}
	int mn = 1e9,mx = 0;
	for (int i=1;i<=n;i++){
		cin >> a[i];
		s[0][i] = a[i];
		mn = min(mn, a[i]);
		mx = max(mx, a[i]);
	}
	if (mx <= 1000){
		for (int i=1;i<=n;i++){
			p[a[i]].pb(i);
		}
	}
	for (int i=1;i<n;i++){
		if (a[i]<=a[i+1]) {
			c[i] = 1;
		}
		sp[0][i] = c[i];
	}
	for (int i=1;i<=20;i++){
		for (int j=1;j+(1<<i)-1<=n;j++){
			sp[i][j] = min(sp[i-1][j], sp[i-1][j+(1<<(i-1))]);
		} 
	}
	for (int i=1;i<=20;i++){
		for (int j=1;j+(1<<i)-1<=n;j++){
			s[i][j] = max(s[i-1][j], s[i-1][j+(1<<(i-1))]);
		} 
	}
	while(q--){
		int ll,rr,k;
		cin >> ll >> rr >> k;
		if (ll==rr){
			cout << 1 << '\n';
			continue;
		}
		int l = ll;
		int r = rr-1;
		while(l<=r){
			int md = (l + r) / 2;
			int x = lg[(rr-1)-md+1];
			int cur = min(sp[x][md], sp[x][(rr-1)-(1<<x)+1]);
			if (cur==1){
				r = md - 1;
			}
			else{
				l = md + 1;
			}
		}
		if (ll==l){
			cout << 1 << '\n';
			continue;
		}
		if (k < mn){
			cout << 0 << '\n';
			continue;
		}
		if (n<=5000){
			int res = 0;
			for (int i=ll+1;i<=rr;i++){
				int x = lg[i-ll+1];
				int cur = max(s[x][ll], s[x][i-(1<<x)+1]);
				if (cur > a[i]){
					res = max(res, cur + a[i]);
				}
			}
			if (res<=k){
				cout << 1 << '\n';
			}
			else{
				cout << 0 << '\n';
			}
		}
		else {
			int res = 0;
			for (int i=1;i<=mx;i++){
				l = 0;
				r = len(p[i]) - 1;
				while(l<=r){
					int md = (l + r) / 2;
					if (p[i][md] < ll){
						l = md + 1;
					}
					else{
						r = md - 1;
					}
				}
				if (l<len(p[i]) && p[i][l]>=ll && p[i][l]<=rr){
					int x = lg[p[i][l] - ll + 1];
					int cur = max(s[x][ll], s[x][p[i][l]-(1<<x)+1]);
					if (cur > i) res = max(res, cur + i);
				}
			}
			if (res <= k){
				cout << 1 << '\n';
			}
			else{
				cout << 0 << '\n';
			}
		}
	}
}

//order_of_key(k): Number of items strictly smaller than k .
//find_by_order(k): K-th element in a set (counting from zero).

//sum of squares n*(n+1)*(2n+1)/6
//sum of cubes [n*(n+1)/2]^2
//sum of squares for odds n*(4*n*n-1)/3
//sum of cubes for odds n*n*(2*n*n-1)

//a/b%mod = a*(b^(m-2)%mod)
//(a>>x)&1 == 0
//a^b = (a+b)-2(a&b)

//srand(time(0))-always changing

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 4 ms 35164 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 4 ms 35164 KB Output is correct
6 Correct 5 ms 41308 KB Output is correct
7 Correct 5 ms 39440 KB Output is correct
8 Correct 5 ms 41304 KB Output is correct
9 Correct 5 ms 41308 KB Output is correct
10 Correct 5 ms 41308 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 4 ms 35164 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 4 ms 35164 KB Output is correct
6 Correct 5 ms 41308 KB Output is correct
7 Correct 5 ms 39440 KB Output is correct
8 Correct 5 ms 41304 KB Output is correct
9 Correct 5 ms 41308 KB Output is correct
10 Correct 5 ms 41308 KB Output is correct
11 Correct 9 ms 47708 KB Output is correct
12 Correct 18 ms 60016 KB Output is correct
13 Correct 18 ms 57948 KB Output is correct
14 Correct 25 ms 60020 KB Output is correct
15 Correct 26 ms 59992 KB Output is correct
16 Correct 37 ms 60020 KB Output is correct
17 Correct 28 ms 59996 KB Output is correct
18 Correct 37 ms 59992 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 904 ms 172368 KB Output is correct
2 Correct 903 ms 172584 KB Output is correct
3 Correct 1004 ms 172548 KB Output is correct
4 Correct 915 ms 172292 KB Output is correct
5 Correct 659 ms 172348 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3039 ms 94076 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 4 ms 35164 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 4 ms 35164 KB Output is correct
6 Correct 5 ms 41308 KB Output is correct
7 Correct 5 ms 39440 KB Output is correct
8 Correct 5 ms 41304 KB Output is correct
9 Correct 5 ms 41308 KB Output is correct
10 Correct 5 ms 41308 KB Output is correct
11 Correct 9 ms 47708 KB Output is correct
12 Correct 18 ms 60016 KB Output is correct
13 Correct 18 ms 57948 KB Output is correct
14 Correct 25 ms 60020 KB Output is correct
15 Correct 26 ms 59992 KB Output is correct
16 Correct 37 ms 60020 KB Output is correct
17 Correct 28 ms 59996 KB Output is correct
18 Correct 37 ms 59992 KB Output is correct
19 Runtime error 121 ms 234068 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 4 ms 35164 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 4 ms 35164 KB Output is correct
6 Correct 5 ms 41308 KB Output is correct
7 Correct 5 ms 39440 KB Output is correct
8 Correct 5 ms 41304 KB Output is correct
9 Correct 5 ms 41308 KB Output is correct
10 Correct 5 ms 41308 KB Output is correct
11 Correct 9 ms 47708 KB Output is correct
12 Correct 18 ms 60016 KB Output is correct
13 Correct 18 ms 57948 KB Output is correct
14 Correct 25 ms 60020 KB Output is correct
15 Correct 26 ms 59992 KB Output is correct
16 Correct 37 ms 60020 KB Output is correct
17 Correct 28 ms 59996 KB Output is correct
18 Correct 37 ms 59992 KB Output is correct
19 Correct 904 ms 172368 KB Output is correct
20 Correct 903 ms 172584 KB Output is correct
21 Correct 1004 ms 172548 KB Output is correct
22 Correct 915 ms 172292 KB Output is correct
23 Correct 659 ms 172348 KB Output is correct
24 Execution timed out 3039 ms 94076 KB Time limit exceeded
25 Halted 0 ms 0 KB -