Submission #143274

#	Time	Username	Problem	Language	Result	Execution time	Memory
143274		Bench0310	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	405 ms	142444 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

const int N=200005;
int tree[4*N];
int lazy[4*N];

void push(int idx)
{
    tree[2*idx]+=lazy[idx];
    lazy[2*idx]+=lazy[idx];
    tree[2*idx+1]+=lazy[idx];
    lazy[2*idx+1]+=lazy[idx];
    lazy[idx]=0;
}

void update(int idx,int l,int r,int ql,int qr,int val)
{
    if(ql>qr) return;
    if(l==ql&&r==qr)
    {
        tree[idx]+=val;
        lazy[idx]+=val;
    }
    else
    {
        push(idx);
        int m=(l+r)/2;
        update(2*idx,l,m,ql,min(qr,m),val);
        update(2*idx+1,m+1,r,max(ql,m+1),qr,val);
        tree[idx]=min(tree[2*idx],tree[2*idx+1]);
    }
}

int query(int idx,int l,int r,int pos)
{
    if(l==r) return tree[idx];
    push(idx);
    int m=(l+r)/2;
    if(pos<=m) return query(2*idx,l,m,pos);
    else return query(2*idx+1,m+1,r,pos);
}

long long count_swaps(vector<int> temp)
{
    int n=temp.size()/2;
    vector<int> s={0};
    for(int i=0;i<2*n;i++) s.push_back(temp[i]);
    for(int i=1;i<=2*n;i++) update(1,1,2*n,i,i,i);
    vector<bool> vis(2*n+1,0);
    queue<int> q[2*n+2]; //left: 2*i, right: 2*i+1
    for(int i=1;i<=2*n;i++)
    {
        if(s[i]<0) q[-2*s[i]].push(i);
        else q[2*s[i]+1].push(i);
    }
    long long res=0;
    for(int o=1;o<=2*n;o++)
    {
        //cout << "in " << o << endl;
        if(vis[o]) continue;
        //cout << "shoe: " << s[o] << endl;
        if(s[o]<0)
        {
            q[-2*s[o]].pop();
            //cout << "left shoe" << endl;
            int pos=q[-2*s[o]+1].front();
            //cout << "position of closest pair: " << pos << endl;
            q[-2*s[o]+1].pop();
            int one=query(1,1,2*n,o);
            int two=query(1,1,2*n,pos);
            //cout << "actual position of first: " << one << endl;
            //cout << "actual position of second: " << two << endl;
            vis[pos]=1;
            res+=((long long)(two-(one+1)));
            update(1,1,2*n,o+1,pos-1,1);
            //update(1,1,2*n,pos,pos,o+1);
        }
        else
        {
            q[2*s[o]+1].pop();
            //cout << "right shoe" << endl;
            int pos=q[2*s[o]].front();
            //cout << "position of closest pair: " << pos << endl;
            q[2*s[o]].pop();
            int one=query(1,1,2*n,o);
            int two=query(1,1,2*n,pos);
            //cout << "actual position of first: " << one << endl;
            //cout << "actual position of second: " << two << endl;
            vis[pos]=1;
            res+=((long long)two-one);
            update(1,1,2*n,o+1,pos-1,1);
            //update(1,1,2*n,pos,pos,o);
        }
        //cout << "res is now " << res << endl;
    }
    return res;
}

/*int main()
{
    cout << count_swaps({2, 1, -1, -2});
    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