Submission #1238625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238625		al_reem_2010	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	299 ms	286416 KiB

shoes

// اَللَهُمَ صَلِ عَلَىَ مُحَمَدٍ وَ آلِ مُحَمَدٍ
#include "bits/stdc++.h"
#include "shoes.h"
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <thread>
#include <fstream>
#include <stack>
using namespace std ;
//#define int long long
#define pb push_back
#define si size()
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define applejuice ios::sync_with_stdio(false) ; cin.tie(nullptr) ; cout.tie(nullptr) ;
const int inf=1e9 ;
const int mod=1e9+7 ;
const int maxn=2e5+7 ;
int tt=1 , sz=1<<19 , e=0 ;
queue<int> lp[maxn] ;
queue<int> ln[maxn] ;
map<int,int> p ;
bool u[maxn] ;
long long seg[maxn*4] ;
long long op(long long l , long long r) {return l+r ;}
void build()
{
    for(int i=sz-1 ; i>0 ; i--) {seg[i]=op(seg[i*2],seg[i*2+1]) ;}
}
void update(int k)
{
    k+=sz ;
    seg[k]=0 ;
    for(k/=2 ; k>0 ; k/=2) {seg[k]=op(seg[k*2],seg[k*2+1]) ;}
}
long long get(int l , int r , int lo=0 , int hi=sz-1 , int x=1)
{
    if(hi<l || r<lo) {return e ;}
    if(l<=lo && hi<=r) {return seg[x] ;}
    int mid=(lo+hi)/2 ;
    long long segl=get(l,r,lo,mid,x*2) ;
    long long segr=get(l,r,mid+1,hi,x*2+1) ;
    return op(segl,segr) ;
}
long long count_swaps(vector<int> s)
{
    int n=(int)s.si ;
    for(int i=0 ; i<n ; i++)
    {
        if(s[i]<0 && !lp[abs(s[i])].empty())
        {
            p[lp[abs(s[i])].front()]=i ;
            p[i]=lp[abs(s[i])].front() ;
            lp[abs(s[i])].pop() ;
        }
        else if(s[i]>0 && !ln[s[i]].empty()) 
        {
            p[ln[s[i]].front()]=i ;
            p[i]=ln[s[i]].front() ;
            ln[s[i]].pop() ;
        }
        else if(s[i]<0) {ln[abs(s[i])].push(i) ;}
        else {lp[s[i]].push(i) ;}
    }
    int cnt=0 ;
    //for(int i=0 ; i<n ; i++) {cout << i << " " << p[i] << "\n" ;}
    for(int i=0 ; i<n ; i++) {seg[i+sz]=1 ;}
    //cout << get(0,n-1,1,0,n-1) << "\n" ;
    build() ;
    //update(2) ;
    //cout << get(0,sz-1,1,1) << "\n" ;
    //for(int i=0 ; i<2*sz ; i++) {cout <<i << " "<< seg[i] << "\n" ;}
    for(int i=n-1 ; i>=0 ; i--)
    {
        if(u[i]) {continue ;}
        if(p[i]+1!=i) 
        {
            long long v=get(p[i]+1,i-1) ;
            //cout << v << "\n" ;
            cnt+=v ;
        }
        if(s[i]<0) {cnt+=1 ;}
        //cout << cnt << " " << i <<"\n" ;
        update(p[i]) ;
        u[i]=u[p[i]]=1 ;
    }
    return cnt ;
}
/*signed main()
{
    //wrong
    applejuice ;
    //cin >> tt ;
    //while(tt--) {solve() ;}
    int n ;
    cin >> n ;
    vector<int> a(n*2) ;
    for(int i=0 ; i<n*2 ; i++) {cin >> a[i] ;}
    cout << count_swaps(a) ;
}*/
/*
 4
 2 1 -2 -2 3 -1 2 -3
 */

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