Submission #369828

#	Time	Username	Problem	Language	Result	Execution time	Memory
369828		Mamnoon_Siam	Port Facility (JOI17_port_facility)	C++17	100 / 100	3597 ms	297836 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];
int ptr[N << 1];
int A[N], B[N];

int par[N], dis[N];
int find(int u) {
  if(par[u] == u) return u;
  int p = find(par[u]);
  dis[u] ^= dis[par[u]];
  return par[u] = p;
}
bool unite(int u, int v, int c) {
  int pu = find(u), pv = find(v);
  if(pu == pv) {
    return (dis[u] ^ dis[v]) == c;
  } else {
    if((dis[u] ^ dis[v]) != c) dis[pu] = 1;
    par[pu] = pv;
    return true;
  }
}

void add_edge(int u, int v, int c) {
  if(!unite(u, v, c)) {
    puts("0");
    exit(0);
  }
  /*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[])
{
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  // cout << sizeof(array<int, 3>) << endl;
  scanf("%d", &n);
  iota(par, par+n, 0);
  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);
    }
  }

  // return 0;
  const int md = 1e9 + 7;
  int ans = 1;
  for(int i = 0; i < n; ++i) {
    if(find(i) == i) {
      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:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
port_facility.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |     scanf("%d %d", &A[i], &B[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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