I am trying to learn sqrt decomposition from cp algorithms in their practice problems session there is this problem called destiny i am stuck at this problem from a long time, not able to find out what the error is
here is the Link to the problem: https://mirror.codeforces.com/contest/840/problem/D
This is my solution:
include<bits/stdc++.h>
using namespace std; struct Query{ int L, R, K, idx; }; int rootN; vector v;
set S; vector freq(300001); bool comp(Query X, Query Y){ if(X.L/rootN == Y.L/rootN){ return X.R < Y.R; } else return X.L/rootN < Y.L/rootN; }
int main(){ int n, q; cin >> n >> q;
v.resize(n+1);
for(int i = 1; i <= n; ++i) cin >> v[i];
vector<Query> Q(q);
rootN = sqrtl(n);
for(int i = 0 ; i < q; ++i){
cin >> Q[i].L >> Q[i].R >> Q[i].K;
Q[i].idx = i;
}
sort(Q.begin(), Q.end(), comp);
int currL = 1, currR = 1;
freq[v[1]]++;
S.insert(v[1]);
vector<int> ans(q);
for(auto query : Q){
int L = query.L, R = query.R, K = query.K;
int treshold = (R - L + 1)/K;
while(currL < L){
freq[v[currL]]--;
if(freq[v[currL]] == treshold){
S.erase(v[currL]);
}
currL++;
}
while(currL > L){
currL--;
freq[v[currL]]++;
if(freq[v[currL]] == 1 + treshold){
S.insert(v[currL]);
}
}
while(currR < R){
currR++;
freq[v[currR]]++;
if(freq[v[currR]] == 1 + treshold){
S.insert(v[currR]);
}
}
while(currR > R){
freq[v[currR]]--;
if(freq[v[currR]] == treshold){
S.erase(v[currR]);
}
currR--;
}
ans[query.idx] = (S.size()) ? *(S.begin()) : -1;
}
for(auto x : ans) cout << x << endl;
} Some one please help me solve the errors, and also recommend some problems to learn sqrt decomp properly




