Submission #851875

#	Time	Username	Problem	Language	Result	Execution time	Memory
851875		NaimSS	Swap Swap Sort (CCO21_day1problem1)	C++14	25 / 25	3375 ms	149268 KiB

Main

#include <bits/stdc++.h>
// #define int long long
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define Unique(v) sort(all(v)),v.erase(unique(all(v)),v.end());
#define sz(v) ((int)v.size())
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
//#define left oooooopss
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
#define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
// std::mt19937_64 rng64((int) std::chrono::steady_clock::now().time_since_epoch().count());
std::mt19937 rng(
  
//  (int) std::chrono::steady_clock::now().time_since_epoch().count()
   1239010
);


ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
//inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll b,ll e,ll m){
    b%=m;
    ll ans = 1;
    for (; e; b = b * b % m, e /= 2)
        if (e & 1) ans = ans * b % m;
    return ans;
}
 
// debug:
template<class T>void print_vector(vector<T> &v){
    rep(i,0,sz(v))cout<<v[i]<<" \n"[i==sz(v)-1];
}
void dbg_out() {cerr << endl; }
template<typename Head, typename ... Tail> void dbg_out(Head H,Tail... T){
    cerr << ' ' << H;
    dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__), cerr << endl
#else
#define dbg(...) 42
#endif
//

int n,k,q;
const int N = 100100;
int a[N];
int cnt[N];
vi posi[N];

map<pii,ll> Cnt;

const int MAGIC = 500;

ll solve(int i,int j){
    if(Cnt.count({i,j}))return Cnt[{i,j}];
    ll res=0;
    int sw=0;
    if(sz(posi[i]) > sz(posi[j]))swap(i,j),sw = 1;
    
    if(max(sz(posi[i]), sz(posi[j])) > MAGIC){

        int tam = sz(posi[j]);
        for(int p : posi[i]){
            int k = lower_bound(all(posi[j]), p) - posi[j].begin();
            res += tam - k;
        }
    }else{
        int k = 0;
        int tam = sz(posi[j]);
        for(int p : posi[i]){
            while(k < sz(posi[j]) && posi[j][k] < p)
                k++;
            res += tam - k;
        }
    }
    if(sw){
        swap(i,j);
        res = cnt[i] * (ll)cnt[j] - res;
    }
    Cnt[{j,i}] = cnt[i] * (ll)cnt[j] - res;
    return Cnt[{i,j}] = res;
}

struct BIT{
    vi bit;int n;
    BIT(int _n){
        n = _n;
        bit.resize(n+10);
    }
    int sum(int x){
        int res=0;
        for(; x > 0; x-= (x&-x))res += bit[x];
        return res;
    }
    void upd(int x,int v){
        for(; x <= n; x += (x&-x))
            bit[x] += v;
    }

};

int32_t main(){
    fastio;
    cin >> n >> k >> q;
    ll inv = 0;
    BIT bit(n+1);
    rep(i,1,n+1){
        cin >> a[i];
        bit.upd(a[i], 1);
        inv += i - bit.sum(a[i]);
        cnt[a[i]]++;
        posi[a[i]].pb(i);
    }
    vi target(k+1);
    rep(i,1,k+1)target[i] = i;

    while(q--){
        int j;
        cin >> j;
        inv += solve(target[j], target[j+1]) - solve(target[j+1], target[j]);
        swap(target[j], target[j+1]);
        cout << inv << endl;
    }
    
    // math -> gcd it all
    // Did you swap N,M? N=1?
}

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 5 / 5
• Subtask 4: 14 / 14