Submission #870763

#	Time	Username	Problem	Language	Result	Execution time	Memory
870763		LTTrungCHL	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	321 ms	283888 KiB

shoes

///***LTT***///
/// ->NHAT QUOC GIA<- ///
#include<bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
//#define int long long
#define endl "\n"
#define F first
#define S second
#define pb push_back
using namespace std;
const long long oo = 1e9+7;
const int N = 2 * 1e5 + 10;
long long tree[N * 4], lazy[N * 4];
int a[N];
queue <int> am[N];
int n;

queue <int> duong[N];
void down(int id,int l,int r){
    if (l != r){
        tree[id * 2] += lazy[id];
        tree[id * 2 + 1] += lazy[id];
        lazy[id * 2 + 1] += lazy[id];
        lazy[id * 2] += lazy[id];
    }
    lazy[id] = 0;
    return;
}
void update(int id,int l,int r,int u,int v,int val){
    if (lazy[id]){
        down(id,l,r);
    }
    if (l > v or r < u) return;
    if (l >= u and r <= v){
        tree[id] += val;
        lazy[id] += val;
        return;
    }
    int mid = (l + r)/2;
    update(id * 2,l, mid,u,v,val);
    update(id * 2 + 1,mid + 1, r,u,v,val);
    return;
}
long long get(int id,int l,int r,int u){
    if (lazy[id]){
        down(id,l,r);
    }
    if (l > u or r < u) return 0;
    if (l == u and r == u){
        return tree[id];
    }
    int mid = (l + r)/2;
    return get(id * 2, l, mid, u) + get(id * 2 + 1,mid + 1, r, u);
}

long long count_swaps(vector <int> S){
    n = S.size();
    for (int i = 1;i <= n;i++){
        a[i] = S[i - 1];
        update(1,1,n,i,i,i);
    }
    for (int i = 1;i <= n;i++){
        if (a[i] < 0) am[-a[i]].push(i);
        if (a[i] > 0) duong[a[i]].push(i);
    }
    long long ans = 0;

    for (int i = 1;i <= n;i++){
        long long pos = get(1,1,n,i);
        if (pos >= oo) continue;

        if (a[i] > 0){
            duong[a[i]].pop();
            int nxt = am[a[i]].front();
            am[a[i]].pop();
            ans += get(1,1,n,nxt) - pos;
            if (i + 1 <= nxt - 1){
                update(1,1,n,i + 1, nxt - 1,1);
            }
            update(1,1,n,nxt,nxt,oo);
        } else {
            am[-a[i]].pop();
            int nxt = duong[-a[i]].front();
            duong[-a[i]].pop();
            ans += (get(1,1,n,nxt) - pos- 1);
            if (i + 1 <= nxt - 1){
                update(1,1,n,i + 1, nxt - 1,1);
            }
            update(1,1,n,nxt,nxt,oo);
        }
    }
    return ans;
}

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