Submission #1238814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238814		ayathk	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	0 ms	328 KiB

shoes

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

#define pb push_back
#define ll long long

const ll inf=1e9+4;
const ll off=(1<<19);

ll tr[off*2];

ll op(ll trl,ll trr){
    return trl+trr;
}

void upd(ll i,ll v){
    i+=off;
    tr[i]=v;
    while (i/=2){
        ll xl=i*2,xr=xl+1;
        tr[i]=op(tr[xl],tr[xr]);
    }
}

ll query(ll ql,ll qr,ll l=0,ll r=off-1,ll x=1){
    if (ql<=l && r<=qr)return tr[x];
    if (l>qr || r<ql)return 0;
    ll mid=(l+r)/2;
    ll xl=x*2,xr=xl+1;
    ll trl=query(ql,qr,l,mid,xl),trr=query(ql,qr,mid+1,r,xr);
    return op(trl,trr);
}

ll count_swaps(vector<int>a){
    ll n=a.size();
    ll us[n];
    for (int i=0;i<n;i++){
        upd(i,1);
        us[i]=1;
    }
    queue<ll>adp[n+1];
    queue<ll>adn[n+1];
    vector<ll>p(n);
    //cout<<"DSFI";
    for (int i=0;i<n;i++){
        if (a[i]>0){
            if (adn[abs(a[i])].size()){
                p[i]=(adn[abs(a[i])].front());
                p[adn[abs(a[i])].front()]=(i);
                adn[abs(a[i])].pop();
            }else{
                adp[a[i]].push(i);
            }
        }
        else{
            //cout<<'d';
            if (adp[abs(a[i])].size()){
                p[i]=(adp[abs(a[i])].front());
                p[adp[abs(a[i])].front()]=(i);
                adp[abs(a[i])].pop();
            }else{
                //cout<<i<<endl;
                adn[abs(a[i])].push(i);
            }
        }
    }
    // for (int i=0;i<n;i++){
    //     cout<<p[i]<<" ";
    // }cout<<endl;
    ll sum=0;
    for (int i=n-1;i>=0;i--){
        if (!us[i])continue;
        // for (auto x:us){
        //     cout<<x<<" ";
        // }cout<<endl;
        ll r=i-1,l=p[i]+1;
        //cout<<l<<" "<<r<<endl;
        if (l<r){
            ll x=query(l,r);
            sum+=x;
            //cout<<x<<endl;
        }
        upd(i,0);
        upd(p[i],0);
        us[i]=0,us[p[i]]=0;
        if (a[i]<0)sum++;
        //cout<<sum<<" ";
    }
    return sum;
}

// 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