Submission #1023821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023821		TraianDanciu	Port Facility (JOI17_port_facility)	C++17	78 / 100	2646 ms	104292 KiB

port_facility

#include <stdio.h>
#include <stdlib.h>

#define MAXN 1000000
#define INFINIT 2000000000
#define MOD 1000000007

int l[MAXN], r[MAXN], idx[2 * MAXN + 1], viz[MAXN];

static inline int max(int a, int b) {
  return a > b ? a : b;
}

int aint[2][8 * MAXN], n, qpos, qval, qleft, qright, which;
  
void _update(int node, int left, int right) {
  int middle;
  
  if(left == right) {
    aint[which][node] = qval;
  } else {
    middle = (left + right) / 2;
    if(qpos <= middle) {
      _update(2 * node + 1, left, middle);
    } else {
      _update(2 * node + 2, middle + 1, right);
    }
    
    aint[which][node] = max(aint[which][2 * node + 1],
                            aint[which][2 * node + 2]);
  }
}
void update(int care, int poz, int val) { // wrapper
  which = care;
  qpos = poz;
  qval = val;
  _update(0, 1, 2 * n);
}

int _query(int node, int left, int right) {
  int middle, ans;
  
  if(qleft <= left && right <= qright) {
    return aint[which][node];
  }
  
  middle = (left + right) / 2;
  ans = -INFINIT;
  
  if(qleft <= middle) {
    ans = max(ans, _query(2 * node + 1, left, middle));
  }
  if(middle < qright) {
    ans = max(ans, _query(2 * node + 2, middle + 1, right));
  }
  
  return ans;
}
int query(int care, int l, int r) { // wrapper
  qleft = l;
  qright = r;
  which = care;
  return _query(0, 1, 2 * n);
}

int bipartit, part[2][MAXN], sp[2], v[MAXN];

void dfs(int nod) {
  int aux;
  
  update(0, l[nod], -INFINIT);
  update(1, r[nod], -INFINIT);
  viz[nod] = 1;
  part[v[nod]][sp[v[nod]]++] = nod;
  
  while((aux = query(0, l[nod], r[nod])) > r[nod]) {
    v[idx[aux]] = v[nod] ^ 1;
    dfs(idx[aux]);
  }
  
  while((aux = -query(1, l[nod], r[nod])) < l[nod]) {
    v[idx[aux]] = v[nod] ^ 1;
    dfs(idx[aux]);
  }
}

int check(int which) {
  int i, rez, aux;
  
  for(i = 0; i < sp[which]; i++) {
    update(0, l[part[which][i]], r[part[which][i]]);
    update(1, r[part[which][i]], -l[part[which][i]]);
  }
  
  i = rez = 0;
  while(rez == 0 && i < sp[which]) {
    aux = query(0, l[part[which][i]], r[part[which][i]]);
    if(aux > r[part[which][i]]) {
      rez = 1;
    }
    
    aux = -query(1, l[part[which][i]], r[part[which][i]]);
    if(aux < l[part[which][i]]) {
      rez = 1;
    }
    
    i++;
  }
  
  for(i = 0; i < sp[which]; i++) {
    update(0, l[part[which][i]], -INFINIT);
    update(1, r[part[which][i]], -INFINIT);
  }
  
  return rez;
}

int main() {
  int i, ans;
  
  scanf("%d", &n);
  for(i = 0; i <= 8 * n; i++) {
    aint[0][i] = aint[1][i] = -INFINIT;
  }
  
  for(i = 0; i < n; i++) {
    scanf("%d%d", &l[i], &r[i]);
    update(0, l[i], r[i]);
    update(1, r[i], -l[i]);
    idx[l[i]] = idx[r[i]] = i;
  }
  
  i = 0;
  bipartit = ans = 1;
  while(i < n && bipartit) {
    if(viz[i] == 0) {
      sp[0] = sp[1] = 0;
      dfs(i);
      
      if(check(0) || check(1)) {
        bipartit = 0;
      }
      
      ans += ans;
      if(ans >= MOD) {
        ans -= MOD;
      }
    }
    
    i++;
  }
  
  printf("%d\n", bipartit ? ans : 0);
  return 0;
}

Compilation message (stderr)

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

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