제출 #348008

#제출 시각아이디문제언어결과실행 시간메모리
348008ChaskaArranging Shoes (IOI19_shoes)C++17
100 / 100
671 ms149612 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; int n; map<int,stack<int>> h; bool vs[200005]; int st[1000005],lz[1000005]; void upd(int no,int i,int f,int pos) { if (f<pos) return; if (i<pos) { int l,r; l = no*2+1; r = l+1; lz[l] += lz[no]; lz[r] += lz[no]; lz[no] = 0; int m = (i+f)/2; upd(l,i,m,pos); upd(r,m+1,f,pos); return; } else { lz[no]++; return; } } int get(int no,int i,int f,int pos) { if (f<pos || i>pos) return 0; if (i==f) { return lz[no]; } int m = (i+f)/2; int l,r; l = no*2+1; r = l+1; lz[l] += lz[no]; lz[r] += lz[no]; lz[no] =0; return get(l,i,m,pos)+get(r,m+1,f,pos); } long long count_swaps(vector<int> s) { n = s.size()/2; long long k=0; for (int i=0;i<n+n;i++) h[s[i]].push(i); for (int i=n+n-1;i>=0;i--) if (!vs[i]) { h[s[i]].pop(); int p = h[s[i]*-1].top(); h[s[i]*-1].pop(); int p1,p2; // change the res[p] to get(0,0,n+n,p); p1 = p-get(0,0,n+n-1,p); p2 = i-get(0,0,n+n-1,i); k += p2 - p1; if (s[i]>0) k--; vs[p] = vs[i] = true; upd(0,0,n+n-1,p+1); } return k; }
#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...