Submission #535817

#	Time	Username	Problem	Language	Result	Execution time	Memory
535817		christinelynn	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	444 ms	408932 KiB

shoes

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

int posi[800000+5];

void update(int a, int b, int id, int pos, int val) {
  if(a == pos && b == pos) {
    posi[id] = val;
    return;
  }
  int mid =(a+b)/2;
  if(pos <= mid) update(a, mid, id*2, pos, val);
  else update(mid+1, b, id*2+1, pos, val);
  posi[id] = posi[id*2]+posi[id*2+1];
}

int get(int a, int b, int id, int from, int to) {
  if(to < a || from > b) return 0;
  if(from <= a && b <= to) return posi[id];
  int mid = (a+b)/2;
  return get(a, mid, id*2, from, to)+get(mid+1, b, id*2+1, from, to);
}

long long count_swaps(vector<int> s) {
  int n = s.size();
  queue <int> findposi[s.size()+1][3];

  long long total2 = 0;

  for(int i = 0; i<n; i++) {
    //cerr << endl << i << endl << endl;
    bool neutral;
    if(s[i] < 0) neutral = false;
    else neutral = true;

    if(!findposi[abs(s[i])][!neutral].empty()) {
      int a = findposi[abs(s[i])][!neutral].front();
      findposi[abs(s[i])][!neutral].pop();
      int b = i;

      int total1 = get(0, n-1, 1, a+1, b-1);
      //cerr << a << " " << b << endl;
      //cerr << total1 << endl;
      total2 += b-a-total1-neutral;

      update(0, n-1, 1, a, 0);
      update(0, n-1, 1, b, 0);
      
    }
    else {
      update(0, n-1, 1, i, 1);
      findposi[abs(s[i])][neutral].push(i);
    }
  }
  return total2;
}

/*

int main() {
  int n;
  cin >> n;

  vector<int> vec;

  for(int i = 1; i<=n; i++) {
    int a;
    cin >> a;
    vec.push_back(a);
  }

  cout << count_swaps(vec) << endl;
}

*/

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