oj.uz

Submission #750594

# Submission time Handle Problem Language Result Execution time Memory
750594 2023-05-29T19:58:26 Z Sam_a17 Strange Device (APIO19_strange_device) C++17
100 / 100
 482 ms 53260 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int)x.size()
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt __builtin_popcount
 
#define pb push_back
#define popf pop_front
#define popb pop_back
#define ld long double
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// for random generations
// mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
mt19937 myrand(373);
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};
 
// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  if(str == "input") {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  } else {
    // freopen("skis.in", "r", stdin);
    // freopen("skis.out", "w", stdout);
  }
}
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const long long maxim = 1e18;

void solve_() {
  long long n, a, b; cin >> n >> a >> b;

  __int128 x = b;
  __int128 per = a / __gcd(a, b + 1);
  per *= b;
  if(per > maxim) {
    per = maxim;
  }

  long long period = per;

  vector<pair<long long, long long>> segments;
  for(int i = 1; i <= n; i++) {
    long long l, r; cin >> l >> r;
    long long len = (r - l + 1);
    if(len >= period) {
      cout << period << '\n';
      return;
    }

    l %= period, r %= period;
    if(l <= r) {
      segments.emplace_back(l, r);
    } else {
      segments.emplace_back(l, period - 1);
      segments.emplace_back(0, r);
    }
  }

  sort(all(segments));
  long long max_r = 0, answ = 0, last = 0;
  for(int i = 0; i < sz(segments); i++) {
    if(i == 0) {
      last = segments[i].first;
      max_r = segments[i].second;
    }

    if(max_r >= segments[i].second) {
      continue;
    }

    if(max_r < segments[i].first) {
      answ += max_r - last + 1;
      last = segments[i].first;
      max_r = max(max_r, segments[i].second);
    } else {
      max_r = segments[i].second;
    }
  }

  answ += (max_r - last + 1);
  cout << answ << '\n';
}
 
