Submission #824464

#TimeUsernameProblemLanguageResultExecution timeMemory
824464tolbiArranging Shoes (IOI19_shoes)C++17
100 / 100
299 ms26776 KiB
#pragma optimize("Bismillahirrahmanirrahim") //█▀█─█──█──█▀█─█─█ //█▄█─█──█──█▄█─█■█ //█─█─█▄─█▄─█─█─█─█ //Allahuekber //ahmet23 orz... //FatihSultanMehmedHan //YavuzSultanSelimHan //AbdulhamidHan //Sani buyuk Osman Pasa Plevneden cikmam diyor #define author tolbi #include <bits/stdc++.h> using namespace std; template<typename X, typename Y> istream& operator>>(istream& is, pair<X,Y> &pr){return is>>pr.first>>pr.second;} template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr){return os<<pr.first<<" "<<pr.second;} template<typename T> istream& operator>>(istream& is, vector<T> &arr){for (auto &it : arr) is>>it; return is;} template<typename T> ostream& operator<<(ostream& os, vector<T> arr){for (auto &it : arr) os<<it<<" "; return os;} template<typename T,size_t Y> istream& operator>>(istream& is, array<T,Y> &arr){for (auto &it : arr) is>>it; return is;} template<typename T,size_t Y> ostream& operator<<(ostream& os, array<T,Y> arr){for (auto &it : arr) os<<it<<" "; return os;} #define deci(x) int x;cin>>x; #define decstr(x) string x;cin>>x; #define cinarr(x) for (auto &it : x) cin>>it; #define coutarr(x) for (auto &it :x) cout<<it<<" ";cout<<endl; #define sortarr(x) sort(x.begin(), x.end()) #define sortrarr(x) sort(x.rbegin(), x.rend()) #define rev(x) reverse(x.begin(), x.end()) #define tol(bi) (1LL<<((int)(bi))) typedef long long ll; const int MOD = 1e9+7; mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count()); #include "shoes.h" struct SegTree{ vector<int> segtree; SegTree(int n){ segtree.resize(tol(ceil(log2(n)+1))-1,0ll); } inline void update(int node){ node+=segtree.size()/2; segtree[node]=1; while (node){ node=(node-1)/2; segtree[node]=segtree[node*2+1]+segtree[node*2+2]; } } int query(int tarl, int tarr, int l = 0, int r = -1, int node = 0){ if (r==-1) r = segtree.size()/2; if (l>=tarl && r<=tarr) return segtree[node]; if (l>tarr || r<tarl) return 0ll; int mid = l+(r-l)/2; int lnode = query(tarl, tarr, l, mid, node*2+1); int rnode = query(tarl, tarr, mid+1, r, node*2+2); return lnode+rnode; } }; long long count_swaps(vector<int> s) { int n = s.size(); map<int,vector<int>> mp; vector<bool> taken(n,false); for (int i = n-1; i >= 0; i--){ mp[s[i]].push_back(i); } ll ans = 0; vector<pair<int,int>> prs; for (int i = 0; i < n; i++){ if (taken[i]) continue; int l = i; int r = mp[-s[i]].back(); mp[-s[i]].pop_back(); mp[s[i]].pop_back(); if (s[i]>0) ans++; prs.push_back({l,r}); taken[l]=taken[r]=true; } SegTree segtree(n); sort(prs.begin(), prs.end(), [&](pair<int,int> x, pair<int,int> y){ return (x.second-x.first)<(y.second-y.first); }); for (int i = 0; i < prs.size(); i++){ int l = prs[i].first; int r = prs[i].second; ans+=segtree.query(l,r); segtree.update(l); segtree.update(r); } return ans; }

Compilation message (stderr)

shoes.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for (int i = 0; i < prs.size(); i++){
      |                  ~~^~~~~~~~~~~~
#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...