제출 #232482

#제출 시각아이디문제언어결과실행 시간메모리
232482AlexLuchianovPort Facility (JOI17_port_facility)C++14
78 / 100
6101 ms730996 KiB
#pragma GCC optimize("O3")

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

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 = 2000000;
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<int> aint[1 + nmax * 5];
  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){
  queue<int> q;
  q.push(node);
  seen[node] = color;
  while(0 < q.size()){
    int node = q.front();
    q.pop();

    for(int h = 0; h < g[node].size(); h++){
      int to = g[node][h];
      if(seen[to] == 0) {
        q.push(to);
        seen[to] = 3 - seen[node];
      }
    }
  }
}

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);
  int lim = 2 * n;
  for(int i = 1; i <= n; i++){
    SegmentTree::query(1, 1, lim, v[i].x, i);
    if(v[i].x + 1 <= v[i].y - 1)
      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;
}

컴파일 시 표준 에러 (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:75:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[node].size(); h++){
                    ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...