oj.uz

답안 #268729

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
268729 2020-08-16T21:39:51 Z Puddlestomps Arranging Shoes (IOI19_shoes) C++14
10 / 100
 2 ms 2048 KB 
#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

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Correct 2 ms 1920 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Correct 2 ms 1920 KB Output is correct
3 Correct 2 ms 1920 KB Output is correct
4 Correct 2 ms 1920 KB Output is correct
5 Correct 2 ms 1920 KB Output is correct
6 Correct 2 ms 2048 KB Output is correct
7 Incorrect 2 ms 1920 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Correct 2 ms 1920 KB Output is correct
3 Correct 2 ms 1920 KB Output is correct
4 Incorrect 2 ms 1920 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Incorrect 2 ms 1920 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Correct 2 ms 1920 KB Output is correct
3 Correct 2 ms 1920 KB Output is correct
4 Correct 2 ms 1920 KB Output is correct
5 Correct 2 ms 1920 KB Output is correct
6 Correct 2 ms 2048 KB Output is correct
7 Incorrect 2 ms 1920 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Correct 2 ms 1920 KB Output is correct
3 Correct 2 ms 1920 KB Output is correct
4 Correct 2 ms 1920 KB Output is correct
5 Correct 2 ms 1920 KB Output is correct
6 Correct 2 ms 2048 KB Output is correct
7 Incorrect 2 ms 1920 KB Output isn't correct
8 Halted 0 ms 0 KB -