oj.uz

Submission #1093984

# Submission time Handle Problem Language Result Execution time Memory
1093984 2024-09-28T08:30:36 Z Muhammet Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 3000 ms 16300 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];

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];
		v[a[i]].push_back(i);
		mx = max(mx,a[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++){
			if(sz(v[j]) == 0) continue;
			// cout << j << ' ';
			int t = (upper_bound(v[j].begin(), v[j].end(), r[i]) - v[j].begin() - 1);
			// cout << t << '\n';
			if(t == -1 or v[j][t]-1 < l[i]) continue;
			int ind = v[j][t]-1;
			// 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 352 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 1 ms 608 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 352 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 1 ms 608 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 1 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 Execution timed out 3076 ms 16300 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 1 ms 608 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 352 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 1 ms 608 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -