Submission #1135908

#TimeUsernameProblemLanguageResultExecution timeMemory
1135908t9unkubjArranging Shoes (IOI19_shoes)C++20
100 / 100
307 ms29372 KiB
#ifdef t9unkubj #include"debug.cpp" //#include"template_no_debug.h" #else #define dbg(...) 199958 #endif #undef _GLIBCXX_DEBUG #pragma GCC optimize("O3") using namespace std; #include<bits/stdc++.h> using ll=long long; using ull=unsigned long long; template<class T>using vc=vector<T>; template<class T>using vvc=vc<vc<T>>; #define rep(i,n) for(ll i=0;i<(ll)(n);i++) #define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++) #define DREP(i,n,m) for(ll i=(n);i>=(m);i--) #define drep(i,n) for(ll i=((n)-1);i>=0;i--) #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() template<class T,class F> bool chmin(T &x, F y){ if(x>y){ x=y; return true; } return false; } template<class T, class F> bool chmax(T &x, F y){ if(x<y){ x=y; return true; } return false; } double pass_time=0; #include<vector> template <class T = long long > struct BIT { int n; std::vector<T>data; void add(int i,T x){ assert(i>=0&&i<n); i++; for(;i<=n;){ data[i - 1] += x; i += (i & -i); } return; } T internal_sum(int r){ T ret = 0; for(;r;){ ret += data[r - 1]; r -= (r & -r); } return ret; } T sum(int l,int r){ return internal_sum(r)-internal_sum(l); } BIT():n(0), data(0) {} BIT(int N):n(N), data(N) {} BIT(std::vector<T>& a){ n = a.size(); data.assign(n, 0); for (int i = 0; i < n; i++)add(i, a[i]); } int lower_bound(T w) { if (w <= 0) { return 0; } else { int x = 0, r = 1; while (r < n) r = r << 1; for (int len = r; len > 0; len = len >> 1) { if (x + len < n && data[x + len] < w) { w -= data[x + len]; x += len; } } return x; } } }; #include"shoes.h" long long count_swaps(vector<int>S){ int n=S.size(); map<int,vc<int>>vs; rep(i,n){ vs[S[i]].push_back(i); } set<pair<int,int>>st; for(auto&[x,y]:vs){ if(x<0)continue; rep(j,y.size()){ int i1=y[j],i2=vs[-x][j]; st.insert(minmax(i1,i2)); } } BIT<int>bit(n); rep(i,n){ bit.add(i,1); } ll ans=0; for(auto&[x,y]:st){ bit.add(x,-1); bit.add(y,-1); ans+=bit.sum(0,x); ans+=bit.sum(0,y); if(S[x]>0)++ans; } return ans; }
#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...