Submission #678085

#	Time	Username	Problem	Language	Result	Execution time	Memory
678085		irmuun	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	132 ms	20336 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];
            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){
    ll ans=0;
    ll n=s.size()/2;
    vector<int>vec(2*n,1);
    segtree sg(vec);
    ll cur[n+5];
    fill(cur,cur+n+1,0);
    vector<int>r[n+5];
    vector<int>l[n+5];
    for(ll i=0;i<s.size();i++){
        if(s[i]>=0){
            r[s[i]].pb(i);
        }
        else{
            l[-s[i]].pb(i);
        }
    }
    int check[2*n+5];
    fill(check,check+2*n+1,0);
    for(int i=0;i<2*n;i++){
        if(check[i]==0){
            int pr;
            if(s[i]>0){
                ans++;
                pr=l[s[i]][cur[abs(s[i])]];
            }
            else{
                pr=r[-s[i]][cur[abs(s[i])]];
            }
            cur[abs(s[i])]++;
            check[i]=1;
            check[pr]=1;
            int add=sg.query(1,0,2*n-1,i+1,pr-1);
            ans+=add;
            sg.update(1,0,2*n-1,i,0);
            sg.update(1,0,2*n-1,pr,0);
        }
    }
    return ans;
}

Compilation message (stderr)

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

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