oj.uz

Submission #133260

# Submission time Handle Problem Language Result Execution time Memory
133260 2019-07-20T10:12:52 Z mbrc Strange Device (APIO19_strange_device) C++14
0 / 100
 2 ms 424 KB 
#define DEBUG
// #define FASTIO

#include <cstring>
#include <cassert>
#include <utility>
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <bitset>
#include <chrono>
#include <cstdlib>
#include <functional>
#include <tuple>
#include <climits>
#include <limits>
#include <deque>
#include <list>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <complex>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

#define F first
#define S second 
#define pb push_back
#define endl "\n"

#ifdef FASTIO

#define pr(x) printf("%d", x)
#define ps    printf(" ")
#define endc  printf("\n")
#define pl(x) printf("%lld", x)
#define pf(x) printf("%lf", x)
#define sc(x) scanf("%d", &x)
#define sl(x) scanf("%lld", &x)
#define sf(x) scanf("%lf", &x)
#define IOS 

#endif

#ifndef FASTIO
    #define IOS { ios :: sync_with_stdio(false); cin.tie(0); }
#endif

#ifdef DEBUG
    #define dbg(s) {s;}
#endif

#ifndef DEBUG
    #define dbg(s)
#endif

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int grand(int x) { // from [0, n-1]
    return uniform_int_distribution<int>(0, x - 1)(rng);
}

#define int ll
#define i32 int32_t
#define all(v) (v).begin(),(v).end()

typedef long long ll;
typedef long double ld;
typedef pair< int, int > pii;
typedef pair< ll, ll > pll;

inline string ps(pii z) {
    stringstream ss; ss << "[" << z.F << ", " << z.S << "]";
    return ss.str();
}

ll gcd(ll x, ll y) {
    if (x < y) return gcd(y, x);
    if (y == 0) return x;
    return gcd(y, x % y);
} 

const ll mod = 1e9 + 7;

ll modexp(ll x, ll ex) {
    ll ans = 1ll;
    while (ex > 0) {
        if (ex & 1ll) ans = (ans * x) % mod;
        ex >>= 1ll;
        x = (x * x) % mod;
    }
    return ans;
}

const int maxn = 1e6 + 7;

const ll inf = 1e18 + 7;

vector < pii > v;

i32 main() {
    //freopen("<file>.in", "r", stdin);
    //freopen("<file>.out", "w", stdout);

    IOS;
    
    int n, A, B; cin >> n >> A >> B;
    int g = gcd(A, B + 1); A /= g;
    if (A >= inf / B) A = inf;
    else A *= B;

    int ms = A;
    int mp = -1;

    for (int j = 1; j <= n; j++) {
        int l, r; cin >> l >> r;
        if (l - r + 1 >= A) {
            cout << A + 1 << endl; return 0;
        }
        if (l <= A * (r / A)) {
            v.pb({0, r % A});
            if (l < A * (r / A))
                v.pb({l % A, A - 1});
        } else {
            v.pb({l % A, r % A});
        }
    }

    sort(all(v));
    
    int ans = 0;

    for (int j = 0; j < v.size(); ) {
        int i = j; pii ci = v[j];
        while (i + 1 < v.size() && v[i + 1].F <= ci.S) {
            i++; ci.S = max(ci.S, v[i].S);
        }
        j = i + 1;
        ans += ci.S - ci.F + 1;
    }
    cout << ans << endl;
}

Compilation message

strange_device.cpp: In function 'int32_t main()':
strange_device.cpp:140:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < v.size(); ) {
                     ~~^~~~~~~~~~
strange_device.cpp:142:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (i + 1 < v.size() && v[i + 1].F <= ci.S) {
                ~~~~~~^~~~~~~~~~
strange_device.cpp:119:9: warning: unused variable 'ms' [-Wunused-variable]
     int ms = A;
         ^~
strange_device.cpp:120:9: warning: unused variable 'mp' [-Wunused-variable]
     int mp = -1;
         ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -