제출 #1308512

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308512		888313666	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	124 ms	21548 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct segtree{
    int n;
    vector<int> st;
    
    int build(const int l, const int r, const int i){
        if (l+1==r){
            return st[i]=1;
        }
        const auto m=l+(r-l>>1);
        return st[i]=build(l, m, (i<<1)+1)+build(m, r, (i<<1)+2);
    }

    segtree(const int n){
        this->n=n;
        st.resize(n<<2, 0);
        build(0, n, 0);
    }

    void upd(const int p, const int l, const int r, const int i){
        if (p<l || r<=p) return;
        if (l+1==r){
            st[i]=0;
            return;
        }
        const auto m=l+(r-l>>1);
        upd(p, l, m, (i<<1)+1);
        upd(p, m, r, (i<<1)+2);
        st[i]=st[(i<<1)+1]+st[(i<<1)+2];
    }

    void update(const int p){
        upd(p, 0, n, 0);
    }

    int qry(const int l, const int r, const int cl, const int cr, const int i){
        if (cr<=l || r<=cl || cr<=cl) return 0;
        if (l<=cl && cr<=r) return st[i];
        const auto m=cl+(cr-cl>>1);
        return qry(l, r, cl, m, (i<<1)+1)+qry(l, r, m, cr, (i<<1)+2);
    }

    int query(const int l, const int r){
        return qry(l, r, 0, n, 0);
    }
};

ll count_swaps(vector<int> s){
    const int n=s.size();
    vector<vector<int>> lf(n+1), rt(n+1);
    vector<int> rm(n, 1);
    for (int i=0; i<n; i++){
        if (s[i]<0){
            lf[-s[i]].push_back(i);
        } else rt[s[i]].push_back(i);
    }
    for (int i=1; i<=n; i++) {
        reverse(lf[i].begin(), lf[i].end());
        reverse(rt[i].begin(), rt[i].end());
    }
    segtree f(n);
    ll ans=0;
    for (int i=0; i<n; i++) if (rm[i]){
        int idx;
        if (s[i]<0){
            idx=rt[-s[i]].back();
            rt[-s[i]].pop_back();
            lf[-s[i]].pop_back();
        } else {
            idx=lf[s[i]].back();
            rt[s[i]].pop_back();
            lf[s[i]].pop_back();
            ++ans;
        }
        f.update(i);
        f.update(idx);
        rm[i]=0;
        rm[idx]=0;
        assert(i<idx);
        ans+=f.query(i, idx);
    }
    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