oj.uz

Submission #158231

# Submission time Handle Problem Language Result Execution time Memory
158231 2019-10-15T15:05:11 Z nickmet2004 Arranging Shoes (IOI19_shoes) C++14
10 / 100
 71 ms 67812 KB 
#include<bits/stdc++.h>
//#include<shoes.h>

using namespace std;

const int NAX = 1e5 + 5;

int N;

struct Hash{
    size_t operator()(const pair<int , int> &x) const{
        return ((long long)x.first) ^ (((long long)x.second) << 32);
    }
};
// fenwick tree to count range sums (+0 , +1 , +2)

int f[2 * NAX + 1];

void update(int idx , int u){
    ++idx;
    while(idx <= N){
        f[idx] += u;
        idx += idx & (-idx);
    }
}
long long sum(int idx){
    long long sum = 0;
    ++idx;
    while(idx){
        sum += f[idx];
        idx -= idx & (-idx);
    }
    return sum;
}

unordered_map<pair<long , long> , bool , Hash> paired , px , nx;
queue<int> q[NAX];

long long count_swaps(vector<int> S){
    N = S.size();
    long long ans = 0;
    for(int i = 1; i <= N; ++i){
        px[{i , 1}] = false;
        nx[{i , -1}] = false;
    }
    // update BIT
    for(int i = 0; i < N; ++i){
        update(i , 1);
    }
    for(int i = 0; i < N; ++i){
        int x = abs(S[i]);
        int k = S[i];
        // when queue is empty
        if(q[x].empty()){
            if(k > 0){
                q[x].push(i);
                //positive x's are in the queue
                px[{x , 1}] = true;
                nx[{x , -1}] = false;
            }
            else {
                q[x].push(i);
                // negative x's are int the queue
                nx[{x , -1}] = true;
                px[{x , 1}] = false;
            }
        } else if(px[{x , 1}]){
            if(k < 0){
                ans += (sum(i) - sum(q[x].front() - 1) - 1);
                update(i , -1);
                if(q[x].front()){
                    update(q[x].front() - 1 , 1);
                }
                q[x].pop();
            } else {
                q[x].push(i);
            }
        } else if(nx[{x , -1}]){
                if(k > 0){
                    ans += (sum(i) - sum(q[x].front() - 1) - 2);
                    update(q[x].front() , -1);
                    update(i - 1 , 1);
                    q[x].pop();
            } else {
                q[x].push(i);
            }
        }
        if(q[x].empty()){
            px[{x , 1}] = false;
            nx[{x , -1}] = false;
        }
    }
    return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 67672 KB Output is correct
2 Correct 70 ms 67576 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 67672 KB Output is correct
2 Correct 70 ms 67576 KB Output is correct
3 Correct 71 ms 67644 KB Output is correct
4 Correct 71 ms 67576 KB Output is correct
5 Correct 70 ms 67576 KB Output is correct
6 Correct 71 ms 67672 KB Output is correct
7 Incorrect 69 ms 67576 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 67672 KB Output is correct
2 Correct 70 ms 67576 KB Output is correct
3 Incorrect 71 ms 67592 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 67664 KB Output is correct
2 Incorrect 71 ms 67812 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 67672 KB Output is correct
2 Correct 70 ms 67576 KB Output is correct
3 Correct 71 ms 67644 KB Output is correct
4 Correct 71 ms 67576 KB Output is correct
5 Correct 70 ms 67576 KB Output is correct
6 Correct 71 ms 67672 KB Output is correct
7 Incorrect 69 ms 67576 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 67672 KB Output is correct
2 Correct 70 ms 67576 KB Output is correct
3 Correct 71 ms 67644 KB Output is correct
4 Correct 71 ms 67576 KB Output is correct
5 Correct 70 ms 67576 KB Output is correct
6 Correct 71 ms 67672 KB Output is correct
7 Incorrect 69 ms 67576 KB Output isn't correct
8 Halted 0 ms 0 KB -