Hi can someone help me with this
#include <bits/stdc++.h>
using namespace std;
#define ll long long
multiset<int> s;
int a[1000000], p[1000000];
ll num[1000000];
ll ans[1000000];
void add(int x,int y){
if(num[x])s.erase(s.find(num[x]));
num[x]+=y;
if(num[x])s.insert(num[x]);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
ll test;
cin>>test;
while(test--)
{
ll n,k,q;
cin>>n>>k>>q;
for(int i = 1; i <= n; i++){
cin>>a[i];
a[i] -= i; a[i] += n;
}
memset(num,0,9*n);
s = {};
for(int i = 1; i <= n; i++){
if(i>k) add(a[i-k],-1);
add(a[i],1);
if(i>=k) ans[i-k+1] = k - *s.rbegin();
}
while(q--){
ll l,r;
cin>>l>>r;
cout<<ans[l]<<endl;
}
}
return 0;
}
Running the code for problem, test case 2 shows TLE but if I change the line 7 to int num[1000000] then it passes.
Auto comment: topic has been updated by OganessonIsland (previous revision, new revision, compare).
Seems like you didn't reset the
num
array properly (you only set $$$9*n$$$ bytes to zero while the numbers can go up to $$$2*n-1$$$, which requires the first $$$2*n$$$ elements of thenum
array to be $$$0$$$ which requires $$$2*n*sizeof(ll)=16*n$$$ bytes to be $$$0$$$). I have fixed the bug: 279736017Thanks