Submission #849905

#TimeUsernameProblemLanguageResultExecution timeMemory
849905tosivanmakArranging Shoes (IOI19_shoes)C++17
65 / 100
60 ms24000 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long struct pairs{ ll l,r; bool operator<(const pairs& p)const{ // l,r,p.l,p.r ll cnt=0; if(r<l){ cnt++; } if(p.l<l){ cnt++; } if(p.l<r){ cnt++; } if(p.r<l){ cnt++; } if(p.r<r){ cnt++; } if(p.r<p.l){ cnt++; } ll cnt2=0; // p.l,p.r,l,r if(p.r<p.l){ cnt2++; } if(l<p.l){ cnt2++; } if(l<p.r){ cnt2++; } if(r<p.l){ cnt2++; } if(r<p.r){ cnt2++; } if(r<l){ cnt2++; } // cout<<1; return cnt<=cnt2; } }; struct FEN{ vector<ll>fen; void init(ll n){ fen.resize(n+5); for(int i=0;i<=n+4;i++){ fen[i]=0; } } void upd(ll n, ll m, ll val){ for(int i=n;i<=m;i+=i&(-i)){ fen[i]+=val; // cout<<i; } } ll sum(ll e){ ll su=0; while(e>=1){ su+=fen[e]; e-=e&(-e); } // cout<<1; return su; } }f; vector<int>adj[200005],adj2[200005]; int ptr[200005]; long long count_swaps(std::vector<int> s) { vector<ll>make; for(int i=0;i<s.size();i++){ if(s[i]<0){ make.push_back(-(s[i])); adj[-(s[i])].push_back(i+1); } else{ adj2[s[i]].push_back(i+1); } } for(int i=0;i<=s.size()+4;i++){ ptr[i]=0; } vector<pairs>bruh; // for(auto u: adj[2]){ // cout<<u<<" "; // } for(int i=0;i<make.size();i++){ bruh.push_back({adj[make[i]][ptr[make[i]]],adj2[make[i]][ptr[make[i]]]}); ptr[make[i]]++; } sort(bruh.begin(),bruh.end()); vector<ll>real; for(int i=0;i<bruh.size();i++){ real.push_back(bruh[i].l); real.push_back(bruh[i].r); } // for(auto u: real){ // cout<<u<<" "; // } f.init(200000); ll ans=0; for(int i=0;i<real.size();i++){ ans+=f.sum(200000)-f.sum(real[i]); // cout<<f.sum(200000)<<" "<<real[i]<<" "; // cout<<f.sum(real[i])<<"\n"; f.upd(real[i],200000,1); } return ans; // return 0; } // #ifndef ONLINE_JUDGE // int main() { // int n; // cin>>n; // vector<int> S(2 * n); // for (int i = 0; i < 2 * n; i++){ // cin>>S[i]; // } // long long result = count_swaps(S); // cout<<result<<"\n"; // return 0; // } // #endif

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:81:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |      for(int i=0;i<s.size();i++){
      |                  ~^~~~~~~~~
shoes.cpp:91:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |      for(int i=0;i<=s.size()+4;i++){
      |                  ~^~~~~~~~~~~~
shoes.cpp:98:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |      for(int i=0;i<make.size();i++){
      |                  ~^~~~~~~~~~~~
shoes.cpp:104:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pairs>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |      for(int i=0;i<bruh.size();i++){
      |                  ~^~~~~~~~~~~~
shoes.cpp:113:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |      for(int i=0;i<real.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...