oj.uz

Submission #890027

# Submission time Handle Problem Language Result Execution time Memory
890027 2023-12-20T11:01:52 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
30 / 100
 3000 ms 172612 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] < 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 16732 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 7 ms 35164 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 5 ms 35404 KB Output is correct
6 Correct 5 ms 41308 KB Output is correct
7 Correct 5 ms 39260 KB Output is correct
8 Correct 6 ms 41512 KB Output is correct
9 Correct 5 ms 41308 KB Output is correct
10 Correct 6 ms 41304 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 7 ms 35164 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 5 ms 35404 KB Output is correct
6 Correct 5 ms 41308 KB Output is correct
7 Correct 5 ms 39260 KB Output is correct
8 Correct 6 ms 41512 KB Output is correct
9 Correct 5 ms 41308 KB Output is correct
10 Correct 6 ms 41304 KB Output is correct
11 Correct 9 ms 47708 KB Output is correct
12 Correct 21 ms 60012 KB Output is correct
13 Correct 18 ms 58000 KB Output is correct
14 Correct 27 ms 59996 KB Output is correct
15 Correct 28 ms 60020 KB Output is correct
16 Correct 47 ms 59996 KB Output is correct
17 Correct 34 ms 59996 KB Output is correct
18 Correct 42 ms 59996 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 936 ms 172464 KB Output is correct
2 Correct 940 ms 172236 KB Output is correct
3 Correct 937 ms 172612 KB Output is correct
4 Correct 951 ms 172340 KB Output is correct
5 Correct 706 ms 172396 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3042 ms 94036 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 7 ms 35164 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 5 ms 35404 KB Output is correct
6 Correct 5 ms 41308 KB Output is correct
7 Correct 5 ms 39260 KB Output is correct
8 Correct 6 ms 41512 KB Output is correct
9 Correct 5 ms 41308 KB Output is correct
10 Correct 6 ms 41304 KB Output is correct
11 Correct 9 ms 47708 KB Output is correct
12 Correct 21 ms 60012 KB Output is correct
13 Correct 18 ms 58000 KB Output is correct
14 Correct 27 ms 59996 KB Output is correct
15 Correct 28 ms 60020 KB Output is correct
16 Correct 47 ms 59996 KB Output is correct
17 Correct 34 ms 59996 KB Output is correct
18 Correct 42 ms 59996 KB Output is correct
19 Incorrect 312 ms 115808 KB Output isn't correct
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 7 ms 35164 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 5 ms 35404 KB Output is correct
6 Correct 5 ms 41308 KB Output is correct
7 Correct 5 ms 39260 KB Output is correct
8 Correct 6 ms 41512 KB Output is correct
9 Correct 5 ms 41308 KB Output is correct
10 Correct 6 ms 41304 KB Output is correct
11 Correct 9 ms 47708 KB Output is correct
12 Correct 21 ms 60012 KB Output is correct
13 Correct 18 ms 58000 KB Output is correct
14 Correct 27 ms 59996 KB Output is correct
15 Correct 28 ms 60020 KB Output is correct
16 Correct 47 ms 59996 KB Output is correct
17 Correct 34 ms 59996 KB Output is correct
18 Correct 42 ms 59996 KB Output is correct
19 Correct 936 ms 172464 KB Output is correct
20 Correct 940 ms 172236 KB Output is correct
21 Correct 937 ms 172612 KB Output is correct
22 Correct 951 ms 172340 KB Output is correct
23 Correct 706 ms 172396 KB Output is correct
24 Execution timed out 3042 ms 94036 KB Time limit exceeded
25 Halted 0 ms 0 KB -