Submission #478493

#	Time	Username	Problem	Language	Result	Execution time	Memory
478493		Vladth11	Port Facility (JOI17_port_facility)	C++14	0 / 100	1 ms	332 KiB

port_facility

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 2000001;
const ll VMAX = 21;
const ll INF = (1LL << 59);
const ll MOD = 1000000007;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 21;

int aib[NMAX];

void update(int node, int x){
    for(; node < NMAX; node += node&(-node))
        aib[node] += x;
}

int query(int node){
    if(!node)
        return 0;
    int sol = 0;
    for(; node > 0; node -= node&(-node))
        sol += aib[node];
    return sol;
}

pii v[NMAX];
pii iesire[NMAX];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, i, comp = 0;
    cin >> n;
    for(i = 1; i <= n; i++){
        cin >> v[i].first >> v[i].second;
    }
    sort(v + 1, v + n + 1);
    for(i = 1; i <= n; i++){
        iesire[i] = {v[i].second, i};
    }
    sort(iesire + 1, iesire + n + 1);
    for(i = 1; i <= n; i++){
        update(v[i].second, 1);
        int s = query(v[i].second - 1) - query(v[i].first);
        if(s == 0){
            comp++;
        }
    }
    int rez = 1;
    for(i = 1; i <= comp; i++){
        rez *= 2;
        rez %= MOD;
    }
    vector <int> a, b;
    i = 1;
    int j = 1;
    while(i <= n && j <= n){
        if(v[i].first < iesire[j].first){
            if(!a.size() || v[a.back()].second >= v[i].second){
                a.push_back(i);
            }else if(!b.size() || v[b.back()].second >= v[i].second){
                b.push_back(i);
            }else{
                rez = 0;
            }
            i++;
        }else{
            if((!a.size() || a.back() != iesire[j].second) && (!b.size() || b.back() != iesire[j].second)){
                rez = 0;
            }else{
                if(a.size() && a.back() == iesire[j].second)
                    a.pop_back();
                else
                    b.pop_back();
            }
            j++;
        }
    }
    cout << rez;
    return 0;
}

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