#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std ;
const int N = (1 << 20) ;
bool ans[N + 1] ;
int n, m, all_mx, all_mn = 1e9, pos[1001], a[N + 1], l[N + 1], r[N + 1], k[N + 1], ind[N + 1], pw[N + 1], mx[N + 1][21], mn1[N + 1][21], mn2[N + 1][21] ;
vector<int> qr[N + 1] ;
void build_sparce_table1()
{
mn1[1][0] = a[1] ;
for(int i = 2 ; i <= N ; i++)
pw[i] = pw[i / 2] + 1, mn1[i][0] = a[i] ;
for(int i = 1 ; i < 21 ; i++)
for(int j = 1 ; j <= N - (1 << i) + 1 ; j++)
mn1[j][i] = min(mn1[j][i - 1], mn1[j + (1 << (i - 1))][i - 1]) ;
}
int get_min1(int l, int r)
{
int num = pw[r - l + 1] ;
return min(mn1[l][num], mn1[r - (1 << num) + 1][num]) ;
}
void build_sparce_table2()
{
mn2[1][0] = ind[1] ;
for(int i = 2 ; i <= N ; i++)
mn2[i][0] = ind[i] ;
for(int i = 1 ; i < 21 ; i++)
for(int j = 1 ; j <= N - (1 << i) + 1 ; j++)
mn2[j][i] = min(mn2[j][i - 1], mn2[j + (1 << (i - 1))][i - 1]) ;
}
int get_min2(int l, int r)
{
int num = pw[r - l + 1] ;
return min(mn2[l][num], mn2[r - (1 << num) + 1][num]) ;
}
void build_sparce_table3()
{
mx[1][0] = a[1] ;
for(int i = 2 ; i <= N ; i++)
pw[i] = pw[i / 2] + 1, mx[i][0] = a[i] ;
for(int i = 1 ; i < 21 ; i++)
for(int j = 1 ; j <= N - (1 << i) + 1 ; j++)
mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1))][i - 1]) ;
}
int get_max(int l, int r)
{
int num = pw[r - l + 1] ;
return max(mx[l][num], mx[r - (1 << num) + 1][num]) ;
}
signed main()
{
ios_base::sync_with_stdio( 0 ) ;
cin.tie( 0 ) ;
cout.tie( 0 ) ;
cin >> n >> m ;
for(int i = 1 ; i <= n ; i++)
cin >> a[i], all_mn = min(all_mn, a[i]), all_mx = max(all_mx, a[i]) ;
if(n <= 5e3 && m <= 5e3)
{
for(int i = 1 ; i <= m ; i++)
{
int sum = 0 ;
cin >> l[i] >> r[i] >> k[i] ;
pair<int, int> b[n + 1] ;
int pref[n + 1] = {} ;
for(int i = 1 ; i <= n ; i++)
b[i] = {a[i], i} ;
for(int j = l[i] ; j <= r[i] ; j++)
pref[j] = max(pref[j - 1], a[j]) ;
sort(b + l[i], b + r[i] + 1) ;
for(int j = l[i] ; j <= r[i] ; j++)
if(pref[b[j].se - 1] > b[j].fi)sum = max(sum, pref[b[j].se - 1] + b[j].fi) ;
if(sum <= k[i])
cout << "1\n" ;
else
cout << "0\n" ;
}
return 0 ;
}
if(all_mx <= 1000)
{
for(int i = 1 ; i <= m ; i++)
{
cin >> l[i] >> r[i] >> k[i] ;
qr[r[i]].push_back(i) ;
}
build_sparce_table3() ;
for(int i = 1 ; i <= n ; i++)
{
pos[a[i]] = i ;
for(int j : qr[i])
{
bool flag = 0 ;
for(int q = 0 ; q <= all_mx ; q++)
if(l[j] < pos[q] && get_max(l[j], pos[q]) > q && get_max(l[j], pos[q]) + q > k[j])
{
flag = 1 ;
break ;
}
ans[j] = 1 ^ flag ;
}
}
for(int i = 1 ; i <= m ; i++)
cout << ans[i] << '\n' ;
return 0 ;
}
build_sparce_table1() ;
for(int i = 1 ; i <= N ; i++)
{
int l1 = i, r1 = N + 1 ;
while(l1 + 1 < r1)
{
int mid = (l1 + r1) >> 1 ;
if(get_min1(i, mid) < a[i])r1 = mid ;
else l1 = mid ;
}
ind[i] = r1 ;
}
build_sparce_table2() ;
for(int i = 1 ; i <= m ; i++)
{
cin >> l[i] >> r[i] >> k[i] ;
if(l[i] == r[i] || get_min2(l[i], r[i] - 1) > r[i])cout << "1\n" ;
else cout << "0\n" ;
}
return 0 ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
33 ms |
50380 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
33 ms |
50396 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
33 ms |
50380 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
33 ms |
50416 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
50352 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
33 ms |
50380 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
