Submission #1155932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155932		lambd47	Port Facility (JOI17_port_facility)	C++20	0 / 100	0 ms	320 KiB

port_facility

#include <bits/stdc++.h>

#define int long long
using namespace std;


std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int MOD=1e9+7;
const int MX=1e6+7;

pair<int,int> seg[8*MX];//tudo pra 

void update(int pos, int ini, int fim, int id, int val){
    if(ini>id || fim<id)return;
    if(ini==fim){
        seg[pos]={val,ini};
        return;
    }
    int e=2*pos,d=2*pos+1;
    int m=(ini+fim)/2;
    update(e,ini,m,id,val);
    update(d,m+1,fim,id,val);
    seg[pos]=min(seg[e],seg[d]);
}
pair<int,int> query(int pos, int ini, int fim, int l, int r){
    if(ini>r || fim<l)return {MOD,MOD};
    if(l<=ini && fim<=r)return seg[pos];
    int e=2*pos,d=2*pos+1;
    int m=(ini+fim)/2;
    return min(query(e,ini,m,l,r),query(d,m+1,fim,l,r));
}


void solve() {
    int n;cin>>n;
    vector<array<int,2>> evs;//posicao,complementar
    evs.reserve(2*n);
    vector<vector<int>> adj(2*n+1);
    vector<int> ls;
    vector<pair<int,int>> q;
    for(int i=1;i<=n;i++){
        int l,r;cin>>l>>r;
        ls.push_back(l);
        q.push_back({l,r});
        evs.push_back({l,r});
        evs.push_back({r,l});
    }
    sort(evs.begin(),evs.end());
    for(int i=1;i<=8*n;i++){
        seg[i]={MOD,MOD};
    }
    
    for(auto [l,r]:evs){
        if(l<r){
            //botando o cara;
            update(1,1,2*n,r,l);
            auto [val,id]=query(1,1,2*n,l,r);

//            cout<<l<<" "<<val<<"\n";
            if(val<l){
                adj[val].push_back(l);
                adj[l].push_back(val);
            }
        }
        else{
            swap(l,r);
            update(1,1,2*n,r,MOD);
        }
    }

    int comp=0;
    vector<int> color(2*n+1,-1);
    auto bfs=[&](auto&& self,int node, int pai)->void{
        for(auto a:adj[node]){
            if(a==pai)continue;
            color[a]=color[node]^1;
            self(self,a,node);
        }
 //       cout<<node<<" "<<pai<<"\n";
    };
    for(auto l: ls){
        if(color[l]==-1){
            color[l]=0;
            bfs(bfs,l,l);
            comp++;
        }
    }


    stack<int> s[2];
    for(auto [a,b]:evs){
        if(a<b){
            s[color[a]].push(a);
        }
        else{
            if(s[color[b]].top()!=b){
                cout<<0;return;
            }
            s[color[b]].pop();
        }
    }


    int respat=1;
    int potat=2;
    for(int i=0;i<30;i++){

        if(comp&(1<<i)){
            respat*=potat;
            respat%=MOD;
        }
        potat*=potat;
        potat%=MOD;
    }
    cout<<respat;


}
 
int32_t main() {
    std::cin.tie(0)->sync_with_stdio(0); 
    std::cin.exceptions(std::cin.failbit);

    int T = 1;
//    std::cin >> T;
    while(T--) {
        solve();
    }

	return 0;
}

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