Submission #1000584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000584		AdamGS	Port Facility (JOI17_port_facility)	C++17	100 / 100	3217 ms	819656 KiB

port_facility

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll MOD=1e9+7;
const int LIM=1e6+7;
vector<pair<int,int>>V[LIM];
ll ans=1;
pair<int,int>T[LIM];
int kol[LIM], tr[8*LIM], kto[8*LIM], trmi[8*LIM], N=1;
void DFS(int x, int o) {
  for(auto i : V[x]) {
    if(!kol[i.st]) {
      kol[i.st]=kol[x]^i.nd;
      DFS(i.st, x);
    } else if((kol[i.st]^i.nd)!=kol[x]) ans=0;
  }
}
void dodaj(int a, int b) {
  if(b==-1) return;
  if(T[b].st<T[a].st) {
    V[a].pb({b, 3});
    V[b].pb({a, 3});
  }
}
void upd(int l, int r, int x, int a) {
  if(l>r) return;
  l+=N; r+=N;
  tr[l]=max(tr[l], x);
  dodaj(a, trmi[l]);
  tr[r]=max(tr[r], x);
  dodaj(a, trmi[r]);
  while(l/2!=r/2) {
    if(l%2==0) {
      tr[l+1]=max(tr[l+1], x);
      dodaj(a, trmi[l+1]);
    }
    if(r%2==1) {
      tr[r-1]=max(tr[r-1], x);
      dodaj(a, trmi[r-1]);
    }
    l/=2; r/=2;
  }
}
vector<pair<int,int>>zejdz(int v, int a, int b) {
  trmi[v]=-1;
  if(a==b) {
    if(kto[a]==-1) return {};
    trmi[v]=kto[a];
    return {{T[kto[a]].st, kto[a]}};
  }
  int mid=(a+b)/2;
  vector<pair<int,int>>A=zejdz(2*v, a, mid), B=zejdz(2*v+1, mid+1, b);
  vector<pair<int,int>>C;
  int l=0;
  for(auto i : A) {
    while(l<B.size() && B[l]<=i) C.pb(B[l++]);
    C.pb(i);
  }
  while(l<B.size()) C.pb(B[l++]);
  l=0;
  while(l+1<C.size() && C[l+1].st<=tr[v]) {
    V[C[l].nd].pb({C[l+1].nd, 0});
    V[C[l+1].nd].pb({C[l].nd, 0});
    ++l;
  }
  if(C.size()) trmi[v]=C[0].nd; else trmi[v]=-1;
  return C;
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  while(N<2*n) N*=2;
  rep(i, 2*N) tr[i]=-MOD;
  rep(i, N) kto[i]=-1;
  rep(i, n) {
    cin >> T[i].st >> T[i].nd;
    --T[i].st; --T[i].nd;
  }
  sort(T, T+n);
  rep(i, n) kto[T[i].nd]=i;
  zejdz(1, 0, N-1);
  rep(i, n) upd(T[i].st+1, T[i].nd-1, T[i].st-1, i);
  zejdz(1, 0, N-1);
  rep(i, n) if(!kol[i]) {
    kol[i]=1;
    DFS(i, i);
    ans=(ans*2)%MOD;
  }
  cout << ans << '\n';
}

Compilation message (stderr)

port_facility.cpp: In function 'std::vector<std::pair<int, int> > zejdz(int, int, int)':
port_facility.cpp:62:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     while(l<B.size() && B[l]<=i) C.pb(B[l++]);
      |           ~^~~~~~~~~
port_facility.cpp:65:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   while(l<B.size()) C.pb(B[l++]);
      |         ~^~~~~~~~~
port_facility.cpp:67:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   while(l+1<C.size() && C[l+1].st<=tr[v]) {
      |         ~~~^~~~~~~~~

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