Submission #510135

#TimeUsernameProblemLanguageResultExecution timeMemory
510135ETKSwap Swap Sort (CCO21_day1problem1)C++14
0 / 25
156 ms19048 KiB
#include <bits/stdc++.h> #define rep(i,a,b) for(int i=(a);i<=(b);++i) #define per(i,a,b) for(int i=(a);i>=(b);--i) #define pii pair<int,int> #define vi vector<int> #define mp make_pair #define fi first #define se second #define pb push_back #define debug(...) fprintf(stderr, __VA_ARGS__) #define ALL(x) x.begin(),x.end() #define sz(x) int(x.size()) #define ll long long using namespace std; inline ll read(){ ll x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f; } const int N=1e5+5,B = 100; int n,k,q,id[N],a[N],idx[N],cnt; int t[N]; void add(int x,int v){for(;x <= n;x += x & -x)t[x] += v;} ll Q(int x){ ll res = 0; for(;x;x -= x & -x)res += t[x]; return res; } vector <int> pos[N]; vector <ll> pre[N]; ll work(int a,int b){ ll tot = (ll)sz(pos[a]) * sz(pos[b]); if(sz(pos[a]) > B)return pre[b][idx[a]]; if(sz(pos[b]) > B)return tot - pre[a][idx[b]]; int j = 0; ll res = 0; for(auto x : pos[a]){ while(j < sz(pos[b]) && pos[b][j] < x)j++; res += j; } return res; } int main(){ n = read(),k = read(),q = read(); rep(i,1,n){ a[i] = read(); pos[a[i]].pb(i); } rep(i,1,n)id[i] = i; ll ans = 0; rep(i,1,n){ ans += Q(k) - Q(a[i]); add(a[i],1); } rep(i,1,k)if(sz(pos[i]) > B){ idx[i] = cnt++; rep(j,1,k)pre[j].pb(0); int res = 0; rep(j,1,n){ if(a[j] == i)res++; else pre[a[j]].back() += res; } } while(q--){ int x = read(); ans += (ll)sz(pos[id[x]]) * sz(pos[id[x+1]]) - 2 * work(id[x],id[x+1]); printf("%lld\n",ans); swap(id[x],id[x+1]); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...