Submission #268729

#	Time	Username	Problem	Language	Result	Execution time	Memory
268729		Puddlestomps	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	2 ms	2048 KiB

shoes

#include "bits/stdc++.h"

using namespace std;

constexpr int MAXN = 1 << 17;
array<int, MAXN * 2> segTree;
array<int, MAXN> shoes;
array<bool, MAXN> starts; // true if swapped

//pos goes from 0
void put(int pos, int val)
{
    pos += MAXN;
    int diff = val - segTree[pos];
    while(pos > 0)
    {
        segTree[pos] += diff;
        pos = pos >> 1;
    }
}

//pos from 0, inclusive
int qry(int left, int right)
{
    int total = 0;
    left += MAXN;
    right += MAXN;
    while(left < right)
    {
        if(left & 1 == 1)
        {
            total += segTree[left];
            left++;
        }
        if(right & 1 == 0)
        {
            total += segTree[right];
            right--;
        }
        left = left >> 1;
        right = right >> 1;
    }

    if(left == right) total += segTree[left];

    return total;
}

long long count_swaps(vector<int> S)
{
    segTree.fill(0);
    starts.fill(false);
    shoes.fill(-1);

    long long total = 0;

    for(int i = 0; i < S.size(); i++)
    {
        int sn = abs(S[i]);
        if(shoes[sn] == -1)
        {
            starts[sn] = S[i] > 0;
        }
        else
        {
            total += i - shoes[sn];
            //cout << "ADD: " << (i - shoes[sn]) << "\n";
            if(!starts[sn])
            {
                //cout << "NOT STARTS\n";
                total--;
            }
        }
        
        shoes[sn] = i;
        put(i, S[i] < 0 ? 1 : -1);
    }

    //cout << "TOTAL PRE PROCESS: " << total << "\n";

    for(int ind = 0; ind < S.size(); ind++)
    {
        if(segTree[MAXN + ind] == 0) continue;

        int sn = abs(S[ind]);

        int helps = qry(ind, shoes[sn]);
        //cout << "HELPS from " << ind << " to " << shoes[sn] << ": " << helps << "\n";
        total -= helps;

        put(ind, 0);
        put(shoes[sn], 0);
    }
    
    return total;
}

/*
int main()
{
    cout << count_swaps({2, 1, -1, -2}) << "\n";

    
}*/

Compilation message (stderr)

shoes.cpp: In function 'int qry(int, int)':
shoes.cpp:30:21: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   30 |         if(left & 1 == 1)
      |                   ~~^~~~
shoes.cpp:35:22: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   35 |         if(right & 1 == 0)
      |                    ~~^~~~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i = 0; i < S.size(); i++)
      |                    ~~^~~~~~~~~~
shoes.cpp:81:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int ind = 0; ind < S.size(); ind++)
      |                      ~~~~^~~~~~~~~~

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