Submission #532671

#	Time	Username	Problem	Language	Result	Execution time	Memory
532671		andecaandeci	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	208 ms	141312 KiB

shoes

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 2e5;
const int nosus = 1e5;

queue<int>q[N + 5];
int node[4*N + 5];

void update(int l, int r, int i, int pos, int val){
    if(l == r){
        node[i] = val;
        return;
    }
 
    int m = (l + r)/2;

    if(pos <= m)
        update(l, m, 2*i, pos, val);
    
    else
        update(m+1, r, 2*i+1, pos, val);
    
    node[i] = node[2*i] + node[2*i+1];
}

ll query(int l, int r, int i, int from, int to){
    if(l > to || r < from) 
        return 0;
    
    if(l >= from && r <= to)
        return node[i];
    
    int m = (l + r)/2;
 
    return (
        query(l, m, 2*i, from, to) +
        query(m+1, r, 2*i + 1, from, to)
    );
}
 
ll count_swaps(vector<int>v){
    memset(node, 0, sizeof(node));
    int n = v.size();
    ll ans = 0;

    for(int i = 0; i < n; i++){
        int now = -v[i] + nosus;
        if(!q[now].empty()){
            int l = q[now].front();
            q[now].pop();
            ans += (i - l);
            ans -= (v[i] > 0);
            ans -= query(0, n - 1, 1, l + 1, i);
            update(0, n - 1, 1, l, 0);
        } else{
            q[v[i] + nosus].push(i);
            update(0, n - 1, 1, i, 1);
        }
    }

    return ans;
}

// int main(){
//     int n; cin >> n;
//     vector<int>v(n);

//     for(int i = 0; i < n; i++) cin >> v[i];

//     cout << count_swaps(v) << endl;

//     return 0;
// }

//-1 -2 -3 -4 1 2 3 4

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