# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
936861 | 4QT0R | Arranging Shoes (IOI19_shoes) | C++17 | 137 ms | 142448 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
queue<int> pos[200004];
const int base=1<<18;
ll tree[2*base];
void zmien(int v){
v+=base;
tree[v]^=1;
v>>=1;
while(v){
tree[v]=tree[2*v]+tree[2*v+1];
v>>=1;
}
}
ll sprawdz(int l, int p){
l+=base-1;
p+=base+1;
ll ans=0;
while(l/2!=p/2){
if (!(l&1))ans+=tree[l+1];
if (p&1)ans+=tree[p-1];
l>>=1;
p>>=1;
}
return ans;
}
ll count_swaps(vector<int> S){
ll n=S.size(),open=0,odp=0;
for (int i = 0; i<n; i++){
if (S[i]>0){
if (pos[S[i]+100000].empty()){
pos[S[i]].push(i);
zmien(i);
}
else{
odp+=i-pos[S[i]+100000].front()-1;
odp-=sprawdz(pos[S[i]+100000].front()+1,i);
zmien(pos[S[i]+100000].front());
pos[S[i]+100000].pop();
}
}
else{
if (pos[-S[i]].empty()){
pos[100000-S[i]].push(i);
zmien(i);
}
else{
odp+=i-pos[-S[i]].front();
odp-=sprawdz(pos[-S[i]].front()+1,i);
zmien(pos[-S[i]].front());
pos[-S[i]].pop();
}
}
}
return odp;
}
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |