Submission #155782

#	Time	Username	Problem	Language	Result	Execution time	Memory
155782		Sasuke0004	Arranging Shoes (IOI19_shoes)	C++17	0 / 100	281 ms	269656 KiB

shoes

#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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15