#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = 5e5 ;
bool flag ;
int n, q, tn, d[N + 1], ans[N + 1] ;
struct query
{
int t, l, r, ind ;
};
bool cmp(query q1, query q2)
{
return (q1.t < q2.t) ;
}
vector<pair<int, int>> pep ;
vector<query> qr ;
signed main()
{
ios_base::sync_with_stdio( 0 ) ;
cin.tie( 0 ) ;
cout.tie( 0 ) ;
cin >> n >> q ;
for(int i = 1 ; i <= n ; i++)
{
cin >> d[i] ;
pep.push_back({-i, d[i]}) ;
}
reverse(pep.begin(), pep.end()) ;
pep.push_back({0, 0}) ;
for(int i = 1 ; i <= q ; i++)
{
query q ;
cin >> q.t >> q.l >> q.r ;
if(q.t > 1000)
flag = 1 ;
q.ind = i ;
qr.push_back(q) ;
}
if(n <= 1000 && q <= 1000 && !flag)
{
sort(qr.begin(), qr.end(), cmp) ;
for(query i : qr)
{
int sum = 0 ;
while(tn < i.t)
{
tn++ ;
pep[pep.size() - 1].fi = tn ;
for(int j = pep.size() - 2 ; j >= 0 ; j--)
if(pep[j + 1].fi - pep[j].fi > pep[j].se)
pep[j].fi = pep[j + 1].fi - 1 ;
}
// cout << tn << '\n' ;
// for(auto j : pep)
// {
// cout << j.fi << ' ' ;
// if(i.l <= j.fi && j.fi <= i.r)
// sum++ ;
// }
// cout << "\n______________\n" ;
ans[i.ind] = sum ;
}
for(int i = 1 ; i <= q ; i++)
cout << ans[i] << '\n' ;
}
return 0 ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
139 ms |
14460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
139 ms |
14460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
