Submission #483485

#	Time	Username	Problem	Language	Result	Execution time	Memory
483485		Bogdan1110	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1 ms	204 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#define ll long long
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ld long double
#define n_4 10010
#define n_5 100010
#define n_6 1000010
#define n_7 10000010
#define n_8 100000010
#define pii pair<int,int>
#define pll pair<long long,long long>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<ld, null_type,less<ld>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key -> # less than k
// find_by_order -> k-th element
// pq max element
const int NMAX = 20010;

ll seg[2*NMAX];
ll lejzi[2*NMAX];
ll nalaz[NMAX];
ll mikimaus[NMAX];

void update(int l, int r, int nl, int nr, int node, int value) {
    if ( l <= nl && r >= nr ) {
        lejzi[node] += value;
        return;
    }
    if ( r < nl || l > nr ) return;
    update(l, r, (nl+nr)/2+1, nr, node*2+2, value);
    update(l, r, nl, (nl+nr)/2, node*2+1, value);
}

ll pronadji(int ind, int nl, int nr, int node) {
    if ( nl == nr ) {
        seg[node] += lejzi[node];
        lejzi[node] = 0;
        return seg[node];
    }
    seg[node] += lejzi[node];
    lejzi[node*2+1] += lejzi[node];
    lejzi[node*2+2] += lejzi[node];
    lejzi[node] = 0;
    if ( ind <= (nl + nr)/2 ) {
        return pronadji(ind, nl, (nl + nr)/2, node*2+1);
    }
    else {
        return pronadji(ind, (nl + nr)/2+1, nr, node*2+2);
    }
}

ll count_swaps(vector<int>v) {
    ll N = v.size();
    unordered_map<ll,ll>m;
    for (int i = 0 ; i < N; i++ ) {
        m[v[i]] = i;
        if ( m.find(-v[i]) != m.end() ) {
            nalaz[i] = m[-v[i]];
        } 
        else nalaz[i] = -1;
    }
    for (int i = N-1; i >= 0 ; i-- ) {
        if ( nalaz[i] != -1) {
            mikimaus[nalaz[i]] = i;
        }
    }
    ll rez = 0;

    for (int i = 0 ; i < N; i++ ) {
        if (mikimaus[i] ) {
            ll r = mikimaus[i] + pronadji(mikimaus[i],0,N-1,0);
            ll l = i + pronadji(i,0,N-1,0);
            ll cnt = r-l-1;
            if ( v[i] > 0 ) cnt++;
            l = i + 1;
            r = mikimaus[i]-1;
            if ( r >= l ) {
                update(l,r,0,N-1,0,1);
            }
            rez += cnt;
        }
    }

    return rez;

}

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