제출 #369750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
369750		Mamnoon_Siam	Port Facility (JOI17_port_facility)	C++17	0 / 100	91 ms	148076 KiB

port_facility

#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>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second

string to_string(string s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#ifdef LOCAL
const int N = 1 << 10 | 2;
#else
const int N = 1 << 21 | 2;
#endif

vi ls[N << 1];
int nn = 1, n;
int le[N];
vector<ii> g[N];
int ptr[N << 1];
int vis[N], col[N];
int A[N], B[N];

bool bfs(int source) {
  queue<int> Q;
  vis[source] = 1;
  Q.push(source);
  while(sz(Q)) {
    int u = Q.front();
    Q.pop();
    for(ii v : g[u]) {
      if(vis[v.fi]) {
        if((col[u] ^ v.se) != col[v.fi]) {
          return false;
        }
      } else {
        vis[v.fi] = 1;
        col[v.fi] = col[u] ^ v.se;
        Q.push(v.fi);
      }
    }
  }
  return true;
}

void add_edge(int u, int v, int 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(sz(v) < p 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);
  }
}*/

void doshit(int l, int r, int k, int id) {
  ++l;
  for(l += nn, r += nn; l < r; l >>= 1, r >>= 1) {
    if(l & 1) prefix(l++, k, id);
    if(r & 1) prefix(--r, k, id);
  }
}

int main(int argc, char const *argv[])
{
  cin.sync_with_stdio(0); cin.tie(0);
  cin.exceptions(cin.failbit);
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  scanf("%d", &n);
  while(nn < n*2) nn <<= 1;
  debug(nn);
  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) {
    merge(all(ls[i<<1]), all(ls[i<<1|1]), back_inserter(ls[i]), [](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);
    }
  }
  for(int i = 0; i < n; ++i) debug(i, g[i]);
  const int md = 1e9 + 7;
  int ans = 1;
  for(int i = 0; i < n; ++i) {
    if(!vis[i]) {
      if(!bfs(i)) {
        puts("0");
        return 0;
      } else {
        if((ans <<= 1) >= md)
          ans -= md;
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

port_facility.cpp: In function 'int main(int, const char**)':
port_facility.cpp:56:20: warning: statement has no effect [-Wunused-value]
   56 | #define debug(...) 42
      |                    ^~
port_facility.cpp:134:3: note: in expansion of macro 'debug'
  134 |   debug(nn);
      |   ^~~~~
port_facility.cpp:56:20: warning: statement has no effect [-Wunused-value]
   56 | #define debug(...) 42
      |                    ^~
port_facility.cpp:151:30: note: in expansion of macro 'debug'
  151 |   for(int i = 0; i < n; ++i) debug(i, g[i]);
      |                              ^~~~~
port_facility.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  132 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
port_facility.cpp:136:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  136 |     scanf("%d %d", &A[i], &B[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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