제출 #184111

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
184111		nicolaalexandra	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	409 ms	275468 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#define DIM 200010
using namespace std;

long long aib[DIM];
vector <int> v;
deque <int> st[DIM],dr[DIM];
int n,i,x;
int f[DIM];

void update (int p, int n, int val){
    for (;p<=n;p+=(p&-p))
        aib[p] += val;
}
long long query (int p){
    long long sol = 0;
    for (;p;p-=(p&-p))
        sol += aib[p];
    return sol;
}
long long count_swaps (vector <int> v){
    /*for (int i=v.size()-1;i>=0;i--){
        int val = v[i], semn = 1;
        if (val < 0)
            semn = -1, val *= -1;
        d[val].push_back(i+1,semn);
    }*/
    int n = v.size();
    for (int i=v.size()-1;i>=0;i--){
        int val = v[i];
        if (val < 0){
            st[-val].push_back(i);
        } else {
            dr[val].push_back(i);
        }
    }
    for (int i=0;i<n;i++)
        f[i] = 0;
    long long sol = 0;
    for (int i=0;i<v.size();i++){
        if (f[i]) /// inseamna ca deja am rezolvat perechea asta
            continue;
        int val = v[i];
        if (val < 0){
            int poz = dr[-val].back();
            f[poz] = 1;
            dr[-val].pop_back();
            st[-val].pop_back();
            /// ma intereseaza cate elemente am in intervalul i...poz
            long long nr = query (poz+1) - query (i+1);
            sol += poz-i-1 - nr;
            update (poz+1,n,1);
        } else {
            int poz = st[val].back();
            f[poz] = 1;
            st[val].pop_back();
            dr[val].pop_back();
            long long nr = query (poz+1) - query (i+1);
            sol += poz-i - nr;
            update (poz+1,n,1);
        }

    }
    return sol;

}

/*int main (){

    ifstream fin ("date.in");
    ofstream fout ("date.out");
    fin>>n;
    for (i=1;i<=n;i++){
        fin>>x;
        v.push_back(x);
    }
    fout<<count_swaps(v);

    return 0;
}*/

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

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:41:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v.size();i++){
                  ~^~~~~~~~~

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