//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("arch=icelake-server,avx512f,avx512bw,avx512bitalg,bmi,bmi2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
constexpr ll mod = 1e9 + 7;
ll bin_pow(ll base, ll exp)
{
ll res = 1;
while (exp){
if (exp & 1)
res = (res * base) % mod;
base = (base * base) % mod;
exp >>= 1;
}
return res;
}
int sgt[8000000];
int min_r[8000000];
/*
void update(int v, int tl, int tr, int pos, int val)
{
if (tl == tr)
sgt[v] = val;
else {
int tm = (tl + tr) / 2;
if (pos <= tm)
update(v * 2, tl, tm, pos, val);
else
update(v * 2 + 1, tm + 1, tr, pos, val);
sgt[v] = sgt[v * 2] + sgt[v * 2 + 1];
}
}
int get(int v, int l, int r, int tl, int tr)
{
if (l > tr or tl > r)
return 0;
if (tl <= l && r <= tr)
return sgt[v];
int m = (l + r) / 2;
return get(v * 2, l, m, tl, tr) + get(v * 2 + 1, m + 1, r, tl, tr);
}*/
struct dsu {
vector<int> p;
vector<int> sz;
int szz;
dsu() {}
dsu(int n) {
p.resize(n);
sz.resize(n);
for(int i = 0;i < n;i++) {
p[i] = i;
sz[i] = 1;
}
szz = n;
}
int get(int v) {
if(p[v] == v) {
return v;
}
return p[v] = get(p[v]);
}
void unite(int a,int b) {
a = get(a);
b = get(b);
if(a == b) return;
szz--;
if(sz[a] < sz[b]) {
swap(a,b);
}
p[b] = a;
sz[a]+=sz[b];
}
} D;
void update(int v,int l,int r,int pos, int val) {
sgt[pos] = val;
}
int get(int v, int l, int r, int tl, int tr) {
int sum = 0;
vector<int> to_rem;
for(int i = tl;i <= tr;i++) {
sum+=sgt[i];
if(sgt[i]) {
to_rem.push_back(i);
D.unite(tl, i);
}
sgt[i] = 0;
}
if(to_rem.size()) {
sgt[to_rem[0]] = 1;
sgt[to_rem.back()] = 1;
}
return sum;
}
int main()
{
//ios_base::sync_with_stdio(false);
//cin.tie(nullptr);
//cout.tie(nullptr);
ll n;
cin >> n;
D = dsu(2*n+1);
vector<pair<int,int>> events;
for (int i = 0; i < n; ++i) {
int l,r;
cin >> l >> r;
events.emplace_back(l,r);
events.emplace_back(r,l);
D.unite(l,r);
}
sort(events.begin(),events.end());
bool is_pos = true;
int cnt = n;
set<int> Rs;
set<int> Ls;
for(int i = 0;i < 2*n;i++) {
if(events[i].first < events[i].second) {
Ls.insert(events[i].first);
auto it = Rs.insert(events[i].second);
if(it.first != Rs.begin()) {
min_r[events[i].first] = *prev(it.first);
}
update(1,1,2*n,events[i].first,1);
}
else {
update(1,1,2*n,events[i].second,0);
Rs.erase(events[i].first);
auto it = Ls.find(events[i].second);
if(it != Ls.end()) {
it++;
if(it != Ls.end() and *it < min_r[events[i].second]) {
is_pos = false;
break;
}
it--;
}
Ls.erase(it);
get(1,1,2*n,events[i].second,events[i].first);
}
}
cnt = D.szz-1;
if(is_pos) {
cout << bin_pow(2,cnt) << '\n';
}
else {
cout << 0 << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2496 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 21 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
0 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2496 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 21 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 25 |
Correct |
10 ms |
2500 KB |
Output is correct |
| 26 |
Correct |
10 ms |
2652 KB |
Output is correct |
| 27 |
Correct |
10 ms |
2652 KB |
Output is correct |
| 28 |
Correct |
10 ms |
2652 KB |
Output is correct |
| 29 |
Correct |
10 ms |
2592 KB |
Output is correct |
| 30 |
Correct |
10 ms |
2648 KB |
Output is correct |
| 31 |
Correct |
9 ms |
2652 KB |
Output is correct |
| 32 |
Correct |
10 ms |
2652 KB |
Output is correct |
| 33 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 34 |
Correct |
2 ms |
2552 KB |
Output is correct |
| 35 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 36 |
Correct |
13 ms |
2760 KB |
Output is correct |
| 37 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 38 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 39 |
Correct |
2 ms |
2608 KB |
Output is correct |
| 40 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 41 |
Correct |
13 ms |
2652 KB |
Output is correct |
| 42 |
Correct |
13 ms |
2652 KB |
Output is correct |
| 43 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 44 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2496 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 21 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 25 |
Correct |
10 ms |
2500 KB |
Output is correct |
| 26 |
Correct |
10 ms |
2652 KB |
Output is correct |
| 27 |
Correct |
10 ms |
2652 KB |
Output is correct |
| 28 |
Correct |
10 ms |
2652 KB |
Output is correct |
| 29 |
Correct |
10 ms |
2592 KB |
Output is correct |
| 30 |
Correct |
10 ms |
2648 KB |
Output is correct |
| 31 |
Correct |
9 ms |
2652 KB |
Output is correct |
| 32 |
Correct |
10 ms |
2652 KB |
Output is correct |
| 33 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 34 |
Correct |
2 ms |
2552 KB |
Output is correct |
| 35 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 36 |
Correct |
13 ms |
2760 KB |
Output is correct |
| 37 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 38 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 39 |
Correct |
2 ms |
2608 KB |
Output is correct |
| 40 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 41 |
Correct |
13 ms |
2652 KB |
Output is correct |
| 42 |
Correct |
13 ms |
2652 KB |
Output is correct |
| 43 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 44 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2496 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 21 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 25 |
Correct |
10 ms |
2500 KB |
Output is correct |
| 26 |
Correct |
10 ms |
2652 KB |
Output is correct |
| 27 |
Correct |
10 ms |
2652 KB |
Output is correct |
| 28 |
Correct |
10 ms |
2652 KB |
Output is correct |
| 29 |
Correct |
10 ms |
2592 KB |
Output is correct |
| 30 |
Correct |
10 ms |
2648 KB |
Output is correct |
| 31 |
Correct |
9 ms |
2652 KB |
Output is correct |
| 32 |
Correct |
10 ms |
2652 KB |
Output is correct |
| 33 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 34 |
Correct |
2 ms |
2552 KB |
Output is correct |
| 35 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 36 |
Correct |
13 ms |
2760 KB |
Output is correct |
| 37 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 38 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 39 |
Correct |
2 ms |
2608 KB |
Output is correct |
| 40 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 41 |
Correct |
13 ms |
2652 KB |
Output is correct |
| 42 |
Correct |
13 ms |
2652 KB |
Output is correct |
| 43 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 44 |
Halted |
0 ms |
0 KB |
- |
