Submission #811018

#	Time	Username	Problem	Language	Result	Execution time	Memory
811018		Essa2006	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	332 ms	149188 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
#include <cstdio>
#include <cassert>
using namespace std;
#define ll long long 
#define endl '\n'
#define FF firtst
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
const int pr=18, s_p=(1<<pr), e_p=(1<<(pr+1))-1;
vector<int>S;
map<int, queue<int>>mp;
void pre(){
    S.clear(), mp.clear();
    S.resize(1<<(pr+1));
}
void update(int id, int u, int v, int l, int r){
    if(l>v || r<u)
        return;
    if(l>=u && r<=v){
        S[id]++;
        return;
    }
    int md=(l+r)/2;
    update(id*2, u, v, l, md);
    update(id*2+1, u, v, md+1, r);
        
}
int get(int ind){
    ll res=S[ind];
    while(ind/=2)
        res+=S[ind];
    return res;
}
ll count_swaps(vector<int> A){
    int n=A.size();
    pre();
    ll ans=0;
    for(int i=0;i<n;i++){
        if(A[i]>0 && !mp[-A[i]].empty()){
            int u=mp[-A[i]].front();
            mp[-A[i]].pop();
            u+=get(u+s_p);
            ans+=i-u-1;
            update(1, u+1+s_p, i+s_p, s_p, e_p);
        }
        else if(A[i]<0 && !mp[-A[i]].empty()){
            int u=mp[-A[i]].front();
            mp[-A[i]].pop();
            u+=get(u+s_p);
            ans+=i-u;
            update(1, u+s_p, i+s_p, s_p, e_p);
        }
        else{
            mp[A[i]].push(i);
        }
    }
    return ans;
}
 
 
//int main() {
//	int n;
//	assert(1 == scanf("%d", &n));
//	vector<int> S(2 * n);
//	for (int i = 0; i < 2 * n; i++)
//		assert(1 == scanf("%d", &S[i]));
//	fclose(stdin);
//
//	long long result = count_swaps(S);
//
//	printf("%lld\n", result);
//	fclose(stdout);
//	return 0;
//}

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