Submission #158392

#	Time	Username	Problem	Language	Result	Execution time	Memory
158392		nickmet2004	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	250 ms	139192 KiB

shoes

#include<bits/stdc++.h>
//#include<shoes.h>
 
using namespace std;
 
const int NAX = 1e5 + 5;
const int l = 1e5 + 5;
 
int N;
// fenwick tree to count range sums (+0 , +1 , +2)
 
int f[2 * NAX + 1];
 
void update(int idx , int u){
    ++idx;
    while(idx <= N){
        f[idx] += u;
        idx += idx & (-idx);
    }
}
long long sum(int idx){
    long long sum = 0;
    ++idx;
    while(idx){
        sum += f[idx];
        idx -= idx & (-idx);
    }
    return sum;
}
queue<int> q[2 * NAX + 200];
 
long long count_swaps(vector<int> S){
    N = S.size();
    long long ans = 0;
    // update BIT
    for(int i = 0; i < N; ++i){
        update(i , 1);
    }
    for(int i = 0; i < N; ++i){
        int x = abs(S[i]);
        int k = S[i];
        if(!q[k + l].empty()){
            ans += (sum(i) - sum(q[k + l].front()));
            if(k > 0){
                --ans;
                update(i , -1);
                update(q[k + l].front() + 1 , 1);
                q[k + l].pop();
            } else {
                update(i , -1);
                update(q[k + l].front() , 1);
                q[k + l].pop();
            }
        } else {
            // q[k * -1 + l] because its opposite is the same as the next x
            // k * -1 + l == next_x(k + l)
            q[k * -1 + l].push(i);
        }
    }
    return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:40:13: warning: unused variable 'x' [-Wunused-variable]
         int x = abs(S[i]);
             ^

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