제출 #408730

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
408730		idk321	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	118 ms	12376 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

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

void ins(int num, int i, int a, int b, int node)
{
    if (a == b)
    {
        tree[node] = num;
        return;
    }

    int mid = (a + b) / 2;
    if (i <= mid) ins(num, i, a, mid, node * 2);
    if (i > mid) ins(num,i ,mid + 1, b, node * 2 + 1);

    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

int getSum(int from, int to, int a, int b, int node)
{
    if (from <= a && b <= to) return tree[node];

    int mid = (a + b) / 2;
    int res = 0;
    if (from <= mid) res += getSum(from, to, a, mid, node * 2);
    if (to > mid) res += getSum(from, to, mid + 1, b, node * 2+ 1);

    return res;
}



long long count_swaps(std::vector<int> s) {
    n = s.size() / 2;
    vector<vector<int>> isAt(n + 1);
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] < 0) isAt[abs(s[i])].push_back(i);
    }

    vector<int> match(s.size());
    for (int i = s.size() - 1; i >= 0; i--)
    {
        if (s[i] > 0)
        {
            match[i] = isAt[s[i]].back();
            match[isAt[s[i]].back()] = i;
            isAt[s[i]].pop_back();

        }
    }

    ll res = 0;

    vector<int> sumRight(2 * n + 1);
    for (int i = 1; i <= 2 * n; i++)
    {

        if (s[i - 1] > 0)sumRight[i]++;
        sumRight[i] += sumRight[i - 1];
    }



    for (int i = 0; i < 2 * n; i++)
    {

        if (s[i] < 0)
        {
            if (match[i] > i)
            {
                res += sumRight[match[i]] - sumRight[i];
            } else
            {
                res += sumRight[i] - sumRight[match[i]];
            }
        }
    }




    for (int i = 0; i < 2 * n; i++)
    {

        if (s[i] < 0)
        {
            if (match[i] < i) res += getSum(match[i], i, 0, N - 1, 1);
            else
            {
                ins(1, i, 0, N - 1, 1);

            }
        } else if (match[i] < i)
        {
            ins(0, match[i], 0, N - 1, 1);
            ins(1, i, 0, N - 1, 1);
        }
    }

    for (int i = 0; i < 4 * N; i++) tree[i] = 0;

    for (int i = 0; i < 2 * n; i++)
    {
        if (s[i] < 0 && match[i] > i)
        {
            res += getSum(match[i], N - 1, 0, N - 1, 1);
            ins(1, match[i], 0, N - 1, 1);
        }
    }

    for (int i = 0; i < 4 * N; i++) tree[i] = 0;

    for (int i = 2 * n - 1; i >= 0; i--)
    {
        if (s[i] < 0 && match[i] < i)
        {
            res += getSum(0, match[i], 0, N - 1, 1);
            ins(1, match[i], 0, N - 1, 1);
        }
    }

	return res;
}

/*
3
3 2 -3 3 -2 -3
*/

컴파일 시 표준 에러 (stderr) 메시지

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < s.size(); i++)
      |                     ~~^~~~~~~~~~

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