이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <algorithm>
#include <vector>
#define f first
#define s second
#define int long long
using namespace std;
const int mod = 1e9+7;
int n, d[2000010], p[2000010], cnt, ans = 1;
bool hv;
pair<int,int> a[1000010];
vector<int> aa, bb, amin, bmin, v[2000010], tmp;
bool check(int i, int j) {
if ((a[i].f < a[j].f) && (a[j].f < a[i].s) && (a[i].s < a[j].s)) return 1;
swap(i,j);
if ((a[i].f < a[j].f) && (a[j].f < a[i].s) && (a[i].s < a[j].s)) return 1;
return 0;
}
int dsu(int u) {
if (p[u] == u) return u;
return p[u] = dsu(p[u]);
}
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i].f >> a[i].s;
sort(a+1,a+n+1);
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (check(i,j)) p[dsu(i)] = p[dsu(j)];
}
}
for (int i = 1; i <= n; i++) v[p[dsu(i)]].push_back(i);
for (int i = 1; i <= n; i++) {
for (int k = 0; k < v[i].size(); k++) {
int j = v[i][k];
while (aa.size() && (aa.back() < a[j].f)) {
aa.pop_back();
while (amin.size() && ((aa.empty()) || (amin.back() < aa.back()))) {
tmp.push_back(amin.back());
amin.pop_back();
}
while (tmp.size()) {
aa.push_back(tmp.back());
tmp.pop_back();
}
}
if ((aa.empty()) || (aa.back() > a[j].s)) {
aa.push_back(a[j].s);
} else {
if (amin.size() && (amin.back() < a[j].s)) {
cout << 0 << endl;
return 0;
}
amin.push_back(a[j].s);
}
}
if (v[i].size()) cnt++;
}
for (int i = 1; i <= cnt; i++) (ans *= 2) %= mod;
cout << ans << endl;
}
컴파일 시 표준 에러 (stderr) 메시지
port_facility.cpp: In function 'int main()':
port_facility.cpp:39:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for (int k = 0; k < v[i].size(); k++) {
| ~~^~~~~~~~~~~~~
# | 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... |