oj.uz

답안 #143340

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
143340 2019-08-13T17:22:40 Z pzdba Arranging Shoes (IOI19_shoes) C++14
0 / 100
 13 ms 9976 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> s[200001];
int j[200001];
bool vis[200001];
int p[200001];

int ft[200001];
void update(int i, int v){
    for(;i<=200000;i+=(i&-i)) ft[i] += v;
}
int query(int i){
    int ans = 0;
    for(;i>0;i-=(i&-i)) ans+=ft[i];
    return ans;
}

ll count_swaps(vector<int> S){
    int n = S.size()/2;
    for(int i=0;i<n+n;i++){
        if(S[i] < 0) S[i] = -S[i];
        else S[i] += n;
        s[S[i]].push_back(i);
        p[i] = -1;
    }

    for(int i=0;i<n+n;i++){
        if(vis[i]) continue;
        vis[i] = 1;


        if(S[i] >= n){
            int l = S[i]-n;
            int r = S[i];
            p[i] = s[l][j[l]];
            vis[p[i]] = 1;
            j[l]++;
            j[r]++;
        }
        else{
            int l = S[i];
            int r = S[i]+n;
            p[i] = s[r][j[r]];
            vis[p[i]] = 1;
            j[r]++;
            j[l]++;
        }
    }
    ll ans = 0;
    for(int i=0;i<n+n;i++){
        if(p[i] == -1) continue;
        int l = i, r = p[i];
        int l2 = l + query(200000) - query(l);
        int r2 = r + query(200000) - query(r);
        ans += r2-l2-1;
        if(S[i] >= n) ans++;
        update(r, 1);
    }
    return ans;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 9976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 9976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 9976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 9976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 9976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 9976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -