oj.uz

Submission #151382

# Submission time Handle Problem Language Result Execution time Memory
151382 2019-09-02T14:52:46 Z alexandra_udristoiu Arranging Shoes (IOI19_shoes) C++14
0 / 100
 2 ms 376 KB 
#include "shoes.h"
#include<iostream>
#include<vector>
#define DIM 200005
using namespace std;
static int n;
static int v[DIM], aib[DIM], st[DIM], dr[DIM], ff[DIM];
static void update(int x, int val){
    for(; x <= n; x += (x & -x) ){
        aib[x] += val;
    }
}
static int query(int x){
    int sum = 0;
    for(; x >= 1; x -= (x & -x) ){
        sum += aib[x];
    }
    return sum;
}
long long count_swaps(vector<int> s) {
    int i;
    long long sol = 0;
    n = s.size();
    for(i = 1; i <= n; i++){
        v[i] = s[i - 1];
        update(i, 1);
    }
    for(i = n; i >= 1; i--){
        if(v[i] < 0){
            ff[i] = dr[ -v[i] ];
            dr[ -v[i] ] = 0;
            if(ff[i] == 0){
                st[ -v[i] ] = i;
            }
        }
        else{
            ff[i] = st[ v[i] ];
            st[ v[i] ] = 0;
            if(ff[i] == 0){
                dr[ v[i] ] = i;
            }
        }
    }
    for(i = 1; i <= n; i++){
        if(ff[i] != 0){
            sol += query(ff[i]) - query(i);
            update(ff[i], -1);
        }
    }
    return sol;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -