제출 #930026

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
930026		vjudge1	Port Facility (JOI17_port_facility)	C++17	0 / 100	3 ms	15964 KiB

port_facility

//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

const int MOD = int(1e9) + 7;

int Sum(int a , int b){
    int res = a + b;
    if(res > MOD) return res - MOD;
    if(res < 0) return res + MOD;
    return res;
}
int Mul(int a , int b){
    return (1ll * a * b) % MOD;
}
int Pow(int a , int b){
    int res = 1;
    while(b){
        if((b & 1)) res = Mul(res , a);
        a = Mul(a , a) , b >>= 1;
    }
    return res;
}

int n;
vector<int> a , b;
set<int> ord;
int sgs[2000000];
int ms[2000000];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    fill(&ms[0] , &ms[2000000] , -1);
    fill(&sgs[0] , &sgs[2000000] , -1);
    for(int i = 0 ; i < n ; i++){
        int l , r;
        cin >> l >> r;
        sgs[l - 1] = r - 1;
        ord.insert(l - 1);
    }
    int o = 0;
    while(!ord.empty()){
        o++ , a.pb(*(ord.bg())) , a.pb(sgs[*(ord.bg())]) , ord.erase(ord.bg());
        int md = 0;
        while(!a.empty()){
            for(int i = 0 ; i < (int)a.size() - 1 ; i++){
                for(int j = a[i] + 1 ; j < a[i + 1] ; j++){
                    if(sgs[j] == -1 or sgs[j] < a[i + 1]) continue;
                    if(ms[j] == md){
                        cout << 0;
                        exit(0);
                    }
                    ms[j] = (md ^ 1);
                    b.pb(j) , b.pb(sgs[j]) , ord.erase(j);
                }
            }
            md ^= 1 , a = b , b.cl();
            // sort(a.bg() , a.end());
        }
    }
    cout << Pow(2 , o);
}

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