Submission #108797

#	Time	Username	Problem	Language	Result	Execution time	Memory
108797		rajarshi_basu	Port Facility (JOI17_port_facility)	C++14	0 / 100	2 ms	384 KiB

port_facility

#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
//#include <string>
//#include <map>
//#include <complex>
//#include <chrono>
//#include <random>
#include <stack>
//#include <set>
//#include <fstream>
 
#define FOR(i,n) for(int i = 0;i < n; i++)
#define FORE(i,a,b) for(int i = a; i <= b ; i++)
#define ss second
#define ff first
#define ll long long int
#define ii pair<ll,ll>
#define il pair<int,ll>
#define li pair<ll,int>
#define x ff
#define y ss
#define lii pair<ll,pair<int,int> > 
#define piil pair<int ,pair<int,int> > 
#define iii pair<pair<int,int>,int> 
#define pll pair<ll,ll>
#define vi vector<int>
#define pb push_back
#define mp make_pair
 

 
using namespace std;
 
const ll INF = 1e18;
const int MAXN = 2e6+1;
const int MOD = 1e9+7;
ii all[MAXN];

int BIT[MAXN+1];
int query(int x){
    int sum = 0;
    while(x > 0){
        sum += BIT[x];
        x -= x&-x;
    }
    return sum;
}
void update(int x,int val){
    while(x <= MAXN){
        BIT[x] += val;
        x += x&-x;
    }
}

ll fxp(ll a,ll b){
    if(b == 0)return 1;
    if(b%2 == 1)return (a*fxp(a,b-1))%MOD;
    else{
        ll x = fxp(a,b/2);
        return (x*x)%MOD;
    }
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    FOR(i,n)cin >> all[i].ff >> all[i].ss;
    sort(all,all+n);

    // check if the graph is bipartite

    stack<ii> s1;
    stack<ii> s2;
    bool bad = 0;
    FOR(i,n){
        ii e = all[i];
        if(s1.empty())s1.push(e);
        else if(s2.empty())s2.push(e);
        else{
            while(!s1.empty() and s1.top().ss < e.ff)s1.pop();
            while(!s2.empty() and s2.top().ss < e.ff)s2.pop();
                
            if(s1.empty() or s1.top().ss > e.ss){
                s1.push(e);
            }else if(s2.empty() or s2.top().ss > e.ss){
                s2.push(e);
            }else{
                bad = 1;
                break;
            }
        }
    }   
    if(bad){
        cout << 0 << endl;
        return 0;
    }

    // since graph is not bipartite, lets find number of components
    int edges = 0;
    FOR(i,n){
        edges += query(all[i].ss)-query(all[i].ff);
        update(all[i].ss,1);
    }

    int C = n-edges;
    cout << fxp(2,C) << endl;

    return 0;
}

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