Submission #268730

#	Time	Username	Problem	Language	Result	Execution time	Memory
268730		Puddlestomps	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	3 ms	2560 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
array<int, MAXN> linked;

//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);
    linked.fill(-1);

    long long total = 0;

    for(int i = 0; i < S.size(); i++)
    {
        int sn = abs(S[i]);
        if(shoes[sn] == -1)
        {
            starts[i] = S[i] > 0;
            shoes[sn] = i;
        }
        else
        {
            //cout << "SHOES[SN]: " << shoes[sn] << "\n";
            linked[shoes[sn]] = i;
            total += i - shoes[sn];
            //cout << "ADD: " << (i - shoes[sn]) << "\n";
            if(!starts[shoes[sn]])
            {
                //cout << "NOT STARTS\n";
                total--;
            }
            shoes[sn] = -1;
        }
        
        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, linked[ind]);
        //cout << "HELPS from " << ind << " to " << linked[ind] << ": " << helps << "\n";
        total -= helps;

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

/*
int main()
{
    int num;
    vector<int> vals;

    cin >> num;
    vals.resize(num);

    for(int i = 0; i < num; i++) cin >> vals[i];
    
    cout << count_swaps(vals) << "\n";

    
}*/

Compilation message (stderr)

shoes.cpp: In function 'int qry(int, int)':
shoes.cpp:31:21: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   31 |         if(left & 1 == 1)
      |                   ~~^~~~
shoes.cpp:36:22: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   36 |         if(right & 1 == 0)
      |                    ~~^~~~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i = 0; i < S.size(); i++)
      |                    ~~^~~~~~~~~~
shoes.cpp:86:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int ind = 0; ind < S.size(); ind++)
      |                      ~~~~^~~~~~~~~~
shoes.cpp:90:13: warning: unused variable 'sn' [-Wunused-variable]
   90 |         int sn = abs(S[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