This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define _CRT_SECURE_NO_WARNINGS
#ifdef _DEBUG
#define FILE_IN "input.txt"
#define FILE_OUT "output.txt"
#endif
#include <iostream>
#include <cstdlib>
#include <climits>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
void openFiles() {
#ifdef _DEBUG
assert(freopen(FILE_IN, "r", stdin));
assert(freopen(FILE_OUT, "w", stdout));
#endif
}
void IOoptimize() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const int MAXN = 100000 + 10;
pair<int, int> max_end[5 * 2 * MAXN];
pair<int, int> min_start[5 * 2 * MAXN];
int color[MAXN];
struct Action {
int id;
int time;
bool type;
Action(int id, int time, bool type) : id(id), time(time), type(type) {}
};
vector<Action> actions;
bool operator<(const Action& a1, const Action& a2) {
return a1.time < a2.time;
}
bool get_bit(int mask, int i) {
return mask & (1 << i);
}
void update_ends(int x, int l, int r, int i, pair<int, int> val) {
if (l > i || r <= i)
return;
if (r - l == 1) {
max_end[x] = val;
return;
}
int c = (l + r) / 2;
update_ends(2 * x + 1, l, c, i, val);
update_ends(2 * x + 2, c, r, i, val);
max_end[x] = max(max_end[2 * x + 1], max_end[2 * x + 2]);
}
void update_starts(int x, int l, int r, int i, pair<int, int> val) {
if (l > i || r <= i)
return;
if (r - l == 1) {
min_start[x] = val;
return;
}
int c = (l + r) / 2;
update_starts(2 * x + 1, l, c, i, val);
update_starts(2 * x + 2, c, r, i, val);
min_start[x] = min(min_start[2 * x + 1], min_start[2 * x + 2]);
}
pair<int, int> query_ends(int x, int l, int r, int ql, int qr) {
if (l >= qr || r <= ql)
return {-1, -1};
if (ql <= l && r <= qr)
return max_end[x];
int c = (l + r) / 2;
return max(
query_ends(2 * x + 1, l, c, ql, qr),
query_ends(2 * x + 2, c, r, ql, qr)
);
}
pair<int, int> query_starts(int x, int l, int r, int ql, int qr) {
if (l >= qr || r <= ql)
return {5 * MAXN, -1};
if (ql <= l && r <= qr)
return min_start[x];
int c = (l + r) / 2;
return min(
query_starts(2 * x + 1, l, c, ql, qr),
query_starts(2 * x + 2, c, r, ql, qr)
);
}
int main() {
openFiles();
IOoptimize();
memset(color, 0, sizeof(color));
int n;
cin >> n;
for (int i = 0; i < 5 * n; i++) {
max_end[i] = {-1, -1};
min_start[i] = {5 * MAXN, -1};
}
vector<pair<int, int>> segments;
for (int i = 0; i < n; i++) {
int time1, time2;
cin >> time1 >> time2;
time1--;
time2--;
segments.push_back({time1, time2});
update_starts(0, 0, 2 * n, time2, {time1, i});
update_ends(0, 0, 2 * n, time1, {time2, i});
actions.push_back(Action(i, time1, true));
actions.push_back(Action(i, time2, false));
}
sort(actions.begin(), actions.end());
//cout << max_end[0].second << "\n";
//cout << query_ends(0, 0, 2 * n, 0, 2 * n).second << "\n";
//return 0;
ll ans = 1;
set<int> s;
for (int i = 0; i < n; i++)
s.insert(i);
//return 0;
while (s.size() != 0) {
ans *= 2;
ans %= mod;
queue<int> q;
q.push(*s.begin());
color[*s.begin()] = 1;
while (!q.empty()) {
int cur = q.front();
q.pop();
s.erase(cur);
update_ends(0, 0, 2 * n, segments[cur].first, { -1, -1 });
update_starts(0, 0, 2 * n, segments[cur].second, { 5 * MAXN, -1 });
int f;
while (true) {
pair<int, int> g = query_ends(0, 0, 2 * n, segments[cur].first, segments[cur].second + 1);
f = g.second;
if (f == -1 || g.first < segments[cur].second)
break;
update_ends(0, 0, 2 * n, segments[f].first, {-1, -1});
color[f] = -color[cur];
q.push(f);
}
while (true) {
pair<int, int> g = query_starts(0, 0, 2 * n, segments[cur].first, segments[cur].second + 1);
f = g.second;
if (f == -1 || g.first > segments[cur].first)
break;
update_starts(0, 0, 2 * n, segments[f].second, {5 * MAXN, -1});
color[f] = -color[cur];
q.push(f);
}
}
}
vector<int> v[2];
for (auto act : actions) {
if (act.type) {
v[(color[act.id] + 1) / 2].push_back(act.id);
}
else {
if (v[(color[act.id] + 1) / 2].back() != act.id) {
cout << "0";
return 0;
}
v[(color[act.id] + 1) / 2].pop_back();
}
}
cout << ans;
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... |