oj.uz

Submission #266356

# Submission time Handle Problem Language Result Execution time Memory
266356 2020-08-15T08:15:13 Z Thistle Strange Device (APIO19_strange_device) C++14
100 / 100
 3302 ms 72148 KB 
#pragma GCC target ("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<unordered_set>
#include<unordered_map>
#include<climits>
#include<fstream>
#include<complex>
#include<time.h>
#include<cassert>
#include<functional>
#include<numeric>
#include<tuple>
using namespace std;
using ll = long long;
using ld = long double;
#define int long long
#define all(a) (a).begin(),(a).end()
#define fs first
#define sc second
#define xx first
#define yy second.first
#define zz second.second
#define H pair<int, int>
#define P pair<int, pair<int, int>>
#define Q(i,j,k) mkp(i,mkp(j,k))
#define rng(i,s,n) for(int i = (s) ; i < (n) ; i++)
#define rep(i,n) rng(i, 0, (n))
#define mkp make_pair
#define vec vector
#define vi vec<int>
#define pb emplace_back
#define siz(a) (int)(a).size()
#define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end())
#define getidx(b,i) (lower_bound(all(b),(i))-(b).begin())
#define ssp(i,n) (i==(int)(n)-1?"\n":" ")
#define ctoi(c) (int)(c-'0')
#define itoc(c) (char)(c+'0')
#define cyes printf("Yes\n")
#define cno printf("No\n")
#define cdf(n) int quetimes_=(n);rep(qq123_,quetimes_)
#define gcj printf("Case #%lld: ",qq123_+1)
#define readv(a,n) a.resize(n,0);rep(i,(n)) a[i]=read()
#define found(a,x) (a.find(x)!=a.end())
//#define endl "\n"
constexpr int mod = (ll)1e9 + 7;
constexpr int Mod = 998244353;
constexpr ld EPS = 1e-10;
constexpr ll inf = (ll)3 * 1e18;
constexpr int Inf = (ll)15 * 1e8;
constexpr int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
ll read() { ll u, k = scanf("%lld", &u); return u; }
string reads() { string s; cin >> s; return s; }
H readh(short g = 0) { H u; int k = scanf("%lld %lld", &u.fs, &u.sc); if (g == 1) u.fs--, u.sc--; if (g == 2) u.fs--; return u; }
bool ina(H t, int h, int w) { return 0 <= t.fs && t.fs < h && 0 <= t.sc && t.sc < w; }
bool ina(int t, int l, int r) { return l <= t && t < r; }
ll gcd(ll i, ll j) { return j ? gcd(j, i % j) : i; }
ll popcount(ll x) {
    int sum = 0; for (int i = 0; i < 60; i++)if ((1ll << i) & x) sum++;
    return sum;
}
template<typename T>
class csum {
    vec<T> v;
public:
    csum(vec<T>& a) :v(a) { build(); }
    csum() {}
    void init(vec<T>& a) { v = a; build(); }
    void build() {
        for (int i = 1; i < v.size(); i++) v[i] += v[i - 1];
    }
    T a(int l, int r) {
        if (r < l) return 0;
        return v[r] - (l == 0 ? 0 : v[l - 1]);
    }//[l,r]
    T b(int l, int r) {
        return a(l, r - 1);
    }//[l,r)
    T a(pair<int, int>t) {
        return a(t.first, t.second);
    }
    T b(pair<int, int>t) {
        return b(t.first, t.second);
    }
};
class mint {
public:ll v;
      mint(ll v = 0) { s(v % mod + mod); }
      constexpr static int mod = (ll)1e9 + 7;
      constexpr static int fn_ = (ll)2e6 + 5;
      static mint fact[fn_], comp[fn_];
      mint pow(int x) const {
          mint b(v), c(1);
          while (x) {
              if (x & 1) c *= b;
              b *= b;
              x >>= 1;
          }
          return c;
      }
      inline mint& s(int vv) {
          v = vv < mod ? vv : vv - mod;
          return *this;
      }
      inline mint inv()const { return pow(mod - 2); }
      inline mint operator-()const { return mint() - *this; }
      inline mint& operator+=(const mint b) { return s(v + b.v); }
      inline mint& operator-=(const mint b) { return s(v + mod - b.v); }
      inline mint& operator*=(const mint b) { v = v * b.v % mod; return *this; }
      inline mint& operator/=(const mint b) { v = v * b.inv().v % mod; return *this; }
      inline mint operator+(const mint b) const { return mint(v) += b; }
      inline mint operator-(const mint b) const { return mint(v) -= b; }
      inline mint operator*(const mint b) const { return mint(v) *= b; }
      inline mint operator/(const mint b) const { return mint(v) /= b; }
      friend ostream& operator<<(ostream& os, const mint& m) {
          return os << m.v;
      }
      friend istream& operator>>(istream& is, mint& m) {
          int x; is >> x; m = mint(x);
          return is;
      }
      bool operator<(const mint& r)const { return v < r.v; }
      bool operator>(const mint& r)const { return v > r.v; }
      bool operator<=(const mint& r)const { return v <= r.v; }
      bool operator>=(const mint& r)const { return v >= r.v; }
      bool operator==(const mint& r)const { return v == r.v; }
      bool operator!=(const mint& r)const { return v != r.v; }
      explicit operator bool()const { return v; }
      explicit operator int()const { return v; }
      mint comb(mint k) {
          if (k > * this) return mint();
          if (!fact[0]) combinit();
          if (v >= fn_) {
              if (k > * this - k) k = *this - k;
              mint tmp(1);
              for (int i = v; i >= v - k.v + 1; i--) tmp *= mint(i);
              return tmp * comp[k.v];
          }
          return fact[v] * comp[k.v] * comp[v - k.v];
      }//nCk
      mint perm(mint k) {
          if (k > * this) return mint();
          if (!fact[0]) combinit();
          if (v >= fn_) {
              mint tmp(1);
              for (int i = v; i >= v - k.v + 1; i--) tmp *= mint(i);
              return tmp;
          }
          return fact[v] * comp[v - k.v];
      }//nPk
      static void combinit() {
          fact[0] = 1;
          for (int i = 1; i < fn_; i++) fact[i] = fact[i - 1] * mint(i);
          comp[fn_ - 1] = fact[fn_ - 1].inv();
          for (int i = fn_ - 2; i >= 0; i--) comp[i] = comp[i + 1] * mint(i + 1);
      }
}; mint mint::fact[fn_], mint::comp[fn_];
//--------------------------------------------------------------



