Submission #533515

#	Time	Username	Problem	Language	Result	Execution time	Memory
533515		devariaota	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	267 ms	277528 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#define ll long long

const int neg = 1e5;

ll seg[800505];
queue<int> pos[400005];
bool vis[400005];

void update(int l, int r, int x, int loc) {
  if (l <= x && x<= r) {
    //cout << l << " " << r << endl;
    seg[loc]++;
    if (l != r) {  
      int mid = (l + r) / 2;
      update(l, mid, x, loc * 2);
      update(mid + 1, r, x, loc * 2 + 1);
    }
  }
    
}

ll query(int l, int r, int x, int y, int loc) {
  //cout << l << " " << r << endl;
  //cout << l << " " << r << endl;
  if(x <= l && r <= y) {
    return seg[loc];
  }
  if (l >= y || r <= x) {
    return 0;
  }
  if (l != r) {
    int mid = (l + r) / 2;
    return query(l, mid, x, y, loc * 2) + query(mid + 1, r, x, y, loc * 2 + 1);
  }
  return 0;
}

long long count_swaps(std::vector<int> s) {
  int n = s.size();
  ll ans = 0;
  for(int i = 0; i < n; i++) {
    pos[s[i] + neg].push(i + 1); 
  }
  
  for(int i = 0; i < n; i++) {
    if (vis[i + 1]) {
      continue;
    }
    else {
      //cout << "::" << i << endl;
      int next = -s[i] + neg;
      if (s[i] > 0) {
        ans++;
      }
      //cout << s[i] << " " << next - neg << endl;
      int r = pos[next].front();
      //cout << r << endl;
      pos[next].pop();
      pos[s[i] + neg].pop();
      vis[i + 1] = true;
      vis[r] = true;
      ans += (r - (i + 1) - 1) - query(1, n, i + 1, r, 1);
      //cout << "---" << ans << endl;
      update(1, n, r, 1);
      
    }
  }
  return ans;
  
}

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