제출 #198298

#제출 시각아이디문제언어결과실행 시간메모리
198298AkashiArranging Shoes (IOI19_shoes)C++14
100 / 100
229 ms31648 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; struct grup{ int x, y; bool operator < (const grup &aux)const{ if((x + y) / 2 != (aux.x + aux.y) / 2) return (x + y) / 2 < (aux.x + aux.y) / 2; return x < aux.x; } }; grup a[100005]; set <int> lf[200005], rf[200005]; int n; int Arb[800005], Lazy[800005]; void propag(int nod){ for(int i = nod * 2; i <= nod * 2 + 1 ; ++i){ Lazy[i] += Lazy[nod]; Arb[i] += Lazy[nod]; } Lazy[nod] = 0; } void build(int st = 1, int dr = n, int nod = 1){ Lazy[nod] = 0; if(st == dr){ Arb[nod] = st; return ; } int mij = (st + dr) / 2; build(st, mij, nod * 2); build(mij + 1, dr, nod * 2 + 1); } void update(int x, int y, int val, int st = 1, int dr = n, int nod = 1){ if(x <= st && dr <= y){ Lazy[nod] += val; Arb[nod] += val; return ; } propag(nod); int mij = (st + dr) / 2; if(x <= mij) update(x, y, val, st, mij, nod * 2); if(mij + 1 <= y) update(x, y, val, mij + 1, dr, nod * 2 + 1); } int query(int x, int st = 1, int dr = n, int nod = 1){ if(st == dr) return Arb[nod]; propag(nod); int mij = (st + dr) / 2; if(x <= mij) return query(x, st, mij, nod * 2); else return query(x, mij + 1, dr, nod * 2 + 1); } long long count_swaps(vector<int> s) { int NR = 0; n = s.size(); long long Sol = 0; for(int i = 1; i <= n ; ++i){ int x = s[i - 1]; if(x < 0){ x = -x; if(!rf[x].empty()){ a[++NR] = {i, *rf[x].begin()}; rf[x].erase(rf[x].begin()); //++Sol; } else lf[x].insert(i); } else{ if(!lf[x].empty()){ a[++NR] = {*lf[x].begin(), i}; lf[x].erase(lf[x].begin()); } else rf[x].insert(i); } } sort(a + 1, a + NR + 1); //cerr << n; build(); for(int i = 1; i <= NR ; ++i){ int p1 = 2 * i - 1, p2 = 2 * i; int x = query(a[i].x); Sol = Sol + abs(x - p1); update(1, a[i].x, 1); int y = query(a[i].y); Sol = Sol + abs(y - p2); update(1, a[i].y, 1); } return Sol; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...