Submission #1238820

#TimeUsernameProblemLanguageResultExecution timeMemory
1238820em4ma2Boxes with souvenirs (IOI15_boxes)C++20
Compilation error
0 ms0 KiB
#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 (ll)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+1];
    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+1);
    //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 && a[p[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;
}

Compilation message (stderr)

boxes.cpp:2:10: fatal error: shoes.h: No such file or directory
    2 | #include "shoes.h"
      |          ^~~~~~~~~
compilation terminated.