이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
struct logaritamska{
int l[maxn];
void update(int x, int val){
for(; x<maxn; x+=(x & -x)){
l[x]+=val;
}
}
int query(int x){
int sol=0;
for(; x>0; x-=(x & -x)){
sol+=l[x];
}
return sol;
}
};
logaritamska L;
queue < int > q1[maxn], q2[maxn];
ll count_swaps(vector<int> s){
int n=s.size();
ll sol=0;
int a, b, c, d;
for(int i=0; i<n; i++){
if(s[i]>0){
if(!q2[s[i]].empty()){
a=q2[s[i]].front();
q2[s[i]].pop();
b=i;
c=L.query(a+1)+a;
d=L.query(b+1)+b;
sol+=d-c-1;
L.update(a+1, 1);
L.update(b+1, -1);
}
else{
q1[s[i]].push(i);
}
}
else{
if(!q1[-s[i]].empty()){
a=q1[-s[i]].front();
q1[-s[i]].pop();
b=i;
c=L.query(a+1)+a;
d=L.query(b+1)+b;
sol+=d-c;
L.update(a+1, 1);
L.update(b+1, -1);
}
else{
q2[-s[i]].push(i);
}
}
}
return sol;
}
# | 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... |