Submission #1035646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035646		Abito	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	220 ms	83784 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define elif else if
#define ep insert
#define F first
#define S second
using namespace std;
const int N=3e5+5;
int a[N],n;
bool vis[N];
vector<int> seg[4*N+5],b[N];
set<int> s[N];
void build(int x,int l,int r){
    if (l==r){
        for (auto u:b[l]) seg[x].pb(u);
        sort(seg[x].begin(),seg[x].end());
        return;
    }
    int mid=(l+r)/2;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    int i=0,j=0;
    while (i<seg[x*2].size() && j<seg[x*2+1].size()){
        if (seg[x*2][i]<seg[x*2+1][j]) seg[x].pb(seg[x*2][i++]);
        else seg[x].pb(seg[x*2+1][j++]);
    }
    while (i<seg[x*2].size()) seg[x].pb(seg[x*2][i++]);
    while (j<seg[x*2+1].size()) seg[x].pb(seg[x*2+1][j++]);
    return;
}
int sum(int x,int l,int r,int lx,int rx){
    if (l>=lx && r<=rx) return seg[x].size();
    if (l>rx || r<lx) return 0;
    int mid=(l+r)/2;
    return sum(x*2,l,mid,lx,rx)+sum(x*2+1,mid+1,r,lx,rx);
}
int query(int x,int l,int r,int lx,int rx,int v){
    //cout<<x<<' '<<l<<' '<<r<<endl;
    if (l>rx || r<lx) return 0;
    if (l>=lx && r<=rx){
        int L=0,R=(int)seg[x].size()-1,mid,ansx=0;
        while (L<=R){
            mid=(L+R)/2;
            if (seg[x][mid]>v){
                ansx=seg[x].size()-mid;
                R=mid-1;
            }else L=mid+1;
        }
        //cout<<ansx<<endl;
        return ansx;
    }
    int mid=(l+r)/2;
    return query(x*2,l,mid,lx,rx,v)+query(x*2+1,mid+1,r,lx,rx,v);
}
int count_swaps(vector<int32_t> v){
    n=v.size();
    for (int i=1;i<=n;i++){
        a[i]=v[i-1];
        if (a[i]>0) s[a[i]].ep(i);
    }
    vector<pair<int,int>> c;
    for (int i=1;i<=n;i++){
        if (vis[i] || a[i]>0) continue;
        int j=*s[-a[i]].begin();
        s[-a[i]].erase(s[-a[i]].begin());
        c.pb({i,j});
    }
    int ans=0;
    for (auto u:c){
        ans+=u.F+u.S-bool(u.F<u.S);
        //cout<<u.F<<' '<<u.S<<endl;
        b[min(u.F,u.S)].pb(max(u.F,u.S));
    }
    /*for (int i=1;i<=n;i++){
        for (auto u:b[i]) cout<<u<<' ';
        cout<<endl;
    }*/
    build(1,1,n);
    ans-=n/2*(n/2+1);
    //query(1,1,n,1,2,2);
    for (auto u:c){
        //cout<<u.F<<' '<<u.S<<' '<<sum(1,1,n,max(u.F,u.S)+1,n)<<' '<<query(1,1,n,min(u.F,u.S)+1,n,max(u.F,u.S))<<endl;
        ans-=2*sum(1,1,n,max(u.F,u.S)+1,n);
        ans-=query(1,1,n,min(u.F,u.S)+1,max(u.F,u.S),max(u.F,u.S));
    }
    return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'void build(long long int, long long int, long long int)':
shoes.cpp:25:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     while (i<seg[x*2].size() && j<seg[x*2+1].size()){
      |            ~^~~~~~~~~~~~~~~~
shoes.cpp:25:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     while (i<seg[x*2].size() && j<seg[x*2+1].size()){
      |                                 ~^~~~~~~~~~~~~~~~~~
shoes.cpp:29:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while (i<seg[x*2].size()) seg[x].pb(seg[x*2][i++]);
      |            ~^~~~~~~~~~~~~~~~
shoes.cpp:30:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     while (j<seg[x*2+1].size()) seg[x].pb(seg[x*2+1][j++]);
      |            ~^~~~~~~~~~~~~~~~~~

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