Submission #540466

#	Time	Username	Problem	Language	Result	Execution time	Memory
540466		new_acc	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	59 ms	16024 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int M=1e6+10;
const int N=2e5+10;
const int SS=1<<20;
const int INFi=1e9;
const ll INFl=1e12;
int val[N],t[N],seg[(SS<<1)+1],wsk[N];
bitset<N>vis;
vi g[N];
void upd(int a,int ind){
  for(ind+=SS;ind>0;ind>>=1) seg[ind]+=a;
}
int Query(int a,int b){
  int res=0;
  for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){
    if(!(a&1)) res+=seg[a+1];
    if(b&1) res+=seg[b-1];
  }
  return res;
}
ll count_swaps(vi v){
  int n=v.size();
  for(int i=0;i<v.size();i++) t[i+1]=v[i];
  for(int i=1;i<=n;i++)
    if(t[i]>0) g[t[i]].push_back(i);
  for(int i=1;i<=n;i++){
    if(t[i]>0) continue;
    int curr=t[i]*(-1);
    int m=g[curr][wsk[curr]++];
    val[m]=(min(m,i)<<1)+1,val[i]=(min(m,i)<<1);
    vis[max(m,i)]=1;
  }
  ll res=0;
  for(int i=1;i<=n;i++){
    upd(1,val[i]);
    if(vis[i]) res+=(ll)Query(val[i]+1,(n<<1));
  }
  return res;
}

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(vi)':
shoes.cpp:31:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(int i=0;i<v.size();i++) t[i+1]=v[i];
      |               ~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15