#include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for (int i = (a); i <= (b); ++i) #define REPD(i,a,b) for (int i = (a); i >= (b); --i) #define FORI(i,n) REP(i,1,n) #define FOR(i,n) REP(i,0,int(n)-1) #define mp make_pair #define pb push_back #define pii pair<int,int> #define vi vector<int> #define ll long long #define SZ(x) int((x).size()) #define DBG(v) cerr << #v << " = " << (v) << endl; #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define fi first #define se second const int N = 500500; int n,k,m,l; int a[N], vis[N], badids[N], goodids[N]; int main() { scanf("%d%d", &n, &k); FOR(i,n) scanf("%d", &a[i]); FOR(i,n) { if (!vis[a[i]]) { if (i >= k) { goodids[l++] = i; } vis[a[i]] = 1; } else if (i < k) { badids[m++] = i; } } if (l < m) { printf("-1\n"); return 0; } //cerr << m << " do zmiany\n"; //FOR(i,m) cerr << a[badids[i]] << " "; cerr << "\n"; //FOR(i,m) cerr << a[goodids[i]] << " "; cerr << "\n"; ll res = 1LL * m * m; FOR(i,m) { res += k - m + i - badids[i]; res += goodids[i] - (k + i); //cerr << badids[i] << " : " << k - m + i - badids[i] << "\n"; //cerr << goodids[i] << " : " << goodids[i] - (k + i) << "\n"; } printf("%lld\n", res); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for (int i = (a); i <= (b); ++i) #define REPD(i,a,b) for (int i = (a); i >= (b); --i) #define FORI(i,n) REP(i,1,n) #define FOR(i,n) REP(i,0,int(n)-1) #define mp make_pair #define pb push_back #define pii pair<int,int> #define vi vector<int> #define ll long long #define SZ(x) int((x).size()) #define DBG(v) cerr << #v << " = " << (v) << endl; #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define fi first #define se second const int N = 500500; int n,k,m,l; int a[N], vis[N], badids[N], goodids[N]; int main() { scanf("%d%d", &n, &k); FOR(i,n) scanf("%d", &a[i]); FOR(i,n) { if (!vis[a[i]]) { if (i >= k) { goodids[l++] = i; } vis[a[i]] = 1; } else if (i < k) { badids[m++] = i; } } if (l < m) { printf("-1\n"); return 0; } //cerr << m << " do zmiany\n"; //FOR(i,m) cerr << a[badids[i]] << " "; cerr << "\n"; //FOR(i,m) cerr << a[goodids[i]] << " "; cerr << "\n"; ll res = 1LL * m * m; FOR(i,m) { res += k - m + i - badids[i]; res += goodids[i] - (k + i); //cerr << badids[i] << " : " << k - m + i - badids[i] << "\n"; //cerr << goodids[i] << " : " << goodids[i] - (k + i) << "\n"; } printf("%lld\n", res); return 0; } |