oj.uz

Submission #155782

# Submission time Handle Problem Language Result Execution time Memory
155782 2019-09-30T14:20:58 Z Sasuke0004 Arranging Shoes (IOI19_shoes) C++17
0 / 100
 281 ms 269656 KB 
#include<bits/stdc++.h>
#define lnode (node << 1)
#define rnode (lnode | 1) 
using namespace std;
const int N = 2e5 + 10;
queue < int > q[N][2];
int a[N] , fix[N] , S[4 * N] , lazy[4 * N];  
void Lazy(int l , int r , int node){
    if(l != r){
        lazy[lnode] += lazy[node];
        lazy[rnode] += lazy[node];
    }
    S[node] += lazy[node];
    lazy[node] = 0;
}
void upd(int l , int r , int L , int R , int x , int node){
    Lazy(l , r , node);
    if(L > r || l > R || L > R || l > r) return;
    if(L <= l && R >= r){
        lazy[node] += x;
        Lazy(l , r , node);
        return;
    }
    int m = (l + r) >> 1;
    upd(l , m , L , R , x , lnode); ++ m;
    upd(m , r , L , R , x , rnode);
    S[node] = S[lnode] + S[rnode];
}
int get(int l , int r , int x , int node){
    Lazy(l , r , node); 
    if(l > x || r < x || l > r) return 0;
    if(l == x && r == x) return S[node]; 
    int m = (l + r) >> 1;
    return max(get(l , m , x , lnode) , get(m + 1 , r , x , rnode));
}
int64_t count_swaps(vector<int> x){
    int n , res = 0;
    n = x.size()/2;
    for(int i = 1; i <= 2 * n; i ++) cin >> a[i] , upd(1 , 2 * n , i , i , i , 1) , q[abs(a[i])][a[i] > 0].push(i);  
    for(int i = 1; i <= 2 * n; i ++){
        if(fix[i]) continue;
        int l = i , r = q[abs(a[i])][a[i] <= 0].front();
        int x = get(1 , 2 * n , l , 1) , y = get(1 , 2 * n , r , 1);
        upd(1 , 2 * n , l + 1 , r - 1 , 1 , 1);
        if(a[l] < 0) res += y - x - 1;
        else res += y - x;
        fix[r] = 1;
    }
    return res;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 15.0

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