Submission #131975

#	Time	Username	Problem	Language	Result	Execution time	Memory
131975		Just_Solve_The_Problem	Seats (IOI18_seats)	C++11	Compilation error	0 ms	0 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
#include "grader.cpp"

using namespace std;

const int N = (int)1e6 + 7;

vector <int> vec;
int n;

struct T {
  pair <int, int> tree[N * 4];
  int add[N * 4];
  T() {
  }
  
  void push(int v, int l, int r) {
    if (add[v] == 0) return ;
    if (l != r) {
      add[v + v] += add[v];
      add[v + v + 1] += add[v];
    }
    tree[v].first += add[v];
    add[v] = 0;
  }
  
  pair <int, int> gather(pair <int, int> l, pair <int, int> r) {
    pair <int, int> res;
    if (l.first == r.first) {
      res = l;
      res.second += r.second;
    } else if (l.first < r.first) {
      res = l;
    } else {
      res = r;
    }
    return res;
  }
  
  void build(int v = 1, int l = 0, int r = n - 1) {
    if (l == r) {
      tree[v] = {0, 1};
      add[v] = 0;
      return ;
    }
    int mid = (l + r) >> 1;
    build(v + v, l, mid);
    build(v + v + 1, mid + 1, r);
    tree[v] = gather(tree[v + v], tree[v + v + 1]);
  }
  
  void upd(int l, int r, int val, int v = 1, int tl = 0, int tr = n - 1) {
    push(v, tl, tr);
    if (tl > r || tr < l) return ;
    if (l <= tl && tr <= r) {
      add[v] += val;
      push(v, tl, tr);
      return ;
    }
    int mid = (tl + tr) >> 1;
    upd(l, r, val, v + v, tl, mid);
    upd(l, r, val, v + v + 1, mid + 1, tr); 
    tree[v] = gather(tree[v + v], tree[v + v + 1]);
    //cout << v << ' ' << tl << ' ' << tr << ' ' << tree[v].first << ' ' << tree[v].second << endl;
  }
  
  pair <int, int> get(int l, int r, int v = 1, int tl = 0, int tr = n - 1) {
    push(v, tl, tr);
    if (tl > r || tr < l) return {1e9, 0};
    if (l <= tl && tr <= r) return tree[v];
    int mid = (tl + tr) >> 1;
    return gather(get(l, r, v + v, tl, mid), get(l, r, v + v + 1, mid + 1, tr));
  }
};
T tr;

vector <int> r, c;

int getval(int x) {
  int val = 0;
  val += (c[x] == 0 || vec[c[x] - 1] > x);
  val += (c[x] == n - 1 || vec[c[x] + 1] > x);
  return val;
}

void add(int x) {
  int val = getval(x);
  if (val == 2) {
    tr.upd(x, n - 1, 2);
  } else if (val == 0) {
    tr.upd(x, n - 1, -2);
  }
}

void del(int x) {
  int val = getval(x);
  if (val == 2) {
    tr.upd(x, n - 1, -2);
  } else if (val == 0) {
    tr.upd(x, n - 1, 2);
  }
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  r = R;
  c = C;
  n = H * W;
  tr.build();
  vec.resize(n);
  for (int i = 0; i < n; i++) {
    vec[C[i]] = i;
  }
  for (int i = 0; i < n; i++) {
    add(i);
  }
  //for (int to : vec) {
    //cout << to << ' ';
  //}
  //cout << endl;
  //for (int i = 0; i < n; i++) {
    //cout << tr.get(i, i).first << ' ';
  //}
  //cout << endl;
  //cout << tr.get(0, n - 1).second << endl;
}

int used[N];

void rollback(int x) {
  if (!used[x]) {
    del(x);
    used[x] = 1;
  }
  if (c[x] > 0 && !used[vec[c[x] - 1]]) {
    used[vec[c[x] - 1]] = 1;
    del(vec[c[x] - 1]);
  }
  if (c[x] + 1 < n && !used[vec[c[x] + 1]]) {
    used[vec[c[x] + 1]] = 1;
    del(vec[c[x] + 1]);
  }
}

void add1(int x)  {
  if (used[x] == 1) {
    add(x);
    used[x] = 0;
  }
  if (c[x] > 0 && used[vec[c[x] - 1]]) {
    add(vec[c[x] - 1]);
    used[vec[c[x] - 1]] = 0;
  }
  if (c[x] + 1 < n && used[vec[c[x] + 1]]) {
    add(vec[c[x] + 1]);
    used[vec[c[x] + 1]] = 0;
  }
}

int swap_seats(int a, int b) {
  rollback(a);
  rollback(b);
  swap(c[a], c[b]);
  vec[c[a]] = a; vec[c[b]] = b;
  add1(a);
  add1(b);
  //for (int i = 0; i < n; i++) {
    //cout << tr.get(i, i).first << ' ';
  //}
  //cout << endl;
  return tr.get(0, n - 1).second;
}

Compilation message (stderr)

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