oj.uz

답안 #784533

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
784533 2023-07-16T08:07:43 Z andecaandeci 이상한 기계 (APIO19_strange_device) C++17
65 / 100
 700 ms 63740 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 / 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 5 ms 1036 KB Output is correct
3 Correct 5 ms 980 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 1 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 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 5 ms 1036 KB Output is correct
17 Correct 62 ms 7036 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 317 ms 33280 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 522 ms 63620 KB Output is correct
3 Correct 575 ms 63596 KB Output is correct
4 Correct 544 ms 63628 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 522 ms 63620 KB Output is correct
3 Correct 575 ms 63596 KB Output is correct
4 Correct 544 ms 63628 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 551 ms 63632 KB Output is correct
7 Correct 537 ms 63680 KB Output is correct
8 Correct 533 ms 63688 KB Output is correct
9 Correct 700 ms 63688 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 522 ms 63620 KB Output is correct
3 Correct 575 ms 63596 KB Output is correct
4 Correct 544 ms 63628 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 50 ms 7076 KB Output is correct
7 Correct 51 ms 7052 KB Output is correct
8 Correct 46 ms 7068 KB Output is correct
9 Correct 51 ms 6980 KB Output is correct
10 Correct 45 ms 7036 KB Output is correct
11 Correct 49 ms 6972 KB Output is correct
12 Correct 55 ms 7144 KB Output is correct
13 Correct 59 ms 7044 KB Output is correct
14 Correct 48 ms 7024 KB Output is correct
15 Correct 60 ms 6968 KB Output is correct
16 Correct 61 ms 7104 KB Output is correct
17 Correct 49 ms 7036 KB Output is correct
18 Correct 553 ms 63664 KB Output is correct
19 Correct 512 ms 63644 KB Output is correct
20 Correct 698 ms 63628 KB Output is correct
21 Correct 60 ms 6972 KB Output is correct
22 Correct 49 ms 7052 KB Output is correct
23 Correct 121 ms 16876 KB Output is correct

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 55 ms 7048 KB Output is correct
3 Correct 56 ms 7036 KB Output is correct
4 Correct 696 ms 63740 KB Output is correct
5 Correct 59 ms 7040 KB Output is correct
6 Correct 57 ms 7052 KB Output is correct
7 Correct 59 ms 7048 KB Output is correct
8 Correct 59 ms 7044 KB Output is correct
9 Correct 54 ms 6968 KB Output is correct
10 Correct 61 ms 7040 KB Output is correct
11 Correct 57 ms 6984 KB Output is correct
12 Correct 47 ms 7036 KB Output is correct
13 Correct 60 ms 7036 KB Output is correct
14 Correct 644 ms 63736 KB Output is correct
15 Correct 60 ms 6844 KB Output is correct
16 Correct 498 ms 63648 KB Output is correct
17 Correct 543 ms 63740 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 5 ms 1036 KB Output is correct
3 Correct 5 ms 980 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 1 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 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 5 ms 1036 KB Output is correct
17 Correct 62 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 0 ms 212 KB Output isn't correct
21 Halted 0 ms 0 KB -