Submission #573403

#	Time	Username	Problem	Language	Result	Execution time	Memory
573403		Lobo	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	259 ms	274048 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 2e5+10;

int n, bit[maxn];
queue<int> vl[maxn], vr[maxn];

void att(int pos, int val) {
    for(int i = pos; i <= n; i+= i&-i) {
        bit[i]+= val;
    }
}

int qrr(int pos) {
    int val = 0;
    for(int i = pos; i > 0; i-= i&-i) {
        val+= bit[i];
    }
    return val;
}

long long count_swaps(vector<int32_t> s) {
    n = s.size();
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        int tp = s[i-1];

        if(tp < 0) {
            tp*=-1;
            if(vr[tp].size()) {
                //manda ele para vr[tp].back()
                int pos = vr[tp].front(); vr[tp].pop();
                ans+= qrr(i)-qrr(pos-1);
                // cout << tp << " 1 " << qrr(i)-qrr(pos-1) << endl;
                att(pos,+1);
            }
            else {
                vl[tp].push(i);
                att(i,+1);
            }
        }
        else {
            if(vl[tp].size()) {
                //manda ele para vl[tp].back()+1
                int pos = vl[tp].front(); vl[tp].pop();
                ans+= qrr(i)-qrr(pos);
                // cout << tp << " 2 " << qrr(i)-qrr(pos) << endl;
                att(pos,+1);
            }
            else {
                vr[tp].push(i);
                att(i,+1);
            }
        }
    }
    return ans;
}

// int32_t main() {
//     ios::sync_with_stdio(false); cin.tie(0);

//     freopen("in.in", "r", stdin);
//     int32_t N;
//     assert(1 == scanf("%d", &N));
//     vector<int32_t> S(2 * N);
//     for (int i = 0; i < 2 * N; i++)
//         assert(1 == scanf("%d", &S[i]));
//     fclose(stdin);

//     long long result = count_swaps(S);

//     printf("%lld\n", result);
//     return 0;

// }

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