| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 185269 | aggu_01000101 | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <shoes.h>
#include <vector>
#include <map>
#define int long long
#define mid(l, u) ((l+u)/2)
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
using namespace std;
int query(int l, int u, int i, int ll, int uu, int segtree[], int lazy[]){
if(lazy[i]){
segtree[i]+=(u-l+1)*lazy[i];
if(l!=u){
lazy[lchild(i)]+=lazy[i];
lazy[rchild(i)]+=lazy[i];
}
lazy[i] = 0;
}
if(l>=ll && u<=uu) return segtree[i];
if(l>uu || u<ll) return 0;
return query(l, mid(l, u), lchild(i), ll, uu, segtree, lazy) + query(mid(l, u)+1, u, rchild(i), ll, uu, segtree, lazy);
}
int update(int l, int u, int i, int ll, int uu, int segtree[], int lazy[]){
if(ll>uu) return 0;
if(lazy[i]){
segtree[i]+=(u-l+1)*lazy[i];
if(l!=u){
lazy[lchild(i)]+=lazy[i];
lazy[rchild(i)]+=lazy[i];
}
lazy[i] = 0;
}
if(l>=ll && u<=uu){
segtree[i] += (u-l+1);
if(l!=u){
lazy[lchild(i)]++;
lazy[rchild(i)]++;
}
return segtree[i];
}
if(l>uu || u<ll) return segtree[i];
return segtree[i] = update(l, mid(l, u), lchild(i), ll, uu, segtree, lazy) + update(mid(l, u)+1, u, rchild(i), ll, uu, segtree, lazy);
}
int count_swaps(vector<int> s){
int n = s.size();
//cout<<n<<endl;
int segtree[4*n], lazy[4*n];
for(int i = 0;i<4*n;i++) segtree[i] = lazy[i] = 0;
map<int, int> mp;
for(int i = 0;i<n;i++) mp[s[i]] = i;
int ans = 0;
for(int i = 0;i<n;i++){
if(mp[-s[i]]>i) continue;
int toadd;
if(s[i]>0){
toadd = i - mp[-s[i]] - 1;
toadd-=query(0, n-1, 0, mp[-s[i]], mp[-s[i]], segtree, lazy);
}
else{
toadd = i - mp[-s[i]];
toadd-=query(0, n-1, 0, mp[-s[i]], mp[-s[i]], segtree, lazy);
}
//cout<<i<<" "<<mp[-s[i]]<<" "<<toadd<<endl;
ans+=toadd;
update(0, n-1, 0, mp[-s[i]]+1, i-1, segtree,lazy);
}
return ans;
}