Submission #1212481

#TimeUsernameProblemLanguageResultExecution timeMemory
1212481simona1230Arranging Shoes (IOI19_shoes)C++20
100 / 100
92 ms22076 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; vector<int> l[200001],r[200001]; vector<pair<int,int> > p; int t[800001]; void update(int i,int l,int r,int id) { if(l==r) { t[i]=1; return; } int m=(l+r)/2; if(id<=m)update(i*2,l,m,id); else update(i*2+1,m+1,r,id); t[i]=t[i*2]+t[i*2+1]; } long long query(int i,int l,int r,int ql,int qr) { if(ql>qr)return 0; if(ql<=l&&r<=qr)return t[i]; int m=(l+r)/2; return query(i*2,l,m,ql,min(qr,m))+query(i*2+1,m+1,r,max(m+1,ql),qr); } long long count_swaps(std::vector<int> s) { for(int i=0;i<s.size();i++) { if(s[i]<0)l[-s[i]].push_back(i); else r[s[i]].push_back(i); } long long ans=0; vector<pair<int,int> > v; for(int i=0;i<s.size();i++) { for(int j=0;j<l[i].size();j++) { if(l[i][j]>r[i][j])ans++; v.push_back({min(l[i][j],r[i][j]),max(l[i][j],r[i][j])}); } } for(int i=0;i<v.size();i++) p.push_back({v[i].first,-1}), p.push_back({v[i].second,v[i].first}); sort(p.begin(),p.end()); int open=0; for(int i=0;i<p.size();i++) { if(p[i].second==-1)open++; else { open--; ans+=open; ans+=query(1,0,s.size()-1,p[i].second,p[i].first); update(1,0,s.size()-1,p[i].second); //cout<<p[i].second<<" + "<<p[i].second<<" "<<p[i].first<<endl; } } 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...