Submission #560214

#	Time	Username	Problem	Language	Result	Execution time	Memory
560214		jk410	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	166 ms	74160 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
typedef long long ll;
struct segtree{
    vector<int> tree;
    int init(int l,int r,int n=1){
        if (l==r)
            return tree[n]=1;
        int m=(l+r)>>1;
        return tree[n]=init(l,m,n<<1)+init(m+1,r,n<<1|1);
    }
    segtree(int n){
        tree.resize(1<<(int)ceil(log2(n))+1);
        init(1,n);
    }
    int update(int x,int v,int l,int r,int n=1){
        if (r<x||x<l)
            return tree[n];
        if (l==r)
            return tree[n]+=v;
        int m=(l+r)>>1;
        return tree[n]=update(x,v,l,m,n<<1)+update(x,v,m+1,r,n<<1|1);
    }
    int query(int lx,int rx,int l,int r,int n=1){
        if (r<lx||rx<l||lx>rx)
            return 0;
        if (lx<=l&&r<=rx)
            return tree[n];
        int m=(l+r)>>1;
        return query(lx,rx,l,m,n<<1)+query(lx,rx,m+1,r,n<<1|1);
    }
};
int N;
int S[200001],Idx[200001];
bool Used[200001];
queue<int> A[100001];
int my_abs(int x){
    if (x<0)
        return -x;
    return x;
}
ll count_swaps(vector<int> s){
    ll ans=0;
    N=(int)s.size();
    segtree *ST=new segtree(N);
    for (int i=1; i<=N; i++)
        S[i]=s[i-1];
    for (int i=1; i<=N; i++){
        int x=my_abs(S[i]);
        if (!A[x].empty()&&S[A[x].front()]+S[i]==0){
            Idx[A[x].front()]=i;
            A[x].pop();
        }
        else
            A[x].push(i);
    }
    for (int i=1; i<=N; i++){
        if (!ST->query(i,i,1,N))
            continue;
        ans+=ST->query(i+1,Idx[i]-1,1,N);
        if (S[i]>S[Idx[i]])
            ans++;
        ST->update(i,-1,1,N);
        ST->update(Idx[i],-1,1,N);
    }
    return ans;
}

Compilation message (stderr)

shoes.cpp: In constructor 'segtree::segtree(int)':
shoes.cpp:14:42: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   14 |         tree.resize(1<<(int)ceil(log2(n))+1);
      |                        ~~~~~~~~~~~~~~~~~~^~

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