Submission #197131

#	Time	Username	Problem	Language	Result	Execution time	Memory
197131		quocnguyen1012	Port Facility (JOI17_port_facility)	C++11	78 / 100	6094 ms	159524 KiB

port_facility

#include <bits/stdc++.h>

int hmt() {int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';if(n) x=-x;return x;}
#define in hmt()
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 1e6 + 5;
const int inf = 1e9;
const int mod = 1e9 + 7;

struct segment
{
  int l, r, c;
};
segment seg[maxn];
int idl[maxn * 2], idr[maxn * 2], N;

struct seg_tree
{
  vector<pair<int, int>> ST;
  void init(int n)
  {
    ST.resize(4 * n + 5);
    fill(begin(ST), end(ST), mp(-inf, 0));
  }
  #define lc id << 1
  #define rc id << 1 | 1
  void update(int id, int l, int r, int pos, int val)
  {
    if (l > pos || r < pos)
      return;
    if (l == r){
      ST[id] = mp(val, pos);
      return;
    }
    int mid = (l + r) / 2;
    update(lc, l, mid, pos, val); update(rc, mid + 1, r, pos, val);
    ST[id] = max(ST[lc], ST[rc]);
  }
  pair<int, int> getmax(int id, int l, int r, int L, int R)
  {
    if (L > R) return mp(-inf, -inf);
    if (l > R || L > r)
      return mp(-inf, -inf);
    if (L <= l && r <= R)
      return ST[id];
    int mid = (l + r) / 2;
    return max(getmax(lc, l, mid, L, R), getmax(rc, mid + 1, r, L, R));
  }
  #undef lc
  #undef rc
}st1, st2;

queue<pair<int, int>> Q;

void bfs(int x, int c)
{
  seg[x].c = c;
  pair<int, int> tmp;
  tmp = st1.getmax(1, 1, 2 * N, seg[x].l + 1, seg[x].r - 1);
  while (tmp.fi > seg[x].r){
    int i = idl[tmp.se];
    st1.update(1, 1, 2 * N, seg[i].l, -inf);
    st2.update(1, 1, 2 * N, seg[i].r, -inf);
    Q.emplace(i, 3 - c);
    tmp = st1.getmax(1, 1, 2 * N, seg[x].l + 1, seg[x].r - 1);
  }
  tmp = st2.getmax(1, 1, 2 * N, seg[x].l + 1, seg[x].r - 1);
  while (-tmp.fi < seg[x].l){
    int i = idr[tmp.se];
    st1.update(1, 1, 2 * N, seg[i].l, -inf);
    st2.update(1, 1, 2 * N, seg[i].r, -inf);
    Q.emplace(i, 3 - c);
    tmp = st2.getmax(1, 1, 2 * N, seg[x].l + 1, seg[x].r - 1);
  }
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  N = in;
  st1.init(2 * N); st2.init(2 * N);
  for (int i = 1; i <= N; ++i){
    seg[i].l = in; seg[i].r = in;
    idl[seg[i].l] = i; idr[seg[i].r] = i;
    st1.update(1, 1, 2 * N, seg[i].l, seg[i].r);
    st2.update(1, 1, 2 * N, seg[i].r, -seg[i].l);
  }
  int ans = 1;
  for (int i = 1; i <= N; ++i){
    if (seg[i].c == 0){
      st1.update(1, 1, 2 * N, seg[i].l, -inf);
      st2.update(1, 1, 2 * N, seg[i].r, -inf);
      Q.emplace(i, 1);
      while (Q.size()){
        auto now = Q.front(); Q.pop();
        bfs(now.fi, now.se);
      }
      ans = ans * 2 % mod;
    }
  }
  sort(seg + 1, seg + 1 + N, [&](const segment & x, const segment & y){
    return x.l < y.l;
  });
  for (int i = 1; i <= N; ++i){
    pair<int, int> c1 = st1.getmax(1, 1, 2 * N, seg[i].l, seg[i].r);
    pair<int, int> c2 = st2.getmax(1, 1, 2 * N, seg[i].l, seg[i].r);
    if (c1.fi != -inf && (c1.fi == seg[i].c || -c2.fi == seg[i].c)){
      cout << 0;
      return 0;
    }
    st1.update(1, 1, 2 * N, seg[i].r, seg[i].c);
    st2.update(1, 1, 2 * N, seg[i].r, -seg[i].c);
  }
  cout << ans;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:89:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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