//---------------------------------------------------------------------

int n, a, b;

using u128 = __uint128_t;

signed main() {
    cin >> n >> a >> b;

    int gd = gcd(a, b + 1);
    u128 shuki = (u128)a * (u128)b / gd;

    vec<pair<u128, u128>>v;

    rep(i, n) {
        int l, r; cin >> l >> r; r++;
        if (r - l >= shuki) {
            cout << (int)shuki << endl;
            return 0;
        }
        l %= shuki, r %= shuki;
        if (l < r) v.pb(mkp(l, r));
        else {
            v.pb(mkp(l, shuki));
            v.pb(mkp(0, r));
        }
    }

    sort(all(v));

    int ans = 0;
    vec<pair<u128, u128>>res;
    rep(i, siz(v)) {
        if (res.empty()) res.pb(v[i]);
        else {
            if (res.back().sc < v[i].fs) {
                res.pb(v[i]);
            }
            else {
                chmax(res.back().sc, v[i].sc);
            }
        }
    }
    for (auto g : res) ans += (int)(g.sc - g.fs);
    cout << ans << endl;
}

Compilation message

strange_device.cpp: In function 'll read()':
strange_device.cpp:72:19: warning: unused variable 'k' [-Wunused-variable]
   72 | ll read() { ll u, k = scanf("%lld", &u); return u; }
      |                   ^
strange_device.cpp: In function 'std::pair<long long int, long long int> readh(short int)':
strange_device.cpp:74:33: warning: unused variable 'k' [-Wunused-variable]
   74 | H readh(short g = 0) { H u; int k = scanf("%lld %lld", &u.fs, &u.sc); if (g == 1) u.fs--, u.sc--; if (g == 2) u.fs--; return u; }
      |                                 ^
