Submission #531772

#	Time	Username	Problem	Language	Result	Execution time	Memory
531772		devariaota	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	150 ms	137340 KiB

shoes

# include <bits/stdc++.h>
using namespace std;

int bit[200005];
queue<int> q[200005];
const int OFFSET = 100000;
int maxn;

int lsone(int x) { return x&(-x); }
int off(int x) { return x+OFFSET; }

int get(int x){
  x++;
  int res = 0;
  for(int i=x; i>0; i-=lsone(i))
    res += bit[i];
  return res;
}

int get(int l, int r){
  return get(r) - get(l);
}

void update(int x, int val){
  x++;
  for(int i=x; i<=maxn; i+=lsone(i))
    bit[i] += val;
}

long long count_swaps(vector<int> shoes){
  long long ans = 0;
  maxn = shoes.size();
  for(int r=0; r<shoes.size(); r++){
    int x = shoes[r];
    if(!q[off(-x)].empty()){
      int l = q[off(-x)].front(); 
      q[off(-x)].pop();
      ans += (r-l);
      if(x > 0) ans--;
      ans -= get(l, r);
      update(l, -1);
    }
    else {
      q[off(x)].push(r);
      update(r, +1);
    }
  }
  return ans;
}

// int main(){
//   int n; cin >> n;
//   vector<int> shoes(n);
//   for(int i=0; i<n; i++){
//     cin >> shoes[i];
//   }
//   cout << count_swaps(shoes) << endl;
// }

Compilation message (stderr)

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

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