제출 #1182981

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182981		Ak_16	Arranging Shoes (IOI19_shoes)	C++20	컴파일 에러	0 ms	0 KiB

shoes

#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;

int segt[1000005];

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);
}

long long count_swaps(vector<int> a){
  inf b[1000005];
  saa c[1000005];
  
  int n = a.size()/2;
  int cntl[1000005] = {0};
  int cntr[1000005] = {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[1000005];
  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[1000005];
  for(int i=1; i<=2*n; i++){
    nif[fin[i]]=i;
  }
  long long 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;
  
}

컴파일 시 표준 에러 (stderr) 메시지

/usr/bin/ld: /tmp/ccKwqiEG.o: in function `main':
grader.cpp:(.text.startup+0x289): undefined reference to `count_swaps(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status