strange_device.cpp: In function 'int main()':
strange_device.cpp:198:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'u128' {aka '__int128 unsigned'} [-Wsign-compare]
  198 |         if (r - l >= shuki) {
      |             ~~~~~~^~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31616 KB Output is correct
2 Correct 62 ms 32628 KB Output is correct
3 Correct 53 ms 32628 KB Output is correct
4 Correct 22 ms 31616 KB Output is correct
5 Correct 22 ms 31744 KB Output is correct
6 Correct 22 ms 31608 KB Output is correct
7 Correct 23 ms 31616 KB Output is correct
8 Correct 23 ms 31616 KB Output is correct
9 Correct 23 ms 31616 KB Output is correct
10 Correct 23 ms 31580 KB Output is correct
11 Correct 22 ms 31616 KB Output is correct
12 Correct 23 ms 31616 KB Output is correct
13 Correct 29 ms 31608 KB Output is correct
14 Correct 22 ms 31616 KB Output is correct
15 Correct 23 ms 31616 KB Output is correct
16 Correct 54 ms 32628 KB Output is correct
17 Correct 336 ms 38500 KB Output is correct
18 Correct 23 ms 31616 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31616 KB Output is correct
2 Correct 22 ms 31616 KB Output is correct
3 Correct 22 ms 31616 KB Output is correct
4 Correct 22 ms 31616 KB Output is correct
5 Correct 23 ms 31616 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31608 KB Output is correct
2 Correct 26 ms 31736 KB Output is correct
3 Correct 26 ms 31744 KB Output is correct
4 Correct 26 ms 31744 KB Output is correct
5 Correct 2310 ms 72148 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31616 KB Output is correct
2 Correct 3124 ms 69132 KB Output is correct
3 Correct 3152 ms 66684 KB Output is correct
4 Correct 3152 ms 66616 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31616 KB Output is correct
2 Correct 3124 ms 69132 KB Output is correct
3 Correct 3152 ms 66684 KB Output is correct
4 Correct 3152 ms 66616 KB Output is correct
5 Correct 25 ms 31616 KB Output is correct
6 Correct 3150 ms 66580 KB Output is correct
7 Correct 3302 ms 66668 KB Output is correct
8 Correct 3222 ms 66716 KB Output is correct
9 Correct 3263 ms 66848 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31616 KB Output is correct
2 Correct 3124 ms 69132 KB Output is correct
3 Correct 3152 ms 66684 KB Output is correct
4 Correct 3152 ms 66616 KB Output is correct
5 Correct 22 ms 31616 KB Output is correct
6 Correct 349 ms 38516 KB Output is correct
7 Correct 337 ms 38668 KB Output is correct
8 Correct 332 ms 38628 KB Output is correct
9 Correct 340 ms 38500 KB Output is correct
10 Correct 344 ms 38500 KB Output is correct
11 Correct 339 ms 38500 KB Output is correct
12 Correct 349 ms 38676 KB Output is correct
13 Correct 343 ms 38628 KB Output is correct
14 Correct 330 ms 38500 KB Output is correct
15 Correct 352 ms 38500 KB Output is correct
16 Correct 338 ms 38704 KB Output is correct
17 Correct 337 ms 38624 KB Output is correct
18 Correct 3155 ms 70212 KB Output is correct
19 Correct 3116 ms 66924 KB Output is correct
20 Correct 3290 ms 67020 KB Output is correct
21 Correct 341 ms 38804 KB Output is correct
22 Correct 334 ms 38620 KB Output is correct
23 Correct 1117 ms 53652 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31616 KB Output is correct
2 Correct 363 ms 38500 KB Output is correct
3 Correct 337 ms 38504 KB Output is correct
4 Correct 3277 ms 68484 KB Output is correct
5 Correct 335 ms 38648 KB Output is correct
6 Correct 350 ms 38500 KB Output is correct
7 Correct 336 ms 38636 KB Output is correct
8 Correct 338 ms 38500 KB Output is correct
9 Correct 337 ms 38628 KB Output is correct
10 Correct 355 ms 38500 KB Output is correct
11 Correct 338 ms 38748 KB Output is correct
12 Correct 332 ms 38816 KB Output is correct
13 Correct 337 ms 38632 KB Output is correct
14 Correct 3211 ms 68312 KB Output is correct
15 Correct 335 ms 38748 KB Output is correct
16 Correct 3170 ms 64768 KB Output is correct
17 Correct 3131 ms 70176 KB Output is correct
18 Correct 23 ms 31616 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31616 KB Output is correct
2 Correct 62 ms 32628 KB Output is correct
3 Correct 53 ms 32628 KB Output is correct
4 Correct 22 ms 31616 KB Output is correct
5 Correct 22 ms 31744 KB Output is correct
6 Correct 22 ms 31608 KB Output is correct
7 Correct 23 ms 31616 KB Output is correct
8 Correct 23 ms 31616 KB Output is correct
9 Correct 23 ms 31616 KB Output is correct
10 Correct 23 ms 31580 KB Output is correct
11 Correct 22 ms 31616 KB Output is correct
12 Correct 23 ms 31616 KB Output is correct
13 Correct 29 ms 31608 KB Output is correct
14 Correct 22 ms 31616 KB Output is correct
15 Correct 23 ms 31616 KB Output is correct
16 Correct 54 ms 32628 KB Output is correct
17 Correct 336 ms 38500 KB Output is correct
18 Correct 23 ms 31616 KB Output is correct
19 Correct 22 ms 31616 KB Output is correct
20 Correct 22 ms 31616 KB Output is correct
21 Correct 22 ms 31616 KB Output is correct
22 Correct 22 ms 31616 KB Output is correct
23 Correct 23 ms 31616 KB Output is correct
24 Correct 23 ms 31608 KB Output is correct
25 Correct 26 ms 31736 KB Output is correct
26 Correct 26 ms 31744 KB Output is correct
27 Correct 26 ms 31744 KB Output is correct
28 Correct 2310 ms 72148 KB Output is correct
29 Correct 22 ms 31616 KB Output is correct
30 Correct 3124 ms 69132 KB Output is correct
31 Correct 3152 ms 66684 KB Output is correct
32 Correct 3152 ms 66616 KB Output is correct
33 Correct 25 ms 31616 KB Output is correct
34 Correct 3150 ms 66580 KB Output is correct
35 Correct 3302 ms 66668 KB Output is correct
36 Correct 3222 ms 66716 KB Output is correct
37 Correct 3263 ms 66848 KB Output is correct
38 Correct 22 ms 31616 KB Output is correct
39 Correct 349 ms 38516 KB Output is correct
40 Correct 337 ms 38668 KB Output is correct
41 Correct 332 ms 38628 KB Output is correct
42 Correct 340 ms 38500 KB Output is correct
43 Correct 344 ms 38500 KB Output is correct
44 Correct 339 ms 38500 KB Output is correct
45 Correct 349 ms 38676 KB Output is correct
46 Correct 343 ms 38628 KB Output is correct
47 Correct 330 ms 38500 KB Output is correct
48 Correct 352 ms 38500 KB Output is correct
49 Correct 338 ms 38704 KB Output is correct
50 Correct 337 ms 38624 KB Output is correct
51 Correct 3155 ms 70212 KB Output is correct
52 Correct 3116 ms 66924 KB Output is correct
53 Correct 3290 ms 67020 KB Output is correct
54 Correct 341 ms 38804 KB Output is correct
55 Correct 334 ms 38620 KB Output is correct
56 Correct 1117 ms 53652 KB Output is correct
57 Correct 22 ms 31616 KB Output is correct
58 Correct 363 ms 38500 KB Output is correct
59 Correct 337 ms 38504 KB Output is correct
60 Correct 3277 ms 68484 KB Output is correct
61 Correct 335 ms 38648 KB Output is correct
62 Correct 350 ms 38500 KB Output is correct
63 Correct 336 ms 38636 KB Output is correct
64 Correct 338 ms 38500 KB Output is correct
65 Correct 337 ms 38628 KB Output is correct
66 Correct 355 ms 38500 KB Output is correct
67 Correct 338 ms 38748 KB Output is correct
68 Correct 332 ms 38816 KB Output is correct
69 Correct 337 ms 38632 KB Output is correct
70 Correct 3211 ms 68312 KB Output is correct
71 Correct 335 ms 38748 KB Output is correct
72 Correct 3170 ms 64768 KB Output is correct
73 Correct 3131 ms 70176 KB Output is correct
74 Correct 23 ms 31616 KB Output is correct
75 Correct 22 ms 31608 KB Output is correct
76 Correct 23 ms 31616 KB Output is correct
77 Correct 26 ms 31616 KB Output is correct
78 Correct 23 ms 31616 KB Output is correct
79 Correct 54 ms 32628 KB Output is correct
80 Correct 3246 ms 70396 KB Output is correct
81 Correct 3266 ms 69908 KB Output is correct
82 Correct 3286 ms 69308 KB Output is correct
83 Correct 3210 ms 68768 KB Output is correct
84 Correct 3250 ms 68772 KB Output is correct
85 Correct 3275 ms 68540 KB Output is correct
86 Correct 1069 ms 53776 KB Output is correct
87 Correct 23 ms 31616 KB Output is correct