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<int> v;↵
↵
set<int> S;↵
vector<int> 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
↵
here is the Link to the problem: https://mirror.codeforces.com/contest/840/problem/D↵
↵
This is my solution:↵
using namespace std;↵
struct Query{↵
int L, R, K, idx;↵
};↵
int rootN;↵
vector<int> v;↵
↵
set<int> S;↵
vector<int> 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
