oj.uz

답안 #158385

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
158385 2019-10-16T20:53:15 Z nickmet2004 Arranging Shoes (IOI19_shoes) C++14
10 / 100
 191 ms 135064 KB 
#include<bits/stdc++.h>
//#include<shoes.h>

using namespace std;

const int NAX = 1e5 + 5;

int N;
// 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;
}
// 0 - negative x's , 1 - positive x's
queue<int> q[NAX][2];

long long count_swaps(vector<int> S){
    N = S.size();
    long long ans = 0;
    // 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];
        int f , d;
        if(S[i] > 0){
            // opposite
            d = 0;
            // its
            f = 1;
        } else {
            d = 1;
            f = 0;
        }
        // when queue is empty
        if(!q[x][d].empty()){
            //cerr << sum(i) << " sum(i) " << endl << sum(q[x][d].front() - 1) << "sum(qFRONT())" << endl;
            ans += (sum(i) - sum(q[x][d].front() - 1) - 1);
            //cerr << "ans: " << ans << "tavdapirvelad" << endl;
            if(k > 0){
                --ans;
                //cerr << "ans: " << ans << " sabolood" << endl;
                update(q[x][d].front() , -1);
                update(i - 1, 1);
                q[x][d].pop();
            } else {
                update(i , -1);
                update(q[x][d].front() , 1);
                q[x][d].pop();
            }

        } else {
            q[x][f].push(i);
        }
    }
    return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 135032 KB Output is correct
2 Correct 156 ms 134904 KB Output is correct
3 Correct 141 ms 134972 KB Output is correct
4 Correct 140 ms 134888 KB Output is correct
5 Correct 145 ms 135032 KB Output is correct
6 Correct 136 ms 134992 KB Output is correct
7 Incorrect 136 ms 134892 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 135032 KB Output is correct
2 Correct 156 ms 134904 KB Output is correct
3 Correct 141 ms 134972 KB Output is correct
4 Correct 140 ms 134888 KB Output is correct
5 Correct 145 ms 135032 KB Output is correct
6 Correct 136 ms 134992 KB Output is correct
7 Incorrect 136 ms 134892 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 135032 KB Output is correct
2 Correct 156 ms 134904 KB Output is correct
3 Correct 141 ms 134972 KB Output is correct
4 Correct 140 ms 134888 KB Output is correct
5 Correct 145 ms 135032 KB Output is correct
6 Correct 136 ms 134992 KB Output is correct
7 Incorrect 136 ms 134892 KB Output isn't correct
8 Halted 0 ms 0 KB -