이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 SegmentTree
{
struct Node
{
int sum;
bool lazy;
Node()
{
sum = lazy = 0;
}
friend Node operator + (const Node &left, const Node &right)
{
Node result;
result.sum = left.sum + right.sum;
return result;
}
};
Node tree[8*MAXN];
void push(int node, int l, int r)
{
if (tree[node].lazy == 0)
{
return;
}
tree[node].sum = r - l + 1;
if (l < r)
{
tree[2*node].lazy = 1;
tree[2*node + 1].lazy = 1;
}
tree[node].lazy = 0;
}
void update(int l, int r, int node, int queryL, int queryR)
{
push(node, l, r);
if (queryR < l || r < queryL)
{
return;
}
if (queryL <= l && r <= queryR)
{
tree[node].lazy = 1;
push(node, l, r);
return;
}
int mid = l + r >> 1;
update(l, mid, 2*node, queryL, queryR);
update(mid + 1, r, 2*node + 1, queryL, queryR);
tree[node] = tree[2*node] + tree[2*node + 1];
}
int query(int l, int r, int node, int queryL, int queryR)
{
push(node, l, r);
if (queryL <= l && r <= queryR)
{
return tree[node].sum;
}
int res = 0;
int mid = l + r >> 1;
if (queryL <= mid) res += query(l, mid, 2*node, queryL, queryR);
if (mid + 1 <= queryR) res += query(mid + 1, r, 2*node + 1, queryL, queryR);
return res;
}
void update(int l, int r)
{
update(1, 2 * n, 1, l, r);
}
int query(int l, int r)
{
return query(1, 2 * n, 1, l, r);
}
};
int a[MAXN];
int b[MAXN];
int prefix[2 * MAXN];
std::vector <int> g[MAXN];
std::pair <int,int> toSort[MAXN];
SegmentTree partTree[2];
int vis[MAXN];
bool dfs(int node)
{
for (const int &u : g[node])
{
if (vis[u] == vis[node])
{
// assert(false);
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;
}
// for (int i = n ; i >= 1 ; --i)
// {
// if (partTree[0].query(b[i], b[i]) && partTree[1].query(b[i], b[i]))
// {
// std::cout << 0 << '\n';
// return;
// }
// int currentPart = 0;
// if (partTree[0].query(b[i], b[i]))
// {
// currentPart = 1;
// }
// partTree[currentPart].update(a[i], b[i]);
// std::cout << "part: " << a[i] << ' ' << b[i] << " = " << currentPart << '\n';
// }
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);
}
}
}
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;
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;
}
컴파일 시 표준 에러 (stderr) 메시지
port_facility.cpp: In member function 'void SegmentTree::update(int, int, int, int, int)':
port_facility.cpp:68:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | int mid = l + r >> 1;
| ~~^~~
port_facility.cpp: In member function 'int SegmentTree::query(int, int, int, int, int)':
port_facility.cpp:83:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
83 | int mid = l + r >> 1;
| ~~^~~
# | 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... |