제출 #423142

#제출 시각아이디문제언어결과실행 시간메모리
423142Osama_AlkhodairySwap Swap Sort (CCO21_day1problem1)C++17
3 / 25
5052 ms4040 KiB
#include <bits/stdc++.h> using namespace std; #define finish(x) return cout << x << endl, 0 #define ll long long const int N = 100001; const int SQ = 100; int n, k, q, mp[N], f[N], tree[4 * N]; ll cost[N / SQ][N]; vector <int> a, v[N]; void update(int l, int r, int node, int idx, int v){ if(r < l || r < idx || l > idx) return; if(l == r){ tree[node] = v; return; } int mid = (l + r) / 2; update(l, mid, 2 * node, idx, v); update(mid + 1, r, 2 * node + 1, idx, v); tree[node] = tree[2 * node] + tree[2 * node + 1]; } int query(int l, int r, int node, int s, int e){ if(r < l || r < s || l > e) return 0; if(s <= l && r <= e) return tree[node]; int mid = (l + r) / 2; return query(l, mid, 2 * node, s, e) + query(mid + 1, r, 2 * node + 1, s, e); } int calc_small(vector <int> &l, vector <int> &r){ int ret = 0; int pl = 0, pr = 0; int cnt = 0; while(pl < (int)l.size() || pr < (int)r.size()){ if(pl == (int)l.size()) pr++; else if(pr == (int)r.size()){ ret += cnt; pl++; } else if(l[pl] < r[pr]){ ret += cnt; pl++; } else{ cnt++; pr++; } } return ret; } ll calc_cost(int x, int y){ //~ if((int)v[x].size() >= SQ){ //~ return 1LL * v[x].size() * v[y].size() - cost[mp[x]][y]; //~ } //~ if((int)v[y].size() >= SQ){ //~ return cost[mp[y]][x]; //~ } return calc_small(v[x], v[y]); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); memset(mp, -1, sizeof mp); cin >> n >> k >> q; a.resize(n); for(auto &i : a){ cin >> i; i--; } for(int i = 0 ; i < n ; i++){ v[a[i]].push_back(i); } int c = 0; for(int i = 0 ; i < k ; i++){ if((int)v[i].size() >= SQ){ mp[i] = c++; int cnt = 0; for(int j = 0 ; j < n ; j++){ if(a[j] == i) cnt++; else cost[mp[i]][a[j]] += cnt; } } } for(int i = 0 ; i < k ; i++){ f[i] = i; } ll ans = 0; //~ for(int i = 0 ; i < n ; i++){ //~ ans += query(0, k - 1, 1, a[i] + 1, k - 1); //~ update(0, k - 1, 1, a[i], 1); //~ } for(int i = 0 ; i < n ; i++){ for(int j = i + 1 ; j < n ; j++){ ans += a[i] > a[j]; } } for(int i = 0 ; i < q ; i++){ int j; cin >> j; j--; ans -= calc_cost(f[j], f[j + 1]); swap(f[j], f[j + 1]); ans += calc_cost(f[j], f[j + 1]); cout << ans << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...