oj.uz

Submission #1094005

# Submission time Handle Problem Language Result Execution time Memory
1094005 2024-09-28T08:56:01 Z Muhammet Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 213 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;

#define sz(s) (int)s.size()

const int N = 1e5+5;

int n, m, l[N], r[N], k[N], p[N], a[N], sp[N][30], b[N][1005];

vector <int> v[1005];

int main(){
	// ios::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n >> m;
	int mx = 0;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		p[i] = p[i-1] + (a[i] < a[i-1]);
		sp[i][0] = a[i];
		mx = max(mx,a[i]);
		v[a[i]].push_back(i);
	}
	for(int i = 1; i <= n; i++){
		if(i == v[a[i]].back()){
			for(int j = i; j <= n; j++){
				b[j][a[i]] = i;
			}
			continue;
		}
		int t = *upper_bound(v[a[i]].begin(), v[a[i]].end(), i);
		for(int j = i; j < t; j++){
			b[j][a[i]] = i;
		}
	}
	for(int j = 1; j <= 25; j++){
		for(int i = 1; i <= n-(1<<j)+1; i++){
			sp[i][j] = max(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
		}
	}
	for(int i = 1; i <= m; i++){
		cin >> l[i] >> r[i] >> k[i];
		int k1 = 0;
		for(int j = 0; j <= mx; j++){
			// cout << j << ' ';
			// cout << t << '\n';
			int ind = b[r[i]][j];
			if(ind-1 < l[i]) continue;
			// cout << l[i] << ' ' << ind << '\n';
			int lg = log2(ind-l[i]+1);
			// cout << lg << '\n';
			int x = max(sp[l[i]][lg], sp[ind-(1<<lg)+1][lg]);
			if(x > j) k1 = max(k1, x-j);
		}
		cout << (k1 <= k[i]) << '\n';
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 6 ms 604 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 6 ms 604 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 6 ms 604 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 6 ms 604 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -