oj.uz

Submission #268494

# Submission time Handle Problem Language Result Execution time Memory
268494 2020-08-16T12:19:42 Z evpipis Strange Device (APIO19_strange_device) C++11
15 / 100
 643 ms 51648 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> pll;

const ll mx = 1e18;
vector<pll> vec, help;

ll gcd(ll a, ll b){
    if (a == 0)
        return b;
    return gcd(b%a, a);
}

ll find_fir(ll a, ll b){
    ll ans = a/gcd(a, b+1);
    if (ans <= mx/b)
        ans = ans*b;
    else
        ans = mx+1;
    return ans;
}

//set<ll> mys;

ll solve(ll m){
    for (int i = 0; i < vec.size(); i++){
        pll cur = vec[i];
        if (cur.se-cur.fi+1 >= m)
            return m;

        //for (int j = cur.fi; j <= cur.se; j++)
          //  mys.insert(j%m);

        cur.fi %= m;
        cur.se %= m;

        if (cur.fi <= cur.se)
            help.pb(cur);
        else
            help.pb(mp(0, cur.se)), help.pb(mp(cur.fi, m-1));
    }

    //return mys.size();

    ll ans = 0;
    /*for (int i = 0; i < m; i++){
        int fin = 0;
        for (int j = 0; j < help.size(); j++)
            if (help[j].fi <= i && i <= help[j].fi)
                fin = 1;

        ans += fin;
    }

    return ans;*/
    sort(help.begin(), help.end());
    for (int i = 0; i < help.size(); i++){
        pll cur = help[i];
        if (i+1 < help.size() && help[i+1].fi-1 < cur.se)
            ans += help[i+1].fi-cur.fi;
        else
            ans += cur.se-cur.fi+1;
    }

    return ans;
}

int main(){
    int n;
    ll a, b;
    scanf("%d %lld %lld", &n, &a, &b);

    ll m = find_fir(a, b);
    //assert(m <= mx);

    for (int i = 0; i < n; i++){
        ll l, r;
        scanf("%lld %lld", &l, &r);
        vec.pb(mp(l, r));
    }

    //printf("%lld\n", m);
    printf("%lld\n", solve(m));
    return 0;
}

Compilation message

strange_device.cpp: In function 'll solve(ll)':
strange_device.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < vec.size(); i++){
      |                     ~~^~~~~~~~~~~~
strange_device.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int i = 0; i < help.size(); i++){
      |                     ~~^~~~~~~~~~~~~
strange_device.cpp:65:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         if (i+1 < help.size() && help[i+1].fi-1 < cur.se)
      |             ~~~~^~~~~~~~~~~~~
strange_device.cpp: In function 'int main()':
strange_device.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |     scanf("%d %lld %lld", &n, &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |         scanf("%lld %lld", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Incorrect 7 ms 892 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 1 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 553 ms 40664 KB Output is correct
3 Correct 552 ms 41176 KB Output is correct
4 Correct 536 ms 51364 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 553 ms 40664 KB Output is correct
3 Correct 552 ms 41176 KB Output is correct
4 Correct 536 ms 51364 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 562 ms 51648 KB Output is correct
7 Correct 579 ms 51500 KB Output is correct
8 Correct 546 ms 51532 KB Output is correct
9 Correct 588 ms 51384 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 553 ms 40664 KB Output is correct
3 Correct 552 ms 41176 KB Output is correct
4 Correct 536 ms 51364 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 56 ms 8744 KB Output is correct
7 Correct 58 ms 8680 KB Output is correct
8 Correct 53 ms 8680 KB Output is correct
9 Correct 64 ms 8804 KB Output is correct
10 Correct 57 ms 8696 KB Output is correct
11 Correct 58 ms 8676 KB Output is correct
12 Correct 55 ms 8828 KB Output is correct
13 Correct 60 ms 8680 KB Output is correct
14 Correct 58 ms 8764 KB Output is correct
15 Incorrect 61 ms 8676 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 61 ms 5348 KB Output is correct
3 Correct 65 ms 5352 KB Output is correct
4 Correct 643 ms 41020 KB Output is correct
5 Correct 56 ms 5352 KB Output is correct
6 Correct 67 ms 5436 KB Output is correct
7 Correct 57 ms 5352 KB Output is correct
8 Correct 65 ms 5384 KB Output is correct
9 Correct 55 ms 5348 KB Output is correct
10 Correct 58 ms 5352 KB Output is correct
11 Correct 59 ms 5356 KB Output is correct
12 Correct 49 ms 5352 KB Output is correct
13 Correct 58 ms 5348 KB Output is correct
14 Incorrect 605 ms 41024 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Incorrect 7 ms 892 KB Output isn't correct
3 Halted 0 ms 0 KB -