Submission #145115

#	Time	Username	Problem	Language	Result	Execution time	Memory
145115		JovanK26	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	34 ms	4472 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
int pos[100001];
int lazy[400001];
int tree[400001];
void build(int start,int l,int r)
{
    if(l==r)
    {
        tree[start]=pos[l];
        return;
    }
    int m=(l+r)/2;
    build(2*start+1,l,m);
    build(2*start+2,m+1,r);
    tree[start]=tree[2*start+1]+tree[2*start+2];
}
void update(int start,int i,int j,int l,int r,int val)
{
    if(lazy[start]!=0)
    {
        tree[start]+=(r-l+1)*val;
        if(l!=r)
        {
            lazy[2*start+1]+=lazy[start];
            lazy[2*start+2]+=lazy[start];
        }
        lazy[start]=0;
    }
    if(l>r || l>j || r<i)return;
    if(l>=i && r<=j)
    {
        tree[start]+=(r-l+1)*val;
        if(l!=r)
        {
            lazy[2*start+1]+=val;
            lazy[2*start+2]+=val;
        }
        return;
    }
    int m=(l+r)/2;
    update(2*start+1,i,j,l,m,val);
    update(2*start+2,i,j,m+1,r,val);
    tree[start]=tree[2*start+1]+tree[2*start+2];
}
int query(int start,int i,int j,int l,int r)
{
    if(lazy[start]!=0)
    {
        tree[start]+=(r-l+1)*lazy[start];
        if(l!=r)
        {
            lazy[2*start+1]+=lazy[start];
            lazy[2*start+2]+=lazy[start];
        }
        lazy[start]=0;
    }
    if(l>r || l>j || r<i)return 0;
    if(l>=i && r<=j)return tree[start];
    int m=(l+r)/2;
    int q1=query(2*start+1,i,j,l,m);
    int q2=query(2*start+2,i,j,m+1,r);
    return q1+q2;
}
long long count_swaps(vector<int> s)
{
    long long rez=0;
	int n=s.size();
	for(int i=0;i<n;i++)
    {
        pos[i]=i;
    }
    build(0,0,n-1);
    for(int i=0;i<n;i+=2)
    {
       for(int j=i+1;j<n;j++)
       {
           int pos1=query(0,i,i,0,n-1);
           int pos2=query(0,j,j,0,n-1);
           if(abs(s[pos1])==abs(s[pos2]) && s[pos1]*s[pos2]<0)
           {
               rez+=(pos2-pos1-1);
               update(0,0,n-1,pos1+2,pos2,-1);
               update(0,0,n-1,pos1+1,pos1+1,(pos2-pos1-1));
               if(s[pos2]<0)
               {
                   update(0,0,n-1,pos1+1,pos1+1,-1);
                   update(0,0,n-1,pos1,pos1,1);
                   rez++;
               }
               break;
           }
       }
    }
    return rez;
}

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