oj.uz

Submission #890029

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

#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[1001];

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 (a[i]<=1000) 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<=min(mx,1000);i++){
				l = 0;
				r = len(p[i]) - 1;
				while(l<=r){
					int md = (l + r) / 2;
					if (p[i][md] <= rr){
						l = md + 1;
					}
					else{
						r = md - 1;
					}
				}
				l = r;
				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 16732 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 4 ms 35164 KB Output is correct
4 Correct 3 ms 26968 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 39260 KB Output is correct
8 Correct 5 ms 41308 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 16732 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 4 ms 35164 KB Output is correct
4 Correct 3 ms 26968 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 39260 KB Output is correct
8 Correct 5 ms 41308 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 47704 KB Output is correct
12 Correct 17 ms 59996 KB Output is correct
13 Correct 18 ms 57944 KB Output is correct
14 Correct 28 ms 59996 KB Output is correct
15 Correct 31 ms 60012 KB Output is correct
16 Correct 50 ms 59992 KB Output is correct
17 Correct 34 ms 59992 KB Output is correct
18 Correct 50 ms 59992 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 957 ms 172464 KB Output is correct
2 Correct 929 ms 172628 KB Output is correct
3 Correct 906 ms 172616 KB Output is correct
4 Correct 879 ms 172304 KB Output is correct
5 Correct 648 ms 172664 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3074 ms 93864 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 16732 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 4 ms 35164 KB Output is correct
4 Correct 3 ms 26968 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 39260 KB Output is correct
8 Correct 5 ms 41308 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 47704 KB Output is correct
12 Correct 17 ms 59996 KB Output is correct
13 Correct 18 ms 57944 KB Output is correct
14 Correct 28 ms 59996 KB Output is correct
15 Correct 31 ms 60012 KB Output is correct
16 Correct 50 ms 59992 KB Output is correct
17 Correct 34 ms 59992 KB Output is correct
18 Correct 50 ms 59992 KB Output is correct
19 Runtime error 120 ms 233880 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 16732 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 4 ms 35164 KB Output is correct
4 Correct 3 ms 26968 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 39260 KB Output is correct
8 Correct 5 ms 41308 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 47704 KB Output is correct
12 Correct 17 ms 59996 KB Output is correct
13 Correct 18 ms 57944 KB Output is correct
14 Correct 28 ms 59996 KB Output is correct
15 Correct 31 ms 60012 KB Output is correct
16 Correct 50 ms 59992 KB Output is correct
17 Correct 34 ms 59992 KB Output is correct
18 Correct 50 ms 59992 KB Output is correct
19 Correct 957 ms 172464 KB Output is correct
20 Correct 929 ms 172628 KB Output is correct
21 Correct 906 ms 172616 KB Output is correct
22 Correct 879 ms 172304 KB Output is correct
23 Correct 648 ms 172664 KB Output is correct
24 Execution timed out 3074 ms 93864 KB Time limit exceeded
25 Halted 0 ms 0 KB -