| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 205015 | hanagasumi | Port Facility (JOI17_port_facility) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <chrono>
#include <bits/stdc++.h>
#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
// #define int ll
#define FAST_ALLOCATOR_MEMORY (2e9)
#ifdef FAST_ALLOCATOR_MEMORY
int allocator_pos = 0;
char allocator_memory[(int)FAST_ALLOCATOR_MEMORY];
inline void * operator new ( size_t n ) {
char *res = allocator_memory + allocator_pos;
allocator_pos += n;
assert(allocator_pos <= (int)FAST_ALLOCATOR_MEMORY);
return (void *)res;
}
inline void operator delete ( void * ) noexcept { }
#endif
using namespace std;
typedef long long ll;
typedef long double ld;
// vector<int> p;
// vector<int> sz;
// vector<vector<int>> g;
// vector<int> color;
// vector<int> used;
const int N = 1 << 21;
vector<int> tree[2 * N];
vector<int> g[N];
int p[N];
int sz[N];
int color[N];
int used[N];
int findp(int v) {
if(p[v] == v)
return v;
p[v] = findp(p[v]);
return p[v];
}
void merge(int a, int b) {
a = findp(a), b = findp(b);
if(a == b)
return;
if(sz[a] < sz[b])
swap(a, b);
sz[a] += sz[b];
p[b] = a;
}
void add(int v, int val) {
if(v == 0)
return;
tree[v].pb(val);
add(v / 2, val);
}
void merge2(int v, int l, int r, int vl, int vr, int val) {
if(vr <= l || r <= vl)
return;
if(vl <= l && r <= vr) {
if(len(tree[v]) == 0)
return;
int x = tree[v][0];
for (auto y : tree[v]) {
g[y].pb(val);
g[val].pb(y);
merge(x, y);
}
merge(x, val);
x = tree[v][0];
tree[v].clear();
tree[v].pb(x);
return;
}
int m = (l + r) / 2;
merge2(v * 2, l, m, vl, vr, val);
merge2(v * 2 + 1, m, r, vl, vr, val);
}
void dfs(int v, int col) {
used[v] = 1;
color[v] = col;
for (auto x : g[v]) {
if(used[x])
continue;
dfs(x, 3 - col);
}
}
bool ch(vector<pair<int, int>>& a) {
vector<int> st;
vector<pair<int, int>> scan;
for (int i = 0; i < len(a); i++) {
scan.pb({a[i].ft, a[i].sc});
scan.pb({a[i].sc, -1});
}
sort(scan.begin(), scan.end());
for (auto x : scan) {
if(x.sc >= 0) {
if(len(st) == 0) {
st.pb(x.sc);
continue;
}
if(st.back() < x.sc)
return 0;
st.pb(x.sc);
}
else {
if(st.back() != x.ft)
return 0;
st.pop_back();
}
}
return 1;
}
ll mod = 1e9 + 7;
signed main() {
#ifdef PC
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
// while(N < (2 * n + 1))
// N *= 2;
// tree = vector<vector<int>> (2 * N);
for (int i = 0; i < N; i++) {
p[i] = i;
sz[i] = 1;
color[i] = 0;
used[i] = 0;
}
vector<int> was;
map<int, int> num;
vector<pair<int, int>> have(n);
vector<int> wasc(n + 1, 0);
vector<pair<int, int>> st1, st2;
for (int i = 0; i < N; i++) {
p[i] = i;
}
for (int i = 0; i < n; i++) {
cin >> have[i].ft >> have[i].sc;
was.pb(have[i].ft);
was.pb(have[i].sc);
}
sort(was.begin(), was.end());
sort(have.begin(), have.end());
for (int i = 0; i < len(was); i++)
num[was[i]] = i;
for (int i = 0; i < n; i++) {
merge2(1, 0, N, num[have[i].ft], num[have[i].sc] + 1, i);
add(N + num[have[i].sc], i);
}
ll ans = 1;
for (int i = 0; i < n; i++) {
int pr = findp(i);
if(!wasc[pr])
ans = (ans * 2LL) % mod;
wasc[pr] = 1;
}
for (int i = 0; i < n; i++) {
if(used[i])
continue;
dfs(i, 1);
}
for (int i = 0; i < n; i++) {
if(color[i] == 1)
st1.pb(have[i]);
else
st2.pb(have[i]);
}
if(!ch(st1) || !ch(st2)) {
cout << 0;
return 0;
}
cout << ans << endl;
return 0;
}
/*
sort(check.begin(), check.end());
vector<int> st1, st2;
vector<int> from(n + 1, 0);
for (auto x: check) {
cout << x.ft << " " << x.sc << endl;
if(x.sc >= 0) {
bool can1 = 0, can2 = 0;
if(len(st1) == 0 || st1.back() > have[x.sc].sc)
can1 = 1;
if(len(st2) == 0 || st2.back() > have[x.sc].sc)
can2 = 1;
// cout << "C " << can1 << " " << can2 << endl;
// if(len(st1) > 0)
// cout << "ST1 " << st1.back() << endl;
// if(len(st2) > 0)
// cout << "ST2 " << st2.back() << endl;
if(!can1 && !can2) {
cout << 0;
return 0;
}
if(len(st1) == 0 && len(st2) == 0) {
st1.pb(have[x.sc].sc);
from[x.sc] = 1;
continue;
}
if(len(st2) == 0 || st1.back() < st2.back()) {
if(can1) {
st1.pb(have[x.sc].sc);
from[x.sc] = 1;
}
else {
st2.pb(have[x.sc].sc);
from[x.sc] = 2;
}
}
else {
if(can2) {
st2.pb(have[x.sc].sc);
from[x.sc] = 2;
}
else {
st1.pb(have[x.sc].sc);
from[x.sc] = 1;
}
}
}
else {
x.sc = -x.sc - 1;
if(from[x.sc] == 1)
st1.pop_back();
else
st2.pop_back();
}
}
*/