#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
#include <set>
typedef long long llong;
const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;
const int INF = 1e9;
int n;
struct Fenwick
{
int tree[2 * MAXN];
void update(int pos, int val)
{
for (int idx = pos ; idx <= 2 * n ; idx += idx & (-idx))
{
tree[idx] += val;
}
}
int query(int pos)
{
int res = 0;
for (int idx = pos ; idx > 0 ; idx -= idx & (-idx))
{
res += tree[idx];
}
return res;
}
};
int a[MAXN];
int b[MAXN];
int cnt[MAXN];
int minA[MAXN];
int maxB[MAXN];
int perm[MAXN];
std::set <int> s;
int prefix[2 * MAXN];
std::pair <int,int> toSort[MAXN];
std::vector <std::pair <int,int>> queries[MAXN];
Fenwick tree;
int vis[MAXN];
std::vector <int> g[MAXN];
bool dfs(int node)
{
for (const int &u : g[node])
{
if (vis[u] == vis[node])
{
return false;
}
if (vis[u] == 0)
{
vis[u] = 3 - vis[node];
if (!dfs(u)) return false;
}
}
return true;
}
void solve()
{
std::sort(toSort + 1, toSort + 1 + n);
for (int i = 1 ; i <= n ; ++i)
{
a[i] = toSort[i].first;
b[i] = toSort[i].second;
prefix[a[i]]++;
}
s.insert(0);
for (int i = 1 ; i <= n ; ++i)
{
auto it = std::prev(s.upper_bound(b[i]));
maxB[i] = *it;
s.insert(b[i]);
}
std::iota(perm + 1, perm + 1 + n, 1);
std::sort(perm + 1, perm + 1 + n, [&](int x, int y)
{
return b[x] > b[y];
});
s.clear();
s.insert(2 * n + 1);
for (int i = 1 ; i <= n ; ++i)
{
auto it = s.upper_bound(a[perm[i]]);
minA[perm[i]] = *it;
s.insert(a[perm[i]]);
}
// for (int i = 2 ; i < n ; ++i)
// {
// if (maxB[i] > minA[i])
// {
// std::cout << 0 << '\n';
// return;
// }
// }
for (int i = 1 ; i <= 2 * n ; ++i)
{
prefix[i] += prefix[i - 1];
}
for (int i = 1 ; i <= n ; ++i)
{
queries[i + 1].push_back({b[i], i});
queries[prefix[b[i]] + 1].push_back({b[i], -i});
}
for (int i = n ; i >= 1 ; --i)
{
tree.update(b[i], 1);
for (const auto &[biggerThan, idx] : queries[i])
{
int curr = tree.query(2 * n) - tree.query(biggerThan);
if (idx > 0) cnt[idx] += curr;
else cnt[-idx] -= curr;
}
}
int sum = 0;
// for (int i = 1 ; i <= n ; ++i)
// {
// sum += cnt[i];
// }
for (int i = 1 ; i <= n ; ++i)
{
for (int j = i + 1 ; j <= n ; ++j)
{
if (a[j] < b[i] && b[i] < b[j])
{
g[i].push_back(j);
g[j].push_back(i);
// sum++;
}
}
}
int compCnt = 0;
for (int i = 1 ; i <= n ; ++i)
{
if (!vis[i])
{
vis[i] = 1;
if (!dfs(i))
{
std::cout << 0 << '\n';
return;
}
compCnt++;
}
}
int ans = 1;
assert(sum < n);
for (int i = 0 ; i < compCnt ; ++i)
{
ans <<= 1;
if (ans >= MOD) ans -= MOD;
}
std::cout << ans << '\n';
}
void input()
{
std::cin >> n;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> toSort[i].first >> toSort[i].second;
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
66132 KB |
Output is correct |
2 |
Correct |
13 ms |
66136 KB |
Output is correct |
3 |
Correct |
13 ms |
66140 KB |
Output is correct |
4 |
Correct |
13 ms |
66140 KB |
Output is correct |
5 |
Correct |
14 ms |
66140 KB |
Output is correct |
6 |
Correct |
13 ms |
66220 KB |
Output is correct |
7 |
Correct |
13 ms |
66140 KB |
Output is correct |
8 |
Correct |
13 ms |
66140 KB |
Output is correct |
9 |
Correct |
12 ms |
66212 KB |
Output is correct |
10 |
Correct |
12 ms |
66284 KB |
Output is correct |
11 |
Correct |
13 ms |
66140 KB |
Output is correct |
12 |
Correct |
15 ms |
66140 KB |
Output is correct |
13 |
Correct |
13 ms |
66228 KB |
Output is correct |
14 |
Correct |
12 ms |
66140 KB |
Output is correct |
15 |
Correct |
13 ms |
66140 KB |
Output is correct |
16 |
Correct |
12 ms |
66140 KB |
Output is correct |
17 |
Correct |
13 ms |
66140 KB |
Output is correct |
18 |
Correct |
13 ms |
66288 KB |
Output is correct |
19 |
Correct |
12 ms |
64092 KB |
Output is correct |
20 |
Correct |
14 ms |
66276 KB |
Output is correct |
21 |
Correct |
14 ms |
66136 KB |
Output is correct |
22 |
Correct |
12 ms |
66140 KB |
Output is correct |
23 |
Correct |
12 ms |
66300 KB |
Output is correct |
24 |
Correct |
13 ms |
66140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
66132 KB |
Output is correct |
2 |
Correct |
13 ms |
66136 KB |
Output is correct |
3 |
Correct |
13 ms |
66140 KB |
Output is correct |
4 |
Correct |
13 ms |
66140 KB |
Output is correct |
5 |
Correct |
14 ms |
66140 KB |
Output is correct |
6 |
Correct |
13 ms |
66220 KB |
Output is correct |
7 |
Correct |
13 ms |
66140 KB |
Output is correct |
8 |
Correct |
13 ms |
66140 KB |
Output is correct |
9 |
Correct |
12 ms |
66212 KB |
Output is correct |
10 |
Correct |
12 ms |
66284 KB |
Output is correct |
11 |
Correct |
13 ms |
66140 KB |
Output is correct |
12 |
Correct |
15 ms |
66140 KB |
Output is correct |
13 |
Correct |
13 ms |
66228 KB |
Output is correct |
14 |
Correct |
12 ms |
66140 KB |
Output is correct |
15 |
Correct |
13 ms |
66140 KB |
Output is correct |
16 |
Correct |
12 ms |
66140 KB |
Output is correct |
17 |
Correct |
13 ms |
66140 KB |
Output is correct |
18 |
Correct |
13 ms |
66288 KB |
Output is correct |
19 |
Correct |
12 ms |
64092 KB |
Output is correct |
20 |
Correct |
14 ms |
66276 KB |
Output is correct |
21 |
Correct |
14 ms |
66136 KB |
Output is correct |
22 |
Correct |
12 ms |
66140 KB |
Output is correct |
23 |
Correct |
12 ms |
66300 KB |
Output is correct |
24 |
Correct |
13 ms |
66140 KB |
Output is correct |
25 |
Correct |
16 ms |
66652 KB |
Output is correct |
26 |
Correct |
18 ms |
66908 KB |
Output is correct |
27 |
Correct |
16 ms |
66648 KB |
Output is correct |
28 |
Correct |
16 ms |
66908 KB |
Output is correct |
29 |
Correct |
18 ms |
66652 KB |
Output is correct |
30 |
Correct |
19 ms |
66796 KB |
Output is correct |
31 |
Correct |
17 ms |
66648 KB |
Output is correct |
32 |
Correct |
17 ms |
66652 KB |
Output is correct |
33 |
Correct |
17 ms |
66696 KB |
Output is correct |
34 |
Correct |
17 ms |
66652 KB |
Output is correct |
35 |
Correct |
15 ms |
66396 KB |
Output is correct |
36 |
Correct |
16 ms |
66392 KB |
Output is correct |
37 |
Correct |
33 ms |
82524 KB |
Output is correct |
38 |
Correct |
25 ms |
74588 KB |
Output is correct |
39 |
Correct |
16 ms |
66396 KB |
Output is correct |
40 |
Correct |
15 ms |
66396 KB |
Output is correct |
41 |
Correct |
26 ms |
74588 KB |
Output is correct |
42 |
Correct |
26 ms |
74588 KB |
Output is correct |
43 |
Correct |
15 ms |
66396 KB |
Output is correct |
44 |
Correct |
15 ms |
66460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
66132 KB |
Output is correct |
2 |
Correct |
13 ms |
66136 KB |
Output is correct |
3 |
Correct |
13 ms |
66140 KB |
Output is correct |
4 |
Correct |
13 ms |
66140 KB |
Output is correct |
5 |
Correct |
14 ms |
66140 KB |
Output is correct |
6 |
Correct |
13 ms |
66220 KB |
Output is correct |
7 |
Correct |
13 ms |
66140 KB |
Output is correct |
8 |
Correct |
13 ms |
66140 KB |
Output is correct |
9 |
Correct |
12 ms |
66212 KB |
Output is correct |
10 |
Correct |
12 ms |
66284 KB |
Output is correct |
11 |
Correct |
13 ms |
66140 KB |
Output is correct |
12 |
Correct |
15 ms |
66140 KB |
Output is correct |
13 |
Correct |
13 ms |
66228 KB |
Output is correct |
14 |
Correct |
12 ms |
66140 KB |
Output is correct |
15 |
Correct |
13 ms |
66140 KB |
Output is correct |
16 |
Correct |
12 ms |
66140 KB |
Output is correct |
17 |
Correct |
13 ms |
66140 KB |
Output is correct |
18 |
Correct |
13 ms |
66288 KB |
Output is correct |
19 |
Correct |
12 ms |
64092 KB |
Output is correct |
20 |
Correct |
14 ms |
66276 KB |
Output is correct |
21 |
Correct |
14 ms |
66136 KB |
Output is correct |
22 |
Correct |
12 ms |
66140 KB |
Output is correct |
23 |
Correct |
12 ms |
66300 KB |
Output is correct |
24 |
Correct |
13 ms |
66140 KB |
Output is correct |
25 |
Correct |
16 ms |
66652 KB |
Output is correct |
26 |
Correct |
18 ms |
66908 KB |
Output is correct |
27 |
Correct |
16 ms |
66648 KB |
Output is correct |
28 |
Correct |
16 ms |
66908 KB |
Output is correct |
29 |
Correct |
18 ms |
66652 KB |
Output is correct |
30 |
Correct |
19 ms |
66796 KB |
Output is correct |
31 |
Correct |
17 ms |
66648 KB |
Output is correct |
32 |
Correct |
17 ms |
66652 KB |
Output is correct |
33 |
Correct |
17 ms |
66696 KB |
Output is correct |
34 |
Correct |
17 ms |
66652 KB |
Output is correct |
35 |
Correct |
15 ms |
66396 KB |
Output is correct |
36 |
Correct |
16 ms |
66392 KB |
Output is correct |
37 |
Correct |
33 ms |
82524 KB |
Output is correct |
38 |
Correct |
25 ms |
74588 KB |
Output is correct |
39 |
Correct |
16 ms |
66396 KB |
Output is correct |
40 |
Correct |
15 ms |
66396 KB |
Output is correct |
41 |
Correct |
26 ms |
74588 KB |
Output is correct |
42 |
Correct |
26 ms |
74588 KB |
Output is correct |
43 |
Correct |
15 ms |
66396 KB |
Output is correct |
44 |
Correct |
15 ms |
66460 KB |
Output is correct |
45 |
Execution timed out |
6092 ms |
98080 KB |
Time limit exceeded |
46 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
66132 KB |
Output is correct |
2 |
Correct |
13 ms |
66136 KB |
Output is correct |
3 |
Correct |
13 ms |
66140 KB |
Output is correct |
4 |
Correct |
13 ms |
66140 KB |
Output is correct |
5 |
Correct |
14 ms |
66140 KB |
Output is correct |
6 |
Correct |
13 ms |
66220 KB |
Output is correct |
7 |
Correct |
13 ms |
66140 KB |
Output is correct |
8 |
Correct |
13 ms |
66140 KB |
Output is correct |
9 |
Correct |
12 ms |
66212 KB |
Output is correct |
10 |
Correct |
12 ms |
66284 KB |
Output is correct |
11 |
Correct |
13 ms |
66140 KB |
Output is correct |
12 |
Correct |
15 ms |
66140 KB |
Output is correct |
13 |
Correct |
13 ms |
66228 KB |
Output is correct |
14 |
Correct |
12 ms |
66140 KB |
Output is correct |
15 |
Correct |
13 ms |
66140 KB |
Output is correct |
16 |
Correct |
12 ms |
66140 KB |
Output is correct |
17 |
Correct |
13 ms |
66140 KB |
Output is correct |
18 |
Correct |
13 ms |
66288 KB |
Output is correct |
19 |
Correct |
12 ms |
64092 KB |
Output is correct |
20 |
Correct |
14 ms |
66276 KB |
Output is correct |
21 |
Correct |
14 ms |
66136 KB |
Output is correct |
22 |
Correct |
12 ms |
66140 KB |
Output is correct |
23 |
Correct |
12 ms |
66300 KB |
Output is correct |
24 |
Correct |
13 ms |
66140 KB |
Output is correct |
25 |
Correct |
16 ms |
66652 KB |
Output is correct |
26 |
Correct |
18 ms |
66908 KB |
Output is correct |
27 |
Correct |
16 ms |
66648 KB |
Output is correct |
28 |
Correct |
16 ms |
66908 KB |
Output is correct |
29 |
Correct |
18 ms |
66652 KB |
Output is correct |
30 |
Correct |
19 ms |
66796 KB |
Output is correct |
31 |
Correct |
17 ms |
66648 KB |
Output is correct |
32 |
Correct |
17 ms |
66652 KB |
Output is correct |
33 |
Correct |
17 ms |
66696 KB |
Output is correct |
34 |
Correct |
17 ms |
66652 KB |
Output is correct |
35 |
Correct |
15 ms |
66396 KB |
Output is correct |
36 |
Correct |
16 ms |
66392 KB |
Output is correct |
37 |
Correct |
33 ms |
82524 KB |
Output is correct |
38 |
Correct |
25 ms |
74588 KB |
Output is correct |
39 |
Correct |
16 ms |
66396 KB |
Output is correct |
40 |
Correct |
15 ms |
66396 KB |
Output is correct |
41 |
Correct |
26 ms |
74588 KB |
Output is correct |
42 |
Correct |
26 ms |
74588 KB |
Output is correct |
43 |
Correct |
15 ms |
66396 KB |
Output is correct |
44 |
Correct |
15 ms |
66460 KB |
Output is correct |
45 |
Execution timed out |
6092 ms |
98080 KB |
Time limit exceeded |
46 |
Halted |
0 ms |
0 KB |
- |