Submission #535810

#	Time	Username	Problem	Language	Result	Execution time	Memory
535810		makanhulia	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1 ms	212 KiB

shoes

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

int posi[400000+5];
int arr[200005];

int build(int a, int b, int id) {
  if(a == b) return posi[id] = arr[a];
  int mid = (a+b)/2;
  return posi[id] = build(a, mid, id*2)+build(mid+1, b, id*2+1);
}

void update(int a, int b, int id, int pos, int val) {
  if(a == pos && b == pos) {
    arr[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();
  int tracker[s.size()+1][3];
  queue <int> findposi[s.size()+1][3];
  memset(tracker, 0, sizeof(tracker));

  for(int i = 0; i<n; i++) arr[i] = s[i];

  build(0, n-1, 1);

  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(tracker[abs(s[i])][!neutral] > 0) {
      tracker[abs(s[i])][!neutral]--;
      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);

      total2 += b-a-total1-neutral;

      update(0, n-1, 1, a, 0);
      update(0, n-1, 1, b, 0);
      
    }
    else {
      tracker[abs(s[i])][neutral]++;
      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: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15