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](https://mirror.codeforces.com/contest/2009/problem/G1), test case 2 shows TLE but if I change the line 7 to int num[1000000] then it passes.
↵
~~~~~↵
#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](https://mirror.codeforces.com/contest/2009/problem/G1), test case 2 shows TLE but if I change the line 7 to int num[1000000] then it passes.
