#include <cmath>
#include <cassert>
#include <iostream>
#include <set>
#include <climits>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <type_traits>
#include <string>
#include <queue>
#include <map>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
using namespace std;
class Intervals {
public:
set<pair<int,int>> intervals;
void print () {
for (auto& p: intervals) {
cout << p.first << " " << p.second << '\n';
}
cout << '\n';
}
pair<int,int> leftIntersect (pair<int,int> p) {
auto it = intervals.upper_bound({p.first + 1, -1});
if (it == intervals.begin()) {
return {-1, -1};
}
it--;
pair<int,int> q = *it;
if (q.second < p.first) {
return {-1, -1};
}
return q;
}
pair<int,int> rightIntersect (pair<int,int> p) {
auto it = intervals.upper_bound({p.second + 1, -1});
if (it == intervals.begin()) {
return {-1, -1};
}
it--;
pair<int,int> q = *it;
if (q.first > p.second) {
return {-1, -1};
}
if (q.first < p.first) {
return {-1, -1};
}
return q;
}
bool willChange (pair<int,int> p) {
pair<int,int> q = leftIntersect(p);
if (q.first < 0 && q.second < 0) {
return true;
}
if (q.first <= p.first && q.second >= p.second) {
return false;
}
return true;
}
pair<int,int> update_left (pair<int,int> p) {
// cout << "UPDATE LEFT " << p.first << " " << p.second << '\n';
pair<int,int> q = leftIntersect(p);
if (q.first == -1 && q.second == -1) {
return p;
}
if (q.second < p.first) {
return p;
}
// cout << "ERASE\n";
if (intervals.count(q)) intervals.erase(q);
return {q.first, p.second};
}
pair<int,int> update_right (pair<int,int> p) {
// cout << "UPDATE RIGHT " << p.first << " " << p.second << '\n';
pair<int,int> q = rightIntersect(p);
if (q.first == -1 && q.second == -1) {
return p;
}
if (q.first > p.second) {
return p;
}
// cout << "ERASE " << q.first << " " << q.second << '\n';
// cout << "ADD " << p.first << " " << q.second << '\n';
if (intervals.count(q)) intervals.erase(q);
return {p.first, q.second};
}
void erase_in_between (pair<int,int> p) {
auto it = intervals.lower_bound({p.first, -1});
set<pair<int,int>> to_erase;
while (it != intervals.end()) {
if ((*it).second < p.second) {
to_erase.insert(*it);
} else {
break;
}
it++;
}
for (auto& q: to_erase) {
intervals.erase(q);
}
}
void add_interval (pair<int,int> p) {
// cout << "ADD " << p.first << " " << p.second << '\n';
if (!willChange(p)) { //if adding this interval will not change anything, then there is no point in adding this interval (i.e. if there is another interval which covers the given interval)
return;
}
erase_in_between(p);
pair<int,int> new_p = update_left(p);
pair<int,int> new_p1 = update_right(new_p);
intervals.insert(new_p1);
}
};
int main () {
int N;
int64_t A, B;
cin >> N >> A >> B;
int64_t prod;
if (A < LLONG_MAX/B) {
prod = A * B;
} else {
prod = LLONG_MAX;
}
Intervals myInterval;
for (int i = 0; i < N; i++) {
int64_t x, y;
cin >> x >> y;
if (abs(y - x) >= prod) {
myInterval.add_interval({0, A * B - 1});
continue;
}
x %= (A * B), y %= (prod);
if (x <= y) {
//cout << "T1\n";
myInterval.add_interval({x, y});
} else {
//cout << "T2\n";
swap(x, y);
myInterval.add_interval({0, x});
myInterval.add_interval({y, A * B - 1});
}
}
// myInterval.print();
int ans = 0;
for (auto& p: myInterval.intervals) {
ans += p.second - p.first + 1;
}
cout << ans << '\n';
}
Compilation message
strange_device.cpp:15: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
15 | #pragma GCC optimization ("O3")
|
strange_device.cpp:16: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
16 | #pragma GCC optimization ("Ofast")
|
strange_device.cpp:17: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
17 | #pragma GCC optimization ("unroll-loops")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
15 ms |
716 KB |
Output is correct |
| 3 |
Correct |
15 ms |
648 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
3 ms |
204 KB |
Output is correct |
| 3 |
Correct |
2 ms |
204 KB |
Output is correct |
| 4 |
Correct |
2 ms |
204 KB |
Output is correct |
| 5 |
Correct |
889 ms |
268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1719 ms |
47216 KB |
Output is correct |
| 3 |
Incorrect |
1427 ms |
5956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1719 ms |
47216 KB |
Output is correct |
| 3 |
Incorrect |
1427 ms |
5956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1719 ms |
47216 KB |
Output is correct |
| 3 |
Incorrect |
1427 ms |
5956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
187 ms |
4816 KB |
Output is correct |
| 3 |
Incorrect |
204 ms |
4172 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
15 ms |
716 KB |
Output is correct |
| 3 |
Correct |
15 ms |
648 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
