| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1094597 | Muhammet | Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define sz(s) (int)s.size()
const int N = 1e6+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];
sp[i][0] = a[i];
mx = max(mx,a[i]);
v[a[i]].push_back(i);
}
for(int i = 1; i <= n; i++){
b[i][a[i]] = 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 = -1;
for(int j = 0; j <= mx; j++){
int ind = b[r[i]][j];
ind--;
if(ind < l[i]) continue;
int lg = log2(ind-l[i]+1);
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] and k1 != -1) << '\n';
}
}