이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <functional>
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
#define mp make_pair
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
const lld pi = 3.14159265358979323846;
#define MAXI (int)1e5
#define LSOne(S) ((S) & -(S))
#define MSB(S) __builtin_clz(S)
vector<int> ad[MAXI];
vector<ll> ft;
ll sumFT(int index){
ll sum = 0;
while(index > 0){
sum+= ft[index];
index -= LSOne(index);
}
return sum;
}
int getval(int index){
int x = sumFT(index)-sumFT(index-1);
if(x == 0) return 1; else return -1;
}
void updateFT(int index, ll val){
while(index < (int)ft.size()){
ft[index] += val;
index += LSOne(index);
}
}
void buildFT(vector<ll> a){
for(int i = 1;i<(int)ft.size();i++){
ft[i]+= a[i];
int x = LSOne(i)+i;
if(x < (int)ft.size())
ft[x] += ft[i];
}
}
void range_update(int l,int r,ll val){
++r;
if(r < (int)ft.size())
updateFT(r,-val);
updateFT(l,val);
}
long long count_swaps(vector<int> a){
int n = a.size();
vector<set<int>> left(2*n+1);
vector<set<int>> right(2*n+1);
vector<bool> marked(2*n,0);
ll ans = 0;
for(int i = 0;i<n;i++){
if(a[i] < 0){
int x = a[i]*-1;
left[x].insert(i);
}else right[a[i]].insert(i);
}
ft.assign(n+1,1);
int links,rechts;
for(int i = 0;i<n;i++){
if(marked[i]) continue;
if(a[i] < 0) {
rechts = *right[abs(a[i])].begin();
}else{
ans++;
rechts = *left[a[i]].begin();
}
right[abs(a[i])].erase(*right[abs(a[i])].begin());
left[abs(a[i])].erase(*left[abs(a[i])].begin());
links = i;
ans += sumFT(rechts)-sumFT(links);
updateFT(links,0);
updateFT(rechts,0);
marked[i] = 1;
marked[rechts] = 1;
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |