oj.uz

Submission #527029

# Submission time Handle Problem Language Result Execution time Memory
527029 2022-02-16T20:05:07 Z Lobo Strange Device (APIO19_strange_device) C++17
0 / 100
 299 ms 131796 KB 
#include<bits/stdc++.h>
using namespace std;
 
const long long inf = (long long) 2e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
 
#define maxn 

int gcdd(int a, int b) {
    if(b == 0) return a;
    a%=b;
    return gcdd(b,a);
}
 
void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    int gc = gcdd(a,b+1);
    int q = (b+1)/gc;
    int m;
    if(log2(a) + log2(b) + log2(q) - log2(b+1) > log2(inf)) m = inf;
    else {
        // assert((a*b*q)%(b+1) == 0);
        m = ((a*q)/(b+1))*b;
    }
 
    vector<pair<int,int>> lr;
 
    for(int i = 1; i <= n; i++) {
        int l, r; cin >> l >> r;
 
        if(r-l+1 >= m) {
            lr.pb(mp(0,m-1));
        }
        else if(l/m != r/m) {
            //terminam em cantos diferentes
            l%= m;
            r%= m;
            //colocar l,m-1 e 0,r
            lr.pb(mp(l,m-1));
            lr.pb(mp(0,r));
        }
        else {
            l%= m;
            r%= m;
            lr.pb(mp(l,r));
        }
    }
 
    sort(all(lr));
 
    int l = 0;
    int r = -1;
    int ans = 0;
    for(auto x : lr) {
        int l1 = x.fr;
        int r1 = x.sc;

 
        if(l1 > r) {
            //conta o lr anterior e comeca um novo
            ans+= r-l+1;
            l = l1;
            r = r1;
        }
        r = max(r,r1);
    }
 
    ans+= r-l+1;
    cout << ans << endl;
 
 
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);
 
    int tt = 1;
    // cin >> tt;
    while(tt--) solve();
 
}

Compilation message

strange_device.cpp: In function 'int32_t main()':
strange_device.cpp:86:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     freopen("in.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 30.0

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