Submission #1023841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023841		TraianDanciu	Port Facility (JOI17_port_facility)	C++17	100 / 100	1933 ms	150604 KiB

port_facility

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

#define MAXN 1000000
#define AINTN 2097152
#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][2 * AINTN], aintn;

void update(int which, int poz, int val) {
  aint[which][poz += aintn - 1] = val;
  while(poz > 1) {
    aint[which][poz >> 1] = max(aint[which][poz],
                                aint[which][poz ^ 1]);
    poz >>= 1;
  }
}

int query(int which, int left, int right) {
  int ans = -INFINIT;
  
  left += aintn - 1;
  right += aintn;
  
  while(left < right) {
    if(left & 1) {
      ans = max(ans, aint[which][left++]);
    }
    if(right & 1) {
      ans = max(ans, aint[which][--right]);
    }
    
    left >>= 1;
    right >>= 1;
  }
  
  return ans;
}

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]) {
    fprintf(stderr, "%d %d\n", nod, aux);
    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 n, i, ans;
  
  scanf("%d", &n);
  aintn = 2 * n;
  while(aintn & (aintn - 1)) {
    aintn += aintn & -aintn;
  }
  for(i = 1; i < 2 * aintn; 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:103:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
port_facility.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |     scanf("%d%d", &l[i], &r[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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