oj.uz

답안 #268730

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
268730 2020-08-16T22:05:41 Z Puddlestomps Arranging Shoes (IOI19_shoes) C++14
10 / 100
 3 ms 2560 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
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

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

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 15.0

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