Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //teja349
- #include <bits/stdc++.h>
- #include <vector>
- #include <set>
- #include <map>
- #include <string>
- #include <cstdio>
- #include <cstdlib>
- #include <climits>
- #include <utility>
- #include <algorithm>
- #include <cmath>
- #include <queue>
- #include <stack>
- #include <iomanip>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- //setbase - cout << setbase (16); cout << 100 << endl; Prints 64
- //setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
- //setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
- //cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
- using namespace std;
- using namespace __gnu_pbds;
- #define f(i,a,b) for(i=a;i<b;i++)
- #define rep(i,n) f(i,0,n)
- #define fd(i,a,b) for(i=a;i>=b;i--)
- #define pb push_back
- #define mp make_pair
- #define vi vector< int >
- #define vl vector< ll >
- #define ss second
- #define ff first
- #define ll long long
- #define pii pair< int,int >
- #define pll pair< ll,ll >
- #define sz(a) a.size()
- #define inf (1000*1000*1000+5)
- #define all(a) a.begin(),a.end()
- #define tri pair<int,pii>
- #define vii vector<pii>
- #define vll vector<pll>
- #define viii vector<tri>
- #define mod (1000*1000*1000+7)
- #define pqueue priority_queue< int >
- #define pdqueue priority_queue< int,vi ,greater< int > >
- #define flush fflush(stdout)
- #define primeDEN 727999983
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- // find_by_order() // order_of_key
- typedef tree<
- int,
- null_type,
- less<int>,
- rb_tree_tag,
- tree_order_statistics_node_update>
- ordered_set;
- #define int ll
- vector<vi> vec(312345);
- int pre[312345];
- int getapsum(int val){
- return val*(val+1)/2;
- }
- int getsum(int i,int j){
- if(i==0)
- return pre[j];
- return pre[j]-pre[i-1];
- }
- int a[312345],done[312345];
- main(){
- std::ios::sync_with_stdio(false); cin.tie(NULL);
- int t;
- cin>>t;
- while(t--){
- int n,k;
- cin>>n>>k;
- int i;
- map<int,int> mapi;
- rep(i,n){
- cin>>a[i];
- done[a[i]]=0;
- vec[a[i]].pb(i);
- }
- int val,lef,rig,j,ans,mini,iinf;
- iinf=inf;
- iinf*=inf;
- mini=iinf;
- rep(i,n){
- if(done[a[i]])
- continue;
- done[a[i]]=1;
- if(vec[a[i]].size()<k){
- vec[a[i]].clear();
- continue;
- }
- val=a[i];
- lef=k/2;
- rig=k-lef;
- rep(j,vec[val].size()){
- if(j==0){
- pre[j]=vec[val][j];
- }
- else{
- pre[j]=pre[j-1]+vec[val][j];
- }
- }
- f(j,k/2,vec[val].size()){
- if(j+rig-1==vec[val].size())
- break;
- ans=getapsum(vec[val][j]-1)-getapsum(vec[val][j]-lef-1)-getsum(j-lef,j-1);
- ans+=getsum(j,j+rig-1)-getapsum(vec[val][j]+rig-1)+getapsum(vec[val][j]-1);
- mini=min(mini,ans);
- }
- vec[val].clear();
- }
- if(mini==iinf)
- mini=-1;
- cout<<mini<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement