Submission #985927

#	Time	Username	Problem	Language	Result	Execution time	Memory
985927		user736482	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	240 ms	88604 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;

//#pragma GCC optimize ("O3")

int licz[200007];
vector<int>zacz[200007];
vector<pair<int,int>>przez[200007];
vector<int>plus_[200007],minus_[200007];

void init(){
    for(int i=0;i<200007;i++){
        int ak=1;
        while(ak+i<200007 && i%ak==0){
            zacz[i].push_back(0);
            for(int j=0;j<ak;j++){
                przez[i+j].push_back({i,(int)zacz[i].size()-1});
            }
            ak*=2;
        }
        //cout<<zacz[i].size()<<" ";
    }
}
void change(int pos,int val){
    for(int i=0;i<(int)przez[pos].size();i++){
        zacz[przez[pos][i].first][przez[pos][i].second]+=val-licz[pos];
        //cout<<37<<" ";
    }
    licz[pos]=val;
}
int get(int x, int y){
    int ak=1,logarithm=0;
    int odp=0;
    y++;
    while(x!=y){
        //cout<<3;
        while(x+ak*2<=y && (int)zacz[x].size()>logarithm+1){
            ak*=2;
            logarithm++;
        }
        odp+=zacz[x][logarithm];
        x+=ak;
        while(x+ak>y){
            ak/=2;
            logarithm--;
        }
        
    }
    return odp;
}
long long count_swaps(vector<int>v){
    long long odp=0;
    for(int i=(int)v.size()-1;i>=0;i--){
        if(v[i]>0){
            plus_[v[i]].push_back(i);
        }
        else{
          //  cout<<-v[i]<<"\n";
            minus_[-v[i]].push_back(i);
        }
    }
    init();
    for(int i=0;i<(int)v.size();i++){
        if(licz[i]==1) continue;
        if(v[i]>0){
            odp++;
            odp+=minus_[v[i]][(int)minus_[v[i]].size()-1]-i-1;
           // cout<<minus_[v[i]].size();return -1;
            odp-=get(i+1,minus_[v[i]][(int)minus_[v[i]].size()-1]-1);
            change(i,1);
            change(minus_[v[i]][(int)minus_[v[i]].size()-1],1);
            plus_[v[i]].pop_back();
            minus_[v[i]].pop_back();
        }
        else{
            //return -1;
            odp+=plus_[-v[i]][(int)plus_[-v[i]].size()-1]-i-1;
            odp-=get(i+1,plus_[-v[i]][(int)plus_[-v[i]].size()-1]-1);
            change(i,1);
            change(plus_[-v[i]][(int)plus_[-v[i]].size()-1],1);
            plus_[-v[i]].pop_back();
            minus_[-v[i]].pop_back();
        }
    }
    return odp;
}
/*int main(){
    vector<int>v={1,1,-1,1,-1,-1};
    cout<<count_swaps(v);
    //init();
    //change(5,1);
    //cout<<get(0,200000);
    return 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