Submission #24294

#	Time	Username	Problem	Language	Result	Execution time	Memory
24294		jiaqiyang	Port Facility (JOI17_port_facility)	C++14	78 / 100	3500 ms	473028 KiB

port_facility

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

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, MOD = 1000000007;

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

std::vector<int> adj[N];

void link(int a, int b) {
  adj[a].push_back(b);
  adj[b].push_back(a);
}

std::vector<int> pool[N];

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

void query(int p, int v) {
  for (; p; p ^= p & -p) {
    if (pool[p].empty()) continue;
    int x = pool[p].back();
    if (b[x] < a[v]) continue;
    for (; !pool[p].empty(); pool[p].pop_back()) {
      int u = pool[p].back();
      if (b[u] >= a[v]) link(u, v); else break;
    }
    pool[p].push_back(x);
  }
}

int tag[N];

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

void dfs(int a) {
  int c = 3 - tag[a];
  for (auto b : adj[a]) {
    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; 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:100: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: 0 / 22