| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1094597 | Muhammet | Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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';
}
}