제출 #572556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
572556		MadokaMagicaFan	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	160 ms	139404 KiB

shoes

    #include "bits/stdc++.h"
     
    using namespace std;
     
    using ll = long long;
    const ll inf = 1e9;
    const int md1 = 1e9+7;
    const int md2 = 998244353;
     
    #define all(v)                      v.begin(), v.end()
    #define rall(v)                     v.rbegin(), v.rend()
    #define sz(v)                       ((int)v.size())
     
    #define forn(i,n)                   for(int i = 0; i < n; ++i)
    #define forbe(i,b,e)                for(int i = b; i < e; ++i)
     
    #define pb                          push_back
     
    #define pry                         puts("YES")
    #define prn                         puts("NO")
    #define endl                        '\n'
     
    #define fst                         first
    #define scn                         second
     
    const int N = 1e5;
     
    bitset<2*N> c;
     
    queue<int> pp[N+1];
    queue<int> np[N+1];
     
    template<typename T>
    struct BIT{
        int n;
        vector<T> fen;
        BIT(int n){
            this->n = n;
            fen.assign(n,0);
        }
        BIT(vector<T> a) : BIT(a.size()){
            for(int i = 0; i < n; ++i) add(i,a[i]);
        }
        void add(int x, T v){
            for(; x < n; x |= x+1) fen[x] += v;
        }
        T query(int x){
            T res = 0;
            for(; x >= 0; x = (x&(x+1))-1)
                res += fen[x];
            return res;
        }
        T query(int l, int r){
            return query(r) - query(l-1);
        }
    };
     
    ll
    count_swaps(vector<int> s)
    {
        ll ans = 0;
        for (int i = 0; i < sz(s); ++i) {
            if (s[i] > 0) pp[s[i]].push(i);
            if (s[i] < 0) np[-s[i]].push(i);
        }
     
        BIT<int> deltr(sz(s)+5);
     
        int pos;
     
        for (int i = 0; i < sz(s); ++i) {
            if (c[i]) {
                continue;
            }
            if (s[i] > 0) {
                pos = np[s[i]].front();
                ans += pos - deltr.query(i,pos) - i;
                c[pos] = 1;
                deltr.add(pos,1);
            } else {
                pos = pp[-s[i]].front() ;
                ans += pos - deltr.query(i,pos) - 1 - i;
                c[pos] = 1;
                deltr.add(pos,1);
            }
            np[abs(s[i])].pop();
            pp[abs(s[i])].pop();
        }
     
        return ans;
    }
     
    #ifdef ONPC
    void
    solve()
    {
        int n;
        cin >> n;
        vector<int> s(n);
        for (int i = 0; i < n; ++i)
            cin >> s[i];
        
        cout <<count_swaps(s) << endl;
    }
     
    int32_t
    main()
    {
        freopen("in", "r", stdin);
        int t = 1;
        /* cin >> t; */
        while(t--)
            solve();
    }
    #endif

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