Submission #411622

#	Time	Username	Problem	Language	Result	Execution time	Memory
411622		RGBB	Swap Swap Sort (CCO21_day1problem1)	C++14	25 / 25	2974 ms	321512 KiB

Main

#include <iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int MAXN=1e5+5;
int n,k,q,inp[MAXN],target[MAXN],seg[(1<<18)];
ll outp;
vector<int>v[MAXN];
gp_hash_table<int,gp_hash_table<int,ll>>memo;
void constructSEG(){
    memset(seg,0,sizeof(seg));
}
int query(int a,int b,int c,int be,int en){
    if(a>b||a>en||b<be)return 0;
    if(a>=be&&b<=en)return seg[c];
    return query(a,(a+b)/2,2*c+1,be,en)+query((a+b)/2+1,b,2*c+2,be,en);
}
void update(int a,int b,int c,int t){
    if(a>b||a>t||b<t)return;
    if(a==b){
        seg[c]++;
        return;
    }
    update(a,(a+b)/2,2*c+1,t);
    update((a+b)/2+1,b,2*c+2,t);
    seg[c]=seg[2*c+1]+seg[2*c+2];
}
void constructMEM(){
    for(int i=0;i<n;i++)v[inp[i]].push_back(i);
}
ll bs(vector<int>&a,vector<int>&b){
    ll ret=0;
    int l=0;
    int r,m;
    for(int i:b){
        r=a.size()-1;
        m=(l+r)/2;
        while(r-l>1){
            if(i<a[m])r=m;
            else l=m;
            m=(l+r)/2;
        }
        if(i<a[l])ret+=a.size()-l;
        else if(i<a[r])ret+=a.size()-r;
    }
    return ret;
}
void calc(int a,int b){
    ll fro,inv;
    if(v[a].size()>v[b].size()){
        fro=bs(v[a],v[b]);
        inv=(ll)v[a].size()*(ll)v[b].size()-fro;
    }
    else{
        inv=bs(v[b],v[a]);
        fro=(ll)v[a].size()*(ll)v[b].size()-inv;
    }
    memo[a][b]=fro;
    memo[b][a]=inv;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>k>>q;
    for(int i=0;i<n;i++)cin>>inp[i];
    for(int i=0;i<n;i++)target[i]=i+1;
    constructSEG();
    outp=0;
    for(int i=0;i<n;i++){
        outp+=query(0,n,0,inp[i]+1,k);
        update(0,n,0,inp[i]);
    }
    constructMEM();
    for(int i=0;i<q;i++){
        int j;
        cin>>j;
        j--;
        if(memo.find(target[j])==memo.end()||memo[target[j]].find(target[j+1])==memo[target[j]].end())calc(target[j],target[j+1]);
        outp-=memo[target[j]][target[j+1]];
        outp+=memo[target[j+1]][target[j]];
        swap(target[j],target[j+1]);
        cout<<outp<<"\n";
    }
}

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