int main() {
  setIO();
 
  auto solve = [&](int test_case)-> void {
    for(int i = 1; i <= test_case; i++) {
      // cout << "Case #" << i << ": ";
      solve_();
    }
  };
 
  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

strange_device.cpp: In function 'void solve_()':
strange_device.cpp:83:12: warning: unused variable 'x' [-Wunused-variable]
   83 |   __int128 x = b;
      |            ^
strange_device.cpp: In function 'void setIO(std::string)':
strange_device.cpp:69:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:70:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 5 ms 1064 KB Output is correct
3 Correct 5 ms 1076 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 0 ms 324 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 5 ms 984 KB Output is correct
17 Correct 45 ms 5708 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 368 KB Output is correct
5 Correct 305 ms 41244 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 384 ms 34096 KB Output is correct
3 Correct 384 ms 53136 KB Output is correct
4 Correct 400 ms 53260 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 384 ms 34096 KB Output is correct
3 Correct 384 ms 53136 KB Output is correct
4 Correct 400 ms 53260 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 410 ms 53208 KB Output is correct
7 Correct 397 ms 53192 KB Output is correct
8 Correct 389 ms 52952 KB Output is correct
9 Correct 449 ms 52852 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 384 ms 34096 KB Output is correct
3 Correct 384 ms 53136 KB Output is correct
4 Correct 400 ms 53260 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 42 ms 5628 KB Output is correct
7 Correct 41 ms 5680 KB Output is correct
8 Correct 41 ms 5828 KB Output is correct
9 Correct 42 ms 5724 KB Output is correct
10 Correct 42 ms 5680 KB Output is correct
11 Correct 39 ms 5700 KB Output is correct
12 Correct 41 ms 5696 KB Output is correct
13 Correct 42 ms 5700 KB Output is correct
14 Correct 40 ms 5652 KB Output is correct
15 Correct 42 ms 5692 KB Output is correct
16 Correct 50 ms 5696 KB Output is correct
17 Correct 42 ms 5664 KB Output is correct
18 Correct 460 ms 53036 KB Output is correct
19 Correct 397 ms 53016 KB Output is correct
20 Correct 431 ms 52980 KB Output is correct
21 Correct 41 ms 5672 KB Output is correct
22 Correct 37 ms 5660 KB Output is correct
23 Correct 126 ms 18456 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 43 ms 5624 KB Output is correct
3 Correct 39 ms 5668 KB Output is correct
4 Correct 482 ms 53188 KB Output is correct
5 Correct 44 ms 5684 KB Output is correct
6 Correct 40 ms 5740 KB Output is correct
7 Correct 39 ms 5656 KB Output is correct
8 Correct 44 ms 5640 KB Output is correct
9 Correct 44 ms 5672 KB Output is correct
10 Correct 43 ms 5668 KB Output is correct
11 Correct 43 ms 5744 KB Output is correct
12 Correct 36 ms 5688 KB Output is correct
13 Correct 41 ms 5664 KB Output is correct
14 Correct 444 ms 53096 KB Output is correct
15 Correct 40 ms 5696 KB Output is correct
16 Correct 389 ms 52964 KB Output is correct
17 Correct 401 ms 53084 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 5 ms 1064 KB Output is correct
3 Correct 5 ms 1076 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 0 ms 324 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 5 ms 984 KB Output is correct
17 Correct 45 ms 5708 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 324 KB Output is correct
22 Correct 1 ms 328 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 368 KB Output is correct
28 Correct 305 ms 41244 KB Output is correct
29 Correct 1 ms 324 KB Output is correct
30 Correct 384 ms 34096 KB Output is correct
31 Correct 384 ms 53136 KB Output is correct
32 Correct 400 ms 53260 KB Output is correct
33 Correct 1 ms 296 KB Output is correct
34 Correct 410 ms 53208 KB Output is correct
35 Correct 397 ms 53192 KB Output is correct
36 Correct 389 ms 52952 KB Output is correct
37 Correct 449 ms 52852 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 42 ms 5628 KB Output is correct
40 Correct 41 ms 5680 KB Output is correct
41 Correct 41 ms 5828 KB Output is correct
42 Correct 42 ms 5724 KB Output is correct
43 Correct 42 ms 5680 KB Output is correct
44 Correct 39 ms 5700 KB Output is correct
45 Correct 41 ms 5696 KB Output is correct
46 Correct 42 ms 5700 KB Output is correct
47 Correct 40 ms 5652 KB Output is correct
48 Correct 42 ms 5692 KB Output is correct
49 Correct 50 ms 5696 KB Output is correct
50 Correct 42 ms 5664 KB Output is correct
51 Correct 460 ms 53036 KB Output is correct
52 Correct 397 ms 53016 KB Output is correct
53 Correct 431 ms 52980 KB Output is correct
54 Correct 41 ms 5672 KB Output is correct
55 Correct 37 ms 5660 KB Output is correct
56 Correct 126 ms 18456 KB Output is correct
57 Correct 1 ms 212 KB Output is correct
58 Correct 43 ms 5624 KB Output is correct
59 Correct 39 ms 5668 KB Output is correct
60 Correct 482 ms 53188 KB Output is correct
61 Correct 44 ms 5684 KB Output is correct
62 Correct 40 ms 5740 KB Output is correct
63 Correct 39 ms 5656 KB Output is correct
64 Correct 44 ms 5640 KB Output is correct
65 Correct 44 ms 5672 KB Output is correct
66 Correct 43 ms 5668 KB Output is correct
67 Correct 43 ms 5744 KB Output is correct
68 Correct 36 ms 5688 KB Output is correct
69 Correct 41 ms 5664 KB Output is correct
70 Correct 444 ms 53096 KB Output is correct
71 Correct 40 ms 5696 KB Output is correct
72 Correct 389 ms 52964 KB Output is correct
73 Correct 401 ms 53084 KB Output is correct
74 Correct 1 ms 212 KB Output is correct
75 Correct 1 ms 212 KB Output is correct
76 Correct 1 ms 324 KB Output is correct
77 Correct 1 ms 320 KB Output is correct
78 Correct 1 ms 328 KB Output is correct
79 Correct 4 ms 980 KB Output is correct
80 Correct 448 ms 53176 KB Output is correct
81 Correct 463 ms 53008 KB Output is correct
82 Correct 426 ms 53084 KB Output is correct
83 Correct 425 ms 52728 KB Output is correct
84 Correct 429 ms 52952 KB Output is correct
85 Correct 434 ms 52760 KB Output is correct
86 Correct 118 ms 18448 KB Output is correct
87 Correct 1 ms 324 KB Output is correct