제출 #1253518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253518		avohado	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	215 ms	273652 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define maxn 200005
#define f first
#define s second
#define ll long long
#define pb(x) push_back(x)
int bit[maxn];
int get(int i, int n){
    int j=i, x=0;
    while(j>0){
        x+=bit[j];
        j-=j&(-j);
    }
    return x;
}
void upd(int i, int n){
    int j=i;
    while(j<=n){
        bit[j]++;
        j+=j&(-j);
        
    }
}
int b[maxn];
int64_t count_swaps(vector<int> v){
    int n=(int)v.size();
    queue<int> s[2][n+1];
    long long ans=0;
    for(int i=0; i<n; i++){
        s[(v[i]>0)][abs(v[i])].push(i);
    }
    for(int i=0; i<n; i++){
        if(b[i])continue;
        int x=s[(v[i]>0)][abs(v[i])].front(),y=s[!(v[i]>0)][abs(v[i])].front();
        b[y]=1;s[(v[i]>0)][abs(v[i])].pop();s[!(v[i]>0)][abs(v[i])].pop();
        ans+=y-x-1-get(y, n)+get(x, n)+(v[i]>0);
        upd(y, n);
    }
    return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15