oj.uz

Submission #784483

# Submission time Handle Problem Language Result Execution time Memory
784483 2023-07-16T07:21:09 Z kebine Strange Device (APIO19_strange_device) C++17
65 / 100
 662 ms 100824 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
#define fi first
#define se second
//*AC BERSAMA ALLAH  FORTIS FORTUNA ADIUVAT
//# nyampah
ll sz;
vector<pair<ll,bool> > lr;
vector<pair<ll,ll> > lr1;
ll n, a, b;

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

ll szz(ll x, ll y){
    if((y+1)%a==0) return y+1;
    else{
        return (x*y);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin>>n>>a>>b;
    // sz = abs(szz(a,b));
    sz = (__int128_t) a * b / gcd(a,b+1);
    // cout<<sz<<'\n';

    for(int i=0;i<n;i++){
        ll l,r; cin>>l>>r;
        l%=sz; r%=sz;
        if(l>r){
            lr.pb(make_pair(0,0)); lr.pb(make_pair(r,1));
            lr.pb(make_pair(l,0)); lr.pb(make_pair(sz-1,1));
        }
        else {
            lr.pb(make_pair(l,0)); lr.pb(make_pair(r,1));
        }
    }
    sort(lr.begin(),lr.end());

    ll cnt=0, l, r;
    for(auto i : lr){
        if(i.se == 0){
            if(cnt==0) l=i.fi;
            cnt++;
        }
        else cnt--;
        
        if(cnt==0){
            r = i.fi;
            lr1.pb(make_pair(l,r));
        }
    }

    ll ans=0;
    for(auto i : lr1){
        ans+=(i.second-i.first+1);
    }
    cout<<ans<<'\n';
    return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:58:33: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |             lr1.pb(make_pair(l,r));
      |                                 ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 6 ms 980 KB Output is correct
3 Correct 5 ms 980 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 4 ms 1040 KB Output is correct
17 Correct 51 ms 9772 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 275 ms 33232 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 536 ms 63636 KB Output is correct
3 Correct 452 ms 63604 KB Output is correct
4 Correct 409 ms 100824 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 536 ms 63636 KB Output is correct
3 Correct 452 ms 63604 KB Output is correct
4 Correct 409 ms 100824 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 444 ms 100744 KB Output is correct
7 Correct 484 ms 100760 KB Output is correct
8 Correct 495 ms 100752 KB Output is correct
9 Correct 534 ms 100756 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 536 ms 63636 KB Output is correct
3 Correct 452 ms 63604 KB Output is correct
4 Correct 409 ms 100824 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 40 ms 10736 KB Output is correct
7 Correct 52 ms 10744 KB Output is correct
8 Correct 40 ms 10720 KB Output is correct
9 Correct 41 ms 10712 KB Output is correct
10 Correct 48 ms 10748 KB Output is correct
11 Correct 55 ms 10744 KB Output is correct
12 Correct 46 ms 10676 KB Output is correct
13 Correct 49 ms 10756 KB Output is correct
14 Correct 40 ms 10684 KB Output is correct
15 Correct 48 ms 10756 KB Output is correct
16 Correct 47 ms 10752 KB Output is correct
17 Correct 41 ms 10700 KB Output is correct
18 Correct 470 ms 100724 KB Output is correct
19 Correct 452 ms 100716 KB Output is correct
20 Correct 593 ms 100796 KB Output is correct
21 Correct 49 ms 10660 KB Output is correct
22 Correct 44 ms 10756 KB Output is correct
23 Correct 115 ms 26652 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 49 ms 7604 KB Output is correct
3 Correct 53 ms 7556 KB Output is correct
4 Correct 662 ms 64240 KB Output is correct
5 Correct 46 ms 7508 KB Output is correct
6 Correct 67 ms 7460 KB Output is correct
7 Correct 45 ms 7492 KB Output is correct
8 Correct 48 ms 7552 KB Output is correct
9 Correct 44 ms 7552 KB Output is correct
10 Correct 47 ms 7552 KB Output is correct
11 Correct 58 ms 7520 KB Output is correct
12 Correct 49 ms 7588 KB Output is correct
13 Correct 48 ms 7552 KB Output is correct
14 Correct 528 ms 64336 KB Output is correct
15 Correct 48 ms 7352 KB Output is correct
16 Correct 420 ms 100748 KB Output is correct
17 Correct 460 ms 100740 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 6 ms 980 KB Output is correct
3 Correct 5 ms 980 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 4 ms 1040 KB Output is correct
17 Correct 51 ms 9772 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Incorrect 0 ms 212 KB Output isn't correct
21 Halted 0 ms 0 KB -