Submission #294978

#	Time	Username	Problem	Language	Result	Execution time	Memory
294978		ASDF123	Arranging Shoes (IOI19_shoes)	C++17	Compilation error	0 ms	0 KiB

shoes

//#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
#define szof(s) (int)s.size()
//#include <chrono>
//#include <random>
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


using namespace std;

const int N = (int)2e5 + 5;

ll tree[N * 4], lz[N * 4];
unordered_map <int, int> pos;
bool used[N];

void push(int v, int tl, int tr) {
  if (!lz[v]) {
    return;
  }
  if (tl != tr) {
    lz[v + v + 1] += lz[v];
    lz[v + v + 2] += lz[v];
  } else {
    tree[v] += lz[v];
  }
  lz[v] = 0;
}

int get(int pos, int v = 0, int tl = 0, int tr = N) {
  push(v, tl, tr);
  if (tl == tr) {
    return tree[v];
  }
  int mid = (tl + tr) >> 1;
  if (pos <= mid) {
    return get(pos, v + v + 1, tl, mid);
  } else {
    return get(pos, v + v + 2, mid + 1, tr);
  }
}

void upd(int l, int r, ll val, int v = 0, int tl = 0, int tr = N) {
  if (l > r) {
    return;
  }
  push(v, tl, tr);
  if (l <= tl && tr <= r) {
    lz[v] += val;
    push(v, tl, tr);
    return;
  }
  if (l > tr || tl > r) {
    return;
  }
  
  int mid = (tl + tr) >> 1;
  upd(l, r, val, v + v + 1, tl, mid);
  upd(l, r, val, v + v + 2, mid + 1, tr);
}

ll count_swaps(vector<int> s) {
  ll ans = 0;
  int n = szof(s) / 2;
  for (int i = 0; i < n * 2; i++) {
    pos[s[i]] = i;
  }
  for (int i = 0; i < n * 2; i++) {
    if (!used[i]) {
      used[pos[s[i]]] = used[pos[-s[i]]] = 1;
      ll l = pos[s[i]] + get(pos[s[i]]);
      ll r = pos[-s[i]] + get(pos[-s[i]]);
      ans += r - (l + 1);
      if (s[i] > 0) {
        ans++;
      }
      upd(pos[s[i]] + 1, pos[-s[i]] - 1, 1);
    }
  }
  return ans;
}
signed main() {
  int n;
  cin >> n;
  vector <int> s(n);
  for (int &el : s) {
    cin >> el;
  }
  cout << count_swaps(s);
}

Compilation message (stderr)

/tmp/cco59VIm.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccezwBni.o:shoes.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status