oj.uz

Submission #268471

# Submission time Handle Problem Language Result Execution time Memory
268471 2020-08-16T12:08:39 Z evpipis Strange Device (APIO19_strange_device) C++11
0 / 100
 508 ms 37572 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 (a <= mx/b)
        ans = a*b;
    else
        ans = mx+1;
    return ans;
}

int cnt[1000006];

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++)
            cnt[j%m] = 1;

        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));
    }

    ll ans = 0;
    for (int i = 0; i < m; i++)
        ans += cnt[i];
    return ans;
    /*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:64: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]
   64 |     for (int i = 0; i < help.size(); i++){
      |                     ~~^~~~~~~~~~~~~
strange_device.cpp:66: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]
   66 |         if (i+1 < help.size() && help[i+1].fi-1 < cur.se)
      |             ~~~~^~~~~~~~~~~~~
strange_device.cpp: In function 'int main()':
strange_device.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |     scanf("%d %lld %lld", &n, &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |         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 Runtime error 6 ms 1020 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Runtime error 13 ms 8320 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Runtime error 2 ms 512 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Runtime error 508 ms 37572 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Runtime error 508 ms 37572 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Runtime error 508 ms 37572 KB Execution killed with signal 11
3 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 Runtime error 54 ms 3896 KB Execution killed with signal 11
3 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 Runtime error 6 ms 1020 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -