Submission #1182966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182966		Ak_16	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	65 ms	8776 KiB

shoes

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int segt[400005];

void build(int x) {
    for (int i = x - 1; i > 0; --i) {
        segt[i] = segt[2 * i] + segt[2 * i + 1];
    }
}

void update(int pos, int value, int x) {
    pos += x - 1;
    segt[pos] = value;
    for (int i=pos/2; i>=1; i/=2) {
        segt[i] = segt[2 * i] + segt[2 * i + 1];
    }
}

int query(int l, int r, int x) {
    l += x - 1;
    r += x - 1;
    int sum = 0;
    while (l <= r) {
        if (l % 2 == 1) sum += segt[l]; l++;
        if (r % 2 == 0) sum += segt[r]; r--;
        l /= 2;
        r /= 2;
    }
    return sum;
}

struct inf{
  int val;
  int ind;
  int cnt;
};

struct saa{
  int n1;
  int n2;
};

bool cmp1(inf p, inf q){
  if(abs(p.val)!=abs(q.val)){
    return abs(p.val)<abs(q.val);
  }
  if(p.cnt!=q.cnt){
    return p.cnt<q.cnt;
  }
  return p.val<q.val;
}

bool cmp2(saa al, saa be){
  return max(al.n1, al.n2) < max(be.n1, be.n2);
}

int count_swaps(vector<int> a){
  inf b[200005];
  saa c[100005];
  
  int n = a.size()/2;
  int cntl[100005] = {0};
  int cntr[100005] = {0};
  int bef[200005] = {0};
  int lasl[100005] = {0};
  int lasr[100005] = {0};
  
  for(int i=1; i<=2*n; i++){
    b[i].val = a[i-1];
    b[i].ind = i;
    
    if(a[i-1]<0){
      cntl[abs(a[i-1])]++;
      b[i].cnt = cntl[abs(a[i-1])];
    }
    
    else{
      cntr[a[i-1]]++;
      b[i].cnt = cntr[a[i-1]];
    }
  }
  
  sort(b+1, b+2*n+1, cmp1);
  
  for(int i=1; i<2*n; i+=2){
    c[(i+1)/2].n1 = b[i].ind;
    c[(i+1)/2].n2 = b[i+1].ind;
  }
  
  sort(c+1, c+n+1, cmp2);
  
  int fin[200005];
  for(int i=1; i<=n; i++){
    fin[2*i-1] = c[i].n1;
    fin[2*i] = c[i].n2;
  }
  for(int i=2*n; i<4*n; i++){
    segt[i]=1;
  }
  build(2*n);
  int nif[200005];
  for(int i=1; i<=2*n; i++){
    nif[fin[i]]=i;
  }
  int ans=0;
  
  for(int i=2*n; i>=1; i--){
    update(nif[i], 0, 2*n);
    ans += query(nif[i]+1, 2*n, 2*n);
  }
  return ans;
  
  
  
  
  
}

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