Submission #24296

#	Time	Username	Problem	Language	Result	Execution time	Memory
24296		jiaqiyang	Port Facility (JOI17_port_facility)	C++14	100 / 100	2383 ms	1040064 KiB

port_facility

#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <cstring>

int nextInt() {
  char ch;
  while (!isdigit(ch = getchar())) {}
  int res = ch - '0';
  while (isdigit(ch = getchar())) res = 10 * res + ch - '0';
  return res;
}

const int N = 2000000 + 10, S = 40 * N, MOD = 1000000007;

int n, a[N], b[N], c[N], id[N];

int adj[N], to[S], next[S];

void link(int a, int b) {
  static int cnt = 2;
  to[cnt] = b;
  next[cnt] = adj[a];
  adj[a] = cnt++;
}

int buffer[S], *pool[N];

void update(int p, int v) {
  for (; p <= 2 * n; p += p & -p) pool[p][++pool[p][0]] = v;
}

void query(int p, int v) {
  for (; p; p ^= p & -p) {
    int &y = pool[p][0];
    if (!y) continue;
    int x = pool[p][y];
    if (b[x] < a[v]) continue;
    for (; y; --y) {
      int u = pool[p][y];
      if (b[u] >= a[v]) link(u, v), link(v, u); else break;
    }
    pool[p][++y] = x;
  }
}

int tag[N];

void fail() {
  puts("0");
  exit(0);
}

void dfs(int a) {
  int c = 3 - tag[a];
  for (int i = adj[a]; i; i = next[i]) {
    int b = to[i];
    if (!tag[b]) {
      tag[b] = c;
      dfs(b);
    } else if (tag[b] != c) {
      fail();
    }
  }
}

class {
  int data[N];
  void add(int p, int v) {
    for (; p <= 2 * n; p += p & -p) data[p] += v;
  }
 public:
  void clear() {
    memset(data, 0, sizeof data);
  }
  void add(int l, int r, int v) {
    add(l, v);
    add(r + 1, -v);
  }
  int query(int p) {
    int res = 0;
    for (; p; p ^= p & -p) res += data[p];
    return res;
  }
} bit;

void check(int y) {
  bit.clear();
  for (int i = 1; i <= 2 * n; ++i) {
    int x = id[i];
    if (tag[x] != y) continue;
    if (c[i] > i) {
      bit.add(1, i, 1);
    } else {
      bit.add(1, c[i], -1);
      if (bit.query(c[i])) fail();
      bit.add(c[i], i, 1);
    }
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1, *top = buffer; i <= 2 * n; ++i) {
    pool[i] = top;
    top += (i & -i) + 1;
  }
  for (int i = 1; i <= n; ++i) a[i] = nextInt(), b[i] = nextInt();
  for (int i = 1; i <= n; ++i) c[a[i]] = b[i], c[b[i]] = a[i], id[a[i]] = id[b[i]] = i;
  for (int i = 1; i <= 2 * n; ++i) {
    if (c[i] > i) continue;
    query(c[i], id[i]);
    update(c[i], id[i]);
  }
  int cnt = 0;
  for (int i = 1; i <= n; ++i) if (!tag[i]) ++cnt, tag[i] = 1, dfs(i);
  check(1);
  check(2);
  int ans = 1;
  while (cnt--) ans = 2 * ans % MOD;
  printf("%d\n", ans);
  return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:103:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 22 / 22