oj.uz

Submission #268493

# Submission time Handle Problem Language Result Execution time Memory
268493 2020-08-16T12:18:13 Z evpipis Strange Device (APIO19_strange_device) C++11
0 / 100
 5000 ms 524292 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 1 ms 288 KB Output is correct
2 Execution timed out 5074 ms 304648 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
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 Runtime error 3122 ms 524292 KB Execution killed with signal 9
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 Execution timed out 5056 ms 45576 KB Time limit exceeded
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 Execution timed out 5081 ms 74064 KB Time limit exceeded
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 Execution timed out 5081 ms 74064 KB Time limit exceeded
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 Execution timed out 5081 ms 74064 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

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

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Execution timed out 5074 ms 304648 KB Time limit exceeded
3 Halted 0 ms 0 KB -