Submission #535496

#	Time	Username	Problem	Language	Result	Execution time	Memory
535496		devariaota	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1 ms	1876 KiB

shoes

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
const ll MOD=1e9+7;
using namespace std;
ll a[200005],node[800005];
void build(ll now,ll l,ll r){
  if(l==r){
    node[now]=a[l];
    return;
  }
  ll m=(l+r)/2;
  build(now*2,l,m);
  build(now*2+1,m+1,r);
  node[now]=node[now*2]+node[now*2+1];
}
ll query(ll now,ll l,ll r,ll x,ll y){
  if(l>r){
    return 0;
  }
  if(x<=l&&r<=y){
    return node[now];
  }
  if(y<l||x>r){
    return 0;
  }
  ll m=(l+r)/2;
  return query(now*2,l,m,x,y)+query(now*2+1,m+1,r,x,y);
}
void update(ll now,ll l,ll r,ll x,ll val){
  if(r<x||x<l){
    return;
  }
  if(l==r){
    node[now]=val;
    return;
  }
  ll m=(l+r)/2;
  update(now*2,l,m,x,val);
  update(now*2+1,m+1,r,x,val);
  node[now]=node[now*2]+node[now*2+1];
}
map <ll,ll> mp;
ll count_swaps(vector <int> vec){
  ll N=vec.size();
  ll a[200005];
  for(int i=1;i<=vec.size();i++){
    a[i]=vec[i-1];
  }
  build(1,1,N);
  ll catat=0;
  for(int i=1;i<=N;i++){
    if(mp[-a[i]]==0){
      update(1,1,N,i,1);
      mp[a[i]]=i;
    }
    else{
      if(a[i]>0){
        ll r=i;
        ll l=mp[-a[i]];
        catat+=(r-l-1);
        catat-=query(1,1,N,l+1,r-1);
        mp[a[i]]=0;
        mp[-a[i]]=0;
        update(1,1,N,l,0);
        update(1,1,N,r,0);
      }
      else{
        ll r=i;
        ll l=mp[-a[i]];
        catat+=(r-l);
        catat-=query(1,1,N,l+1,r-1);
        mp[a[i]]=0;
        mp[-a[i]]=0;
        update(1,1,N,l,0);
        update(1,1,N,r,0);
      }
    }
  }
  return catat;
}
//int main(){
//  ll N;
//  cin>>N;
//  vector <ll> test;
//  for(int i=1;i<=N;i++){
//    ll temp;
//    cin>>temp;
//    test.push_back(temp);
//  }
//  cout<<count_swaps(test)<<endl;
//}

Compilation message (stderr)

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

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