Submission #1212489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212489		guagua0407	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	48 ms	11720 KiB

shoes

#include "shoes.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

namespace{
    const int mxn=2e5+5;
    vector<int> bit(mxn);
    void update(int pos,int val){
        pos++;
        for(;pos<mxn;pos+=(pos&-pos)){
            bit[pos]+=val;
        }
    }
    int query(int pos){
        pos++;
        int ans=0;
        for(;pos>0;pos-=(pos&-pos)){
            ans+=bit[pos];
        }
        return ans;
    }
}

long long count_swaps(std::vector<int> a) {
	int n=(int)a.size();
    vector<vector<int>> pos(n+1);
    for(int i=0;i<n;i++){
        pos[abs(a[i])].push_back(i);
    }
    vector<pair<int,int>> vec;
    ll ans=0;
    for(int t=1;t<=n;t++){
        deque<int> st;
        for(auto v:pos[t]){
            if(st.empty() or a[st[0]]/abs(a[st[0]])==a[v]/abs(a[v])){
                st.push_back(v);
            }
            else{
                vec.push_back({st[0],v});
                st.pop_front();
                if(a[v]<0) ans++;
            }
        }
    }
    for(auto v:vec){
        ans+=v.s-v.f-1;
    }
    ll neg=0;
    sort(all(vec));
    for(auto v:vec){
        neg+=query(v.s)-query(v.f);
        update(v.s,1);
    }
    return ans-neg;
}

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