oj.uz

Submission #784527

# Submission time Handle Problem Language Result Execution time Memory
784527 2023-07-16T07:58:49 Z kebine Strange Device (APIO19_strange_device) C++17
65 / 100
 706 ms 64324 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);
}

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 * 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(),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 984 KB Output is correct
3 Correct 6 ms 1256 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 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 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 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 6 ms 1112 KB Output is correct
17 Correct 64 ms 7576 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 0 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 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 380 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 355 ms 33948 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 532 ms 63664 KB Output is correct
3 Correct 563 ms 64148 KB Output is correct
4 Correct 528 ms 63788 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 532 ms 63664 KB Output is correct
3 Correct 563 ms 64148 KB Output is correct
4 Correct 528 ms 63788 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 554 ms 63932 KB Output is correct
7 Correct 530 ms 63756 KB Output is correct
8 Correct 540 ms 63840 KB Output is correct
9 Correct 666 ms 63872 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 532 ms 63664 KB Output is correct
3 Correct 563 ms 64148 KB Output is correct
4 Correct 528 ms 63788 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 48 ms 7536 KB Output is correct
7 Correct 53 ms 7532 KB Output is correct
8 Correct 50 ms 7480 KB Output is correct
9 Correct 51 ms 7536 KB Output is correct
10 Correct 46 ms 7540 KB Output is correct
11 Correct 52 ms 7484 KB Output is correct
12 Correct 48 ms 7520 KB Output is correct
13 Correct 60 ms 7608 KB Output is correct
14 Correct 47 ms 7468 KB Output is correct
15 Correct 60 ms 7484 KB Output is correct
16 Correct 59 ms 7544 KB Output is correct
17 Correct 57 ms 7500 KB Output is correct
18 Correct 560 ms 63904 KB Output is correct
19 Correct 548 ms 63784 KB Output is correct
20 Correct 680 ms 63772 KB Output is correct
21 Correct 61 ms 7364 KB Output is correct
22 Correct 55 ms 7376 KB Output is correct
23 Correct 121 ms 17156 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 56 ms 7032 KB Output is correct
3 Correct 64 ms 7568 KB Output is correct
4 Correct 706 ms 64324 KB Output is correct
5 Correct 60 ms 7592 KB Output is correct
6 Correct 58 ms 7464 KB Output is correct
7 Correct 62 ms 7508 KB Output is correct
8 Correct 62 ms 7584 KB Output is correct
9 Correct 55 ms 7528 KB Output is correct
10 Correct 62 ms 7540 KB Output is correct
11 Correct 58 ms 7576 KB Output is correct
12 Correct 53 ms 7600 KB Output is correct
13 Correct 61 ms 7424 KB Output is correct
14 Correct 655 ms 64248 KB Output is correct
15 Correct 61 ms 7320 KB Output is correct
16 Correct 501 ms 63784 KB Output is correct
17 Correct 555 ms 63788 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 5 ms 984 KB Output is correct
3 Correct 6 ms 1256 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 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 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 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 6 ms 1112 KB Output is correct
17 Correct 64 ms 7576 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Incorrect 0 ms 212 KB Output isn't correct
21 Halted 0 ms 0 KB -