Submission #991365

#	Time	Username	Problem	Language	Result	Execution time	Memory
991365		MarwenElarbi	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	456 ms	149460 KiB

shoes

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
const int nax=200005;
int segtree[4*nax];
void update(int pos,int l,int r,int left,int right){
    if(l>r||l>right||r<left) return;
    if(l>=left&&r<=right){
        segtree[pos]++;
        return;
    }
    int mid=(r+l)/2;
    update(pos*2+1,l,mid,left,right);
    update(pos*2+2,mid+1,r,left,right);
    return;
}
int query(int pos,int l,int r,int idx){
    if(l==r) return segtree[pos];
    int mid=(r+l)/2;
    if(idx<= mid) return segtree[pos]+query(pos*2+1,l,mid,idx);
    else return segtree[pos]+query(pos*2+2,mid+1,r,idx);
}
long long count_swaps(std::vector<int> s) {
    int n=s.size();
    map<int,queue<int>> mp;
    bool vis[n];
    memset(vis,0,sizeof vis);
    for (int i = 0; i < n; ++i)
    {
        mp[s[i]].push(i);
    }
    long long ans=0;
    int cur=0;
    for (int i = 0; i < n; ++i)
    {
        if(vis[i]) continue;
        auto u=mp[-s[i]].front();
        mp[-s[i]].pop();
        mp[s[i]].pop();
        vis[i]=vis[u]=true;
        int x=query(0,0,n-1,i);
        int y=query(0,0,n-1,u);
        if(s[i]<=0&&u+y==i+x+1){
            continue;
        }
        //cout <<x+i<<" "<<y+u<<endl;
        ans+=(y+u-x-i-1)+(s[i]>0);
        update(0,0,n-1,i,u);
        //cout <<ans<<endl;
    }
    return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:36:9: warning: unused variable 'cur' [-Wunused-variable]
   36 |     int cur=0;
      |         ^~~

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