Submission #334256

#	Time	Username	Problem	Language	Result	Execution time	Memory
334256		bigDuck	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	179 ms	139768 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount




int fw[200010];
queue<int> l[100010], r[100010];


void update(int i, int x){
    for(int j=(200000-i+1); j<=200000; j+=(j&(-j))){
        fw[j]+=x;
    }
}

int query(int i){
    int res=0;
    for(int j=(200000-i+1); j>0; j-=(j&(-j))){
        res+=fw[j];
    }
    return res;
}

bool v[200010];

long long count_swaps(std::vector<int> s) {



int n=s.size()/2;



for(int i=0; i<2*n; i++){
    if(s[i]<0){
        l[-s[i] ].push(i+1);
    }
    else{
        r[s[i] ].push(i+1);
    }
}

ll res=0;
int p1=1;
for(int i=1; i<=n; i++){
    while(v[p1]==true){p1++;}
    v[p1]=true;
    int p=p1;
    int c=s[p-1];
    p+=query(p);
    if(c<0){
        int j=r[-c].front();
        v[j]=true;
        update(j, 1);
        j+=query(j);
        l[-c].pop();
        r[-c].pop();
        res+=j-p-2;
    }
    else{
        int j=l[c].front();
        v[j]=true;
        update(j, 1);
        j+=query(j);
        l[c].pop();
        r[c].pop();
        res+=j-p-1;
    }
}

return res;
}

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