oj.uz

Submission #784534

# Submission time Handle Problem Language Result Execution time Memory
784534 2023-07-16T08:08:33 Z kebine Strange Device (APIO19_strange_device) C++17
65 / 100
 703 ms 63736 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
__int128_t 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);
}

bool comp(pair<ll,bool> a, pair<ll,bool> b){
    if(a.fi==b.fi) return a.se<b.se;
    else return a.fi<b.fi;
}

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 / gcd(a,b+1) * b ;
    // 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(),comp);

    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:56:33: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |             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 5 ms 1028 KB Output is correct
3 Correct 5 ms 984 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 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 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 5 ms 984 KB Output is correct
17 Correct 65 ms 7036 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 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 0 ms 212 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 309 ms 33276 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 539 ms 63728 KB Output is correct
3 Correct 576 ms 63636 KB Output is correct
4 Correct 528 ms 63668 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 539 ms 63728 KB Output is correct
3 Correct 576 ms 63636 KB Output is correct
4 Correct 528 ms 63668 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 552 ms 63640 KB Output is correct
7 Correct 531 ms 63672 KB Output is correct
8 Correct 542 ms 63644 KB Output is correct
9 Correct 662 ms 63636 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 539 ms 63728 KB Output is correct
3 Correct 576 ms 63636 KB Output is correct
4 Correct 528 ms 63668 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 47 ms 7032 KB Output is correct
7 Correct 53 ms 7044 KB Output is correct
8 Correct 47 ms 7028 KB Output is correct
9 Correct 51 ms 7032 KB Output is correct
10 Correct 45 ms 6968 KB Output is correct
11 Correct 50 ms 6972 KB Output is correct
12 Correct 46 ms 6948 KB Output is correct
13 Correct 60 ms 7032 KB Output is correct
14 Correct 47 ms 6992 KB Output is correct
15 Correct 65 ms 7036 KB Output is correct
16 Correct 58 ms 6992 KB Output is correct
17 Correct 50 ms 6944 KB Output is correct
18 Correct 554 ms 63732 KB Output is correct
19 Correct 512 ms 63636 KB Output is correct
20 Correct 665 ms 63640 KB Output is correct
21 Correct 60 ms 7040 KB Output is correct
22 Correct 43 ms 7048 KB Output is correct
23 Correct 124 ms 16948 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 55 ms 7036 KB Output is correct
3 Correct 59 ms 7032 KB Output is correct
4 Correct 703 ms 63592 KB Output is correct
5 Correct 57 ms 7064 KB Output is correct
6 Correct 57 ms 7032 KB Output is correct
7 Correct 58 ms 7032 KB Output is correct
8 Correct 59 ms 6988 KB Output is correct
9 Correct 54 ms 7016 KB Output is correct
10 Correct 60 ms 7048 KB Output is correct
11 Correct 57 ms 7036 KB Output is correct
12 Correct 49 ms 7052 KB Output is correct
13 Correct 60 ms 7036 KB Output is correct
14 Correct 659 ms 63680 KB Output is correct
15 Correct 60 ms 6840 KB Output is correct
16 Correct 502 ms 63736 KB Output is correct
17 Correct 539 ms 63636 KB Output is correct
18 Correct 0 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 5 ms 1028 KB Output is correct
3 Correct 5 ms 984 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 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 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 5 ms 984 KB Output is correct
17 Correct 65 ms 7036 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Incorrect 1 ms 212 KB Output isn't correct
21 Halted 0 ms 0 KB -