Submission #667000

#	Time	Username	Problem	Language	Result	Execution time	Memory
667000		irmuun	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1 ms	300 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#define ll long long
#define pb push_back
struct segtree{
    int n;
    vector<int>d;
    vector<int>u;
    segtree(vector<int>v){
        n=v.size();
        u=v;
        d.resize(4*n);
        build(1,0,n-1);
    }
    void build(int node,int l,int r){
        if(l==r){
            d[node]=u[l-1];
            return;
        }
        int mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        d[node]=d[node*2],d[node*2+1];
    }
    int query(int node,int l,int r,int L,int R){
        if(L > r || R < l || L > R){
            return 0;
        }
        if(L <= l && r <= R){
            return d[node];
        }
        int mid=(l+r)/2;
        return query(node*2,l,mid,L,R)+query(node*2+1,mid+1,r,L,R);
    }   
    void update(int node,int l,int r,int k,int val){
        if(l>k || r<k)return;
        if(l==r){
            d[node]=val;
            return;
        }
        int mid=(l+r)/2;
        update(node*2,l,mid,k,val);
        update(node*2+1,mid+1,r,k,val);
        d[node]=d[node*2]+d[node*2+1];
    }
};
long long count_swaps(vector<int>s){
    vector<int>s1=s;
    int n=s.size()/2;//number of pair
    vector<int>pos[n+5];//add
    vector<int>neg[n+5];
    for(int i=0;i<2*n;i++){
        if(s[i]<0){
            neg[-s[i]].pb(i);
        }
        else{
            pos[s[i]].pb(i);
        }
    }
    int cur=0;
    long long ans=0;
    vector<int>a(2*n);
    for(int i=1;i<=n;i++){
        for(int j=0;j<pos[i].size();j++){
            cur++;
            if(pos[i][j]<neg[i][j]){
                ans++;
            }
            a[min(pos[i][j],neg[i][j])]=cur;
            a[max(pos[i][j],neg[i][j])]=cur;
        }
    }
    vector<int>fi,se;
    fi.resize(2*n);
    se.resize(2*n);
    int l[n+5],r[n+5];
    fill(l+1,l+n+1,-1);
    for(int i=0;i<2*n;i++){
        if(l[a[i]]==-1){
            l[a[i]]=i;
            fi[i]=1;
        }
        else{
            r[a[i]]=i;
            se[i]=1;
        }
    }
    segtree sg1(fi);
    segtree sg2(se);
    for(int i=0;i<2*n;i++){
        if(l[a[i]]==-1){
            continue;
        }
        ans+=sg1.query(1,0,2*n-1,l[a[i]],r[a[i]]);
        ans-=sg2.query(1,0,2*n-1,l[a[i]],r[a[i]]);
        sg1.update(1,0,2*n-1,l[a[i]],0);
        sg2.update(1,0,2*n-1,r[a[i]],0);
        l[a[i]]=-1;
    }
    return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int j=0;j<pos[i].size();j++){
      |                     ~^~~~~~~~~~~~~~

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