Submission #369788

#	Time	Username	Problem	Language	Result	Execution time	Memory
369788		Mamnoon_Siam	Port Facility (JOI17_port_facility)	C++17	78 / 100	5725 ms	1048580 KiB

port_facility

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;

/* sorry, this is the bare minimum :'( */
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
// using vi = deque<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second

const int N = 1 << 21 | 2;

vi ls[N << 1];
int nn = 1, n;
int le[N];
vector<ii> g[N];
int ptr[N << 1];
int vis[N], col[N];
int A[N], B[N];
int cnt[N];
vector<array<int, 3>> edges;

bool bfs(int source) {
  queue<int> Q;
  vis[source] = 1;
  Q.push(source);
  while(sz(Q)) {
    int u = Q.front();
    Q.pop();
    for(ii v : g[u]) {
      if(vis[v.fi]) {
        if((col[u] ^ v.se) != col[v.fi]) {
          return false;
        }
      } else {
        vis[v.fi] = 1;
        col[v.fi] = col[u] ^ v.se;
        Q.push(v.fi);
      }
    }
  }
  return true;
}

void add_edge(int u, int v, int c) {
  cnt[u]++, cnt[v]++;
  edges.push_back({u, v, c});
  // g[u].emplace_back(v, c);
  // g[v].emplace_back(u, c);
}

void prefix(int u, int k, int id) {
  vi& v = ls[u];
  int& p = ptr[u];
  if(sz(v) and A[v[0]] < k) {
    add_edge(id, v[0], 1);
    while(p < sz(v) and A[v[p]] < k)
      ++p;
  }
}

void doshit(int l, int r, int k, int id) { // (l, r), < k
  for(l += nn, r += nn; l+1 < r; l >>= 1, r >>= 1) {
    if(~l & 1) prefix(l ^ 1, k, id);
    if(r & 1) prefix(r ^ 1, k, id);
  }
}

int main(int argc, char const *argv[])
{
  cin.sync_with_stdio(0); cin.tie(0);
  cin.exceptions(cin.failbit);
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  edges.reserve(40*N);
  scanf("%d", &n);
  while(nn < n*2) nn <<= 1;
  for(int i = 0; i < n; ++i) {
    scanf("%d %d", &A[i], &B[i]);
    A[i]--, B[i]--;
    ls[B[i] + nn].emplace_back(i);
  }
  for(int i = nn-1; i >= 1; --i) {
    ls[i].resize(sz(ls[i<<1])+sz(ls[i<<1|1]));
    merge(all(ls[i<<1]), all(ls[i<<1|1]), ls[i].begin(), [](int x, int y){ return A[x] < A[y]; });
  }
  for(int i = 0; i < n; ++i) {
    doshit(A[i], B[i], A[i], i);
  }
  for(int i = nn-1; i >= 1; --i) {
    for(int j = 1; j < ptr[i]; ++j) {
      add_edge(ls[i][j-1], ls[i][j], 0);
    }
  }
  for(int i = 0; i < n; ++i) g[i].reserve(cnt[i]);
  for(array<int, 3> e : edges) {
    g[e[0]].emplace_back(e[1], e[2]);
    g[e[1]].emplace_back(e[0], e[2]);
  }
  // return 0;
  const int md = 1e9 + 7;
  int ans = 1;
  for(int i = 0; i < n; ++i) {
    if(!vis[i]) {
      if(!bfs(i)) {
        puts("0");
        return 0;
      } else {
        if((ans <<= 1) >= md)
          ans -= md;
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main(int, const char**)':
port_facility.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
port_facility.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |     scanf("%d %d", &A[i], &B[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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