Submission #575192

#	Time	Username	Problem	Language	Result	Execution time	Memory
575192		MohammadAghil	Port Facility (JOI17_port_facility)	C++17	100 / 100	2834 ms	634440 KiB

port_facility

      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
    using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
    #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
      #define per(i,r,l) for(int i = (r); i >= (l); i--)
        #define rep(i,l,r) for(int i = (l); i < (r); i++)
           #define all(x) x.begin(), x.end()
              #define sz(x) (int)(x).size()
                  #define pb push_back
                      #define ss second
                           #define ff first
                                   void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 2e6+5, lg = 20, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}

vector<int> seg[maxn<<2];
int ptrl[maxn<<2], ptrr[maxn<<2];
int mtch[maxn], n, vl[maxn], l[maxn], r[maxn];
bool st[maxn], vis[maxn];

void build(int x = 1, int lx = 0, int rx = n<<1){
     if(lx + 1 == rx){
          seg[x].pb(mtch[lx]);
          return;
     }
     int mid = (lx + rx)>>1;
     build(x<<1, lx, mid), build(x<<1|1, mid, rx);
     seg[x].resize(sz(seg[x<<1]) + sz(seg[x<<1|1])), merge(all(seg[x<<1]), all(seg[x<<1|1]), begin(seg[x]));
     ptrr[x] = sz(seg[x])-1;
}

vector<int> res;
void query(int l, int r, int x = 1, int lx = 0, int rx = n<<1){
     if(l <= lx && r >= rx){
          // er(l, r, lx, rx);
          // for(int c: seg[x]) cout << c << ' '; cout << endl;
          while(ptrl[x] <= ptrr[x] && seg[x][ptrl[x]] < l){
               if(!vis[vl[seg[x][ptrl[x]]]]) res.pb(vl[seg[x][ptrl[x]]]);
               vis[vl[seg[x][ptrl[x]]]] = true;
               ptrl[x]++;
          }
          while(ptrr[x] >= ptrl[x] && seg[x][ptrr[x]] >= r){
               if(!vis[vl[seg[x][ptrr[x]]]]) res.pb(vl[seg[x][ptrr[x]]]);
               vis[vl[seg[x][ptrr[x]]]] = true;
               ptrr[x]--;
          }
          return;
     } if(l >= rx || r <= lx) return;
     int mid = (lx + rx)>>1;
     query(l, r, x<<1, lx, mid), query(l, r, x<<1|1, mid, rx);
}

void dfs(int x, int f){
     // er(x, f);
     vis[x] = true;
     query(l[x], r[x]);
     vector<int> adj = res; res.clear();
     for(int c: adj) st[c] = st[x]^1, dfs(c, f);
}

bool chk(){
     vector<int> stk[2];
     rep(i,0,n<<1){
          int cr = vl[i];
          if(i == l[cr]) stk[st[cr]].pb(cr);
          else{
               if(stk[st[cr]].back() == cr) stk[st[cr]].pop_back();
               else return false;
          }
     }
     return true;
}

int main(){
     cin.tie(0) -> sync_with_stdio(0);
     cin >> n;
     rep(i,0,n){
          int a, b; cin >> a >> b; a--, b--;
          mtch[a] = b, mtch[b] = a, vl[a] = vl[b] = i, l[i] = a, r[i] = b + 1;
     }
     build();
     ll ans = 1;
     rep(i,0,n) if(!vis[i]) dfs(i, i), ans = ans*2ll%mod;
     // rep(i,0,n) er(st[i]);
     cout << (chk()?ans:0) << '\n'; 
     return 0; 
}

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