Submission #499335

#TimeUsernameProblemLanguageResultExecution timeMemory
499335OzyPort Facility (JOI17_port_facility)C++17
0 / 100
1 ms324 KiB
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) //cout << #a << " = " << a << endl
#define debugsl(a) //cout << #a << " = " << a << ", "

#define MAX 1000000
#define mod 1000000007
#define v first
#define id second.first
#define tipo second.second

lli offset,n,res,a;
lli pari[MAX+2];

vector< pair<lli, pair<lli,lli> > > eventos;

lli inicios[MAX + 2], fines[MAX + 2];
set<pair<lli, lli> > cceros, cunos, cdos;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    rep(i,1,n){
        cin >> inicios[i] >> fines[i];
        eventos.push_back({inicios[i],{i,1} });
        eventos.push_back({fines[i],{i,0} });
    }
    sort(eventos.begin(), eventos.end());

    res = 1;
    for (auto act : eventos) {

        debugsl(act.tipo);
        debugsl(act.v);
        debug(act.id);

        if (act.tipo == 1){
            cceros.insert({act.v, act.id});
        }
        else {
            debug(pari[act.id]);
            if (pari[act.id] == 0) {
                res *= 2;
                res %= mod;
                pari[act.id] = 1;
            }

            auto it = cceros.upper_bound({inicios[act.id], n + 1});
            lli nuevapar = pari[act.id] ^ 3;
            while (it != cceros.end()){
                debugsl(nuevapar);
                debug((*it).second);
                if (pari[(*it).second] == 0) pari[(*it).second] = nuevapar;
                else if (pari[(*it).second] != nuevapar){
                    res = 0;
                    break;
                }
                it++;
            }
                cceros.erase({inicios[act.id], act.id});
        }

    }

    cout << res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...