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<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;
const int mod = 1e9 + 7;
mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );
struct Mint {
int a;
Mint(int _a = 0) : a(_a) {}
friend ostream& operator << (ostream &out, const Mint &_) {
out << _.a;
return out;
}
bool operator == (const Mint &_) const { return a == _.a; }
bool operator ! () const { return !a; }
Mint operator + (const Mint &_) const {
int ret = a + _.a;
return ret < mod ? Mint(ret) : Mint(ret - mod);
}
Mint operator - (const Mint &_) const { return *this + Mint(mod - _.a); }
Mint operator * (const Mint &_) const { return Mint( (int)( (LL)a * _.a % mod) ); }
friend Mint& operator += (Mint &a, const Mint &b) { return a = a + b; }
friend Mint& operator -= (Mint &a, const Mint &b) { return a = a - b; }
friend Mint& operator *= (Mint &a, const Mint &b) { return a = a * b; }
Mint& operator ++ () { return *this = *this + Mint(1); }
Mint& operator -- () { return *this = *this - Mint(1); }
template<class T> Mint binPow(T exp) const {
Mint ret(1), c = *this;
for (; exp; exp >>= 1, c *= c) if (exp & 1) ret *= c;
return ret;
}
};
int n;
vector<pair<int, int> > container;
vector<int> idx;
vector<vector<int> > gr;
struct It {
#define lC (i << 1)
#define rC (i << 1 | 1)
#define Mid ( (Left + Right) >> 1)
#define rt int i = 1, int Left = 0, int Right = n - 1
vector<vector<int> > group;
vector<int> iGroup;
It(int nNode) { group.assign(nNode, {} ); iGroup.assign(nNode, 0); }
void ins(int pos, int id, rt) {
group[i].emplace_back(id);
if (Left == Right) return;
if (pos <= Mid) ins(pos, id, lC, Left, Mid);
else ins(pos, id, rC, Mid + 1, Right);
}
void addEdge(int l, int r, int id, rt) {
if (l <= Left && Right <= r) {
while (iGroup[i] < sz(group[i]) && container[ group[i][ iGroup[i] ] ].first < container[id].first) {
gr[id].emplace_back(group[i][ iGroup[i] ]);
gr[group[i][ iGroup[i] ]].emplace_back(id);
++iGroup[i];
}
if (iGroup[i]) --iGroup[i];
return;
}
if (l <= Mid) addEdge(l, r, id, lC, Left, Mid);
if (Mid < r) addEdge(l, r, id, rC, Mid + 1, Right);
}
};
vector<int> label;
void dfs(int u, int cur) {
label[u] = cur;
for (int v : gr[u]) if (!(~label[v]) ) dfs(v, cur ^ 1);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef FourLeafClover
freopen("input", "r", stdin);
#endif // FourLeafCLover
cin >> n;
container.assign(n, {} );
for (int i = 0; i < n; ++i) {
cin >> container[i].first >> container[i].second;
--container[i].first; --container[i].second;
}
vector<pair<int, bool> > change(n << 1);
for (int i = 0; i < n; ++i) {
change[ container[i].first ] = { i, true };
change[ container[i].second ] = { i, false };
}
idx.assign(n << 1, -1);
for (int i = 0, cur = 0; i < n << 1; ++i) {
idx[i] = cur;
cur += !change[i].second;
}
vector<int> sor(n); iota(all(sor), 0);
sort(all(sor), [&](int i, int j) { return container[i].first < container[j].first; });
It it( (n + 5) << 2);
for (auto i : sor) it.ins(idx[ container[i].second ], i);
gr.assign(n, {} );
for (auto i : sor) it.addEdge(idx[ container[i].first ], idx[ container[i].second ], i);
Mint ans(1);
label.assign(n, -1);
for (int u = 0; u < n; ++u) if (!(~label[u]) ) {
dfs(u, 0);
ans += ans;
}
stack<int> st[2];
for (auto _ : change) {
int i = _.first; bool in = _.second;
if (in) st[ label[i] ].emplace(i);
else {
if (st[ label[i] ].top() ^ i) {
ans = Mint(0);
break ;
}
else st[ label[i] ].pop();
}
}
cout << ans << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |