Submission #232466

#	Time	Username	Problem	Language	Result	Execution time	Memory
232466		AlexLuchianov	Port Facility (JOI17_port_facility)	C++14	78 / 100	6083 ms	661592 KiB

port_facility

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <stack>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 1000000;
int const modulo = 1000000007;

struct Port{
  int x;
  int y;
  bool operator < (Port const &a) const {
    return y < a.y;
  }
} v[1 + nmax];

int seen[1 + nmax];
vector<int> g[1 + nmax];

void addedge(int x, int y){
  g[x].push_back(y);
  g[y].push_back(x);
}

namespace SegmentTree{
  vector<vector<int>> aint;
  void initialize(int n){
    aint.resize(1 + 4 * n);
  }
  void update(int node, int from, int to, int x, int y, int id){
    if(from == x && to == y)
      aint[node].push_back(id);
    else {
      int mid = (from + to)/ 2;
      if(x <= mid)
        update(node * 2, from, mid, x, MIN(y, mid), id);
      if(mid + 1 <= y)
        update(node * 2 + 1, mid + 1, to, MAX(mid + 1, x), y, id);
    }
  }
  void query(int node, int from, int to, int x, int id){
    for(int i = 0; i < aint[node].size(); i++){
      int val = aint[node][i];
      addedge(val, id);
    }
    while(1 < aint[node].size())
      aint[node].pop_back();

    if(from < to){
      int mid = (from + to) / 2;
      if(x <= mid)
        query(node * 2, from, mid, x, id);
      else
        query(node * 2 + 1, mid + 1, to, x, id);
    }
  }
}

void dfs(int node, int color){
  seen[node] = color;
  for(int h = 0; h < g[node].size(); h++){
    int to = g[node][h];
    if(seen[to] == 0)
      dfs(to, 3 - color);
  }
}

stack<int> st[3];
int event[1 + 2 * nmax];

bool valid(int n){
  for(int i = 1;i <= n; i++) {
    event[v[i].x] = i;
    event[v[i].y] = -i;
  }
  for(int i = 1;i <= 2 * n; i++){
    if(0 < event[i])
      st[seen[event[i]]].push(event[i]);
    else {
      int id = -event[i];
      if(0 == st[seen[id]].size() || st[seen[id]].top() != id)
        return 0;

      st[seen[id]].pop();
    }
  }
  return 1;
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;
  for(int i = 1; i <= n; i++)
    cin >> v[i].x >> v[i].y;
  sort(v + 1, v + n + 1);
  SegmentTree::initialize(2 * n);
  int lim = 2 * n;
  for(int i = 1; i <= n; i++){
    SegmentTree::query(1, 1, lim, v[i].x, i);
    SegmentTree::update(1, 1, lim, v[i].x + 1, v[i].y - 1, i);
  }
  int result = 1;

  for(int i = 1;i <= n; i++)
    if(seen[i] == 0) {
      dfs(i, 1);
      result = 1LL * result * 2 % modulo;
    }
  if(valid(n) == 1)
    cout << result;
  else
    cout << 0;
  return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'void SegmentTree::query(int, int, int, int, int)':
port_facility.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < aint[node].size(); i++){
                    ~~^~~~~~~~~~~~~~~~~~~
port_facility.cpp: In function 'void dfs(int, int)':
port_facility.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~

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