제출 #746357

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
746357		Sami_Massah	Arranging Shoes (IOI19_shoes)	C++17	30 / 100	156 ms	29024 KiB

shoes

#include <bits/stdc++.h>
using namespace std;


const long long maxn = 2e5 + 12, mod = 998244353, inf = 1e9 + 12 ;
long long L[maxn * 4], R[maxn * 4], sum[maxn * 4];
bitset <maxn> marked;
vector <int> locs[maxn][2];
void make_tree(int l, int r, int ind){
    int mid = (l + r) / 2;
    L[ind] = l;
    R[ind] = r;
    if(l == r)
        return;
    make_tree(l, mid, ind * 2);
    make_tree(mid + 1, r, ind * 2 + 1);
}
void update_tree(int l, int r, int u){
    if(r < L[u] || R[u] < l)
        return;
    if(l <= L[u] && R[u] <= r){
        sum[u] = 1;
        return;

    }
    update_tree(l, r, u * 2);
    update_tree(l, r, u * 2 + 1);
    sum[u] = (sum[u * 2] + sum[u * 2 + 1]);
}
int get_sum(int l, int r, int u){
    if(r < L[u] || R[u] < l)
        return 0;
    if(l <= L[u] && R[u] <= r){
        return sum[u];

    }
    return get_sum(l, r, u * 2) + get_sum(l, r, u * 2 + 1);
}
long long count_swaps(vector <int> s){

    int n = s.size();
    make_tree(0, n, 1);
    for(int i = 0; i < n; i++)
        locs[abs(s[i])][(s[i] < 0)].push_back(i);

    n = n / 2;
    for(int i = 1; i <= n; i++){
        reverse(locs[i][0].begin(), locs[i][0].end());
        reverse(locs[i][1].begin(), locs[i][1].end());
        }
    long long nat = 0, k = 0;

   // cout << locs[1][0][0] << ' ' << locs[1][1][0] << endl;
    for(int i = 0; i < n * 2; i++){
        int now = abs(s[i]);
        if(marked[now] == 1){
            marked[now] = 0;
            continue;

        }
        marked[now] = 1;
        if(locs[now][0].back() > locs[now][1].back())
            nat -= 1;
        nat += abs(locs[now][0].back() - locs[now][1].back());
        int mn = min(locs[now][0].back(), locs[now][1].back()), mx = max(locs[now][0].back(), locs[now][1].back());
        nat -= get_sum(mn, mx, 1);
        update_tree(mx, mx, 1);
        locs[now][0].pop_back();
        locs[now][1].pop_back();

        }



    return nat;
}
/*
int main(){
    vector <int> f;
    int n, l, r;
    cin >> n;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        f.push_back(a);

    }
    cout << count_swaps(f) << endl;


}

*/

컴파일 시 표준 에러 (stderr) 메시지

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:51:24: warning: unused variable 'k' [-Wunused-variable]
   51 |     long long nat = 0, k = 0;
      |                        ^

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15