QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#209880#5409. PerotationScintillaCompile Error//C++203.6kb2023-10-10 18:45:272023-10-10 18:45:27

Judging History

你现在查看的是最新测评结果

  • [2023-10-10 18:45:27]
  • 评测
  • [2023-10-10 18:45:27]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl

const int N = 1e5 + 10;
const int M = 2e4;

int read() {
  int x = 0, f = 1; char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
  return x * f;
}

int n, m, cnt, B;
int a[N], pos[N], bit[N], id[N], L[M], R[M];
int v[N], b[M][M], d[M][M], c[M];

void upd(int x) {
  for (; x <= n; x += x & -x) bit[x] ^= 1;
}

int qry(int x) {
  int res = 0;
  for (; x; x -= x & -x) res ^= bit[x];
  return res;
}

void psdw(int o) {
  int len = R[o] - L[o] + 1;
  for (int i = 1; i <= len; i++) 
    v[pos[b[o][i]]] = (v[pos[b[o][i-1]]] ^ d[o][i]);
}

void psup(int o) {
  int len = R[o] - L[o] + 1;
  c[o] = 0;
  for (int i = 1; i <= len; i++) 
    c[o] += (d[o][i] = (v[pos[b[o][i]]] ^ v[pos[b[o][i-1]]]));
}

void build() {
  for (int i = 1; i <= n; i++) {
    id[i] = (i - 1) / B + 1;
    if (i == 1 || id[i] != id[i-1]) L[id[i]] = i, cnt++;
    R[id[i]] = max(R[id[i]], i);
  }
  for (int o = 1; o <= cnt; o++) {
    int len = R[o] - L[o] + 1;
    for (int i = 1; i <= len; i++) b[o][i] = a[L[o]+i-1];
    sort(b[o] + 1, b[o] + 1 + len), psup(o);
  }
}

int cg(int o, int x) {
  int len = R[o] - L[o] + 1;
  int p = lower_bound(b[o] + 1, b[o] + 1 + len, x) - b[o];
  int res = ((p - 1) & 1);
  if (p <= len) c[o] -= d[o][p], c[o] += (d[o][p] ^= 1);
  return res;
}

void mdf(int o, int x, int y) {
  int len = R[o] - L[o] + 1, p;
  for (p = 1; p <= len; p++) if (b[o][p] == x) break;
  for (int i = p; i < len; i++) b[o][i] = b[o][i+1];
  for (p = 1; p < len; p++) if (b[o][p] > y) break;
  for (int i = len; i > p; i--) b[o][i] = b[o][i-1];
  b[o][p] = y;
}

void work(int x, int y) {
  if (id[x] == id[y]) {
    psdw(id[x]);
    for (int i = x + 1; i < y; i++) v[i] ^= ((a[i] > a[y]) ^ (a[i] > a[x]));
    for (int i = x; i < y; i++) if (a[y] > a[i]) v[y] ^= 1;
    for (int i = y; i > x; i--) if (a[x] > a[i]) v[x] ^= 1; 
    swap(a[x], a[y]), swap(pos[a[x]], pos[a[y]]), swap(v[x], v[y]);
    return psup(id[x]);
  }
  psdw(id[x]), psdw(id[y]);
  for (int i = x + 1; id[i] == id[x]; i++) v[i] ^= ((a[i] > a[y]) ^ (a[i] > a[x]));
  for (int i = y - 1; id[i] == id[y]; i--) v[i] ^= ((a[i] > a[y]) ^ (a[i] > a[x]));
  for (int i = x; id[i] == id[x]; i++) if (a[y] > a[i]) v[y] ^= 1;
  for (int i = y - 1; id[i] == id[y]; i--) if (a[y] > a[i]) v[y] ^= 1;
  for (int i = x + 1; id[i] == id[x]; i++) if (a[x] > a[i]) v[x] ^= 1;
  for (int i = y; id[i] == id[y]; i--) if (a[x] > a[i]) v[x] ^= 1;
  for (int i = id[x] + 1; i < id[y]; i++) v[x] ^= cg(i, a[x]), v[y] ^= cg(i, a[y]);
  mdf(id[x], a[x], a[y]), mdf(id[y], a[y], a[x]);
  swap(a[x], a[y]), swap(pos[a[x]], pos[a[y]]), swap(v[x], v[y]);
  psup(id[x]), psup(id[y]);
}

int calc() {
  int p = cnt;
  while (p >= 1 && !c[p]) p--;
  if (!p) return 1;
  psdw(p);
  int x = R[p];
  while (x >= L[p] && !v[x]) x--;
  psup(p);
  return x + 1;
}

int main() {
  n = read(), m = read(), B = min(n, int(sqrt(n) / __lg(n + 1) + 1));
  rep(i, 1, n) a[i] = read(), pos[a[i]] = i;
  drep(i, n, 1) v[i] = qry(a[i]), upd(a[i]);
  build();
  rep(i, 1, m) {
    int x = read(), y = read();
    if (x > y) swap(x, y);
    work(x, y);
    printf("%d\n", calc());
  }
  return 0;
}

详细

/tmp/ccQFRYC0.o: in function `upd(int)':
answer.code:(.text+0x436): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccQFRYC0.o
answer.code:(.text+0x441): relocation truncated to fit: R_X86_64_PC32 against symbol `bit' defined in .bss section in /tmp/ccQFRYC0.o
/tmp/ccQFRYC0.o: in function `qry(int)':
answer.code:(.text+0x46e): relocation truncated to fit: R_X86_64_PC32 against symbol `bit' defined in .bss section in /tmp/ccQFRYC0.o
/tmp/ccQFRYC0.o: in function `psdw(int)':
answer.code:(.text+0x49a): relocation truncated to fit: R_X86_64_PC32 against symbol `R' defined in .bss section in /tmp/ccQFRYC0.o
answer.code:(.text+0x4a1): relocation truncated to fit: R_X86_64_PC32 against symbol `L' defined in .bss section in /tmp/ccQFRYC0.o
answer.code:(.text+0x4d9): relocation truncated to fit: R_X86_64_PC32 against symbol `v' defined in .bss section in /tmp/ccQFRYC0.o
answer.code:(.text+0x4e0): relocation truncated to fit: R_X86_64_PC32 against symbol `pos' defined in .bss section in /tmp/ccQFRYC0.o
/tmp/ccQFRYC0.o: in function `psup(int)':
answer.code:(.text+0x5bc): relocation truncated to fit: R_X86_64_PC32 against symbol `R' defined in .bss section in /tmp/ccQFRYC0.o
answer.code:(.text+0x5c3): relocation truncated to fit: R_X86_64_PC32 against symbol `L' defined in .bss section in /tmp/ccQFRYC0.o
answer.code:(.text+0x62a): relocation truncated to fit: R_X86_64_PC32 against symbol `v' defined in .bss section in /tmp/ccQFRYC0.o
answer.code:(.text+0x63b): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status