Submission #707733

#	Time	Username	Problem	Language	Result	Execution time	Memory
707733		Urvuk3	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	120 ms	23576 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int INF=1e9;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define PRINT(x) cerr<<#x<<'='<<x<<endl;
#define pb push_back
#define PRINTvec(niz) { cerr<<#niz<<"="; for(auto _i:niz) cerr<<_i<<" "; cerr<<endl; }

int mxN=2e5+1;

vector<int> seg(4*mxN+1);
vector<vector<int>> l(mxN),r(mxN);

void Init(int node,int l,int r){
    if(l==r){
        seg[node]=1;
        return;
    }
    Init(2*node,l,mid); Init(2*node+1,mid+1,r);
    seg[node]=seg[2*node]+seg[2*node+1];
}

void Update(int node,int l,int r,int idx,int val){
    if(idx>r) return;
    if(l==r){
        seg[node]+=val;
        return;
    }
    if(idx<=mid) Update(2*node,l,mid,idx,val);
    else Update(2*node+1,mid+1,r,idx,val);
    seg[node]=seg[2*node]+seg[2*node+1];
}

int Query(int node,int l,int r,int L,int R){
    if(L<=l && r<=R) return seg[node];
    int ret=0;
    if(L<=mid) ret+=Query(2*node,l,mid,L,R);
    if(R>mid) ret+=Query(2*node+1,mid+1,r,L,R);
    return ret;
}

long long count_swaps(vector<int> a){
    int N=sz(a)/2;
    for(int i=0;i<2*N;i++){
        if(a[i]<0) l[-a[i]].pb(i+1);
        else r[a[i]].pb(i+1);
    }
    vector<pair<pii,int>> parovi;
    for(int i=1;i<mxN;i++){
        for(int j=0;j<sz(l[i]);j++){
            int L=l[i][j],R=r[i][j];
            parovi.pb({{min(L,R),max(L,R)},L>R});
        }
    }
    sort(all(parovi));
    ll res=0;
    Init(1,1,2*N);
    for(auto p:parovi){
        int L=p.fi.fi,R=p.fi.se,x=p.se;
        //PRINT(L); PRINT(R); PRINT(x);
        //PRINT(Query(1,1,2*N,1,R));
        //PRINT(Query(1,1,2*N,1,L));
        res+=abs(Query(1,1,2*N,1,R)-Query(1,1,2*N,1,L))-1+x;
        //PRINT(res);
        Update(1,1,2*N,L+1,1);
        Update(1,1,2*N,R,-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