Submission #533249

#	Time	Username	Problem	Language	Result	Execution time	Memory
533249		makanhulia	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	137 ms	26728 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
typedef long long ll;
using namespace std;

vector<long long> kiri[200005], kanan[200005];
vector<pair<long long,long long> > swaps;
long long tree[4 * 200005];

void upd(long long idx, long long l, long long r, long long titik, long long val){
    if(titik > r || titik < l){
        return;
    }

    if(l == r){
        tree[idx] += val;
        return;
    }

    upd(2 * idx, l, (l + r)/2, titik, val);
    upd(2 * idx + 1, (l + r)/2 + 1, r, titik, val);
    tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
}

long long cari(long long idx, long long l, long long r, long long kiri, long long kanan){
    if(kiri > r || kanan < l){
        return 0;
    }

    if(l >= kiri && r <= kanan){
        return tree[idx];
    }

    long long satu = cari(2 * idx, l, (l + r)/2, kiri, kanan);
    long long dua = cari(2 * idx + 1, (l + r)/2 + 1, r, kiri, kanan);
    return satu + dua;
}

long long count_swaps(vector<int> s) {
    long long n = s.size() / 2;
    for(long long i = 0; i < s.size(); i++){
        if(s[i] < 0){
            kiri[-s[i]].pb(i + 1);
        }else{
            kanan[s[i]].pb(i + 1);
        }    
    }

    long long ans = 0;
    for(long long i = 1; i < s.size() + 5; i++){
        for(long long j = 0; j < kiri[i].size(); j++){
            long long lef = kiri[i][j];
            long long rig = kanan[i][j];
            if(lef > rig){
                ans++;
                swap(lef, rig);
            }
            // cout << lef << " " << rig << " here\n";
            swaps.pb(mp(lef, rig));
        }
    }

    sort(swaps.begin(), swaps.end());
    memset(tree, 0, sizeof(tree));
    for(long long i = 0; i < swaps.size(); i++){
        long long l = swaps[i].first;
        long long r = swaps[i].second;
        long long ans_now = (r - l - 1) - cari(1, 1, 200000, l, r);
        ans += ans_now;
        upd(1, 1, 200000, l, 1);
        upd(1, 1, 200000, r, 1);
    }
    return ans;
}

// int main(){
//     int n; cin >> n;
//     vector<int> bawa;
//     for(int i = 0; i < n; i++){
//         int x; cin >> x;
//         bawa.pb(x);
//     }
//     cout << count_swaps(bawa) << "\n";
// }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:45:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(long long i = 0; i < s.size(); i++){
      |                          ~~^~~~~~~~~~
shoes.cpp:54:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(long long i = 1; i < s.size() + 5; i++){
      |                          ~~^~~~~~~~~~~~~~
shoes.cpp:55:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(long long j = 0; j < kiri[i].size(); j++){
      |                              ~~^~~~~~~~~~~~~~~~
shoes.cpp:69:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(long long i = 0; i < swaps.size(); i++){
      |                          ~~^~~~~~~~~~~~~~
shoes.cpp:44:15: warning: unused variable 'n' [-Wunused-variable]
   44 |     long long n = s.size() / 2;
      |               ^

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