Submission #806626

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
806626	2023-08-04T08:24:59 Z	gg123_pe	Strange Device (APIO19_strange_device)	C++14	35 / 100	1249 ms	78612 KB

strange_device

#include <bits/stdc++.h> 
using namespace std; 

typedef long long ll; 
#define f(i,a,b) for(int i = a; i < b; i++)
const int N = 1e6 + 5; 
const ll inf = 1e18 + 5; 

int n; 
ll l[N], r[N]; 
ll A, B, S; 

void subtask_1(){
    set <pair<ll,ll>> s;

    f(i,1,n+1){
        for(ll j = l[i]; j <= r[i]; j++){
            ll a, b; 
            a = (j + j/B) % A; 
            b = j % B; 
            s.insert({a, b}); 
        }
    }
    cout << s.size() << "\n"; 
}
ll gcd(ll x, ll y){
    return y == 0 ? x : gcd(y, x%y); 
}
void solve(){
    ll X = A / gcd(A, B+1);  
    ll period = X * B;  

    set <pair<ll,ll>> s; 

    f(i,1,n+1){
        ll len = r[i] - l[i] + 1;  
        if(len >= period){
            cout << period << "\n"; 
            return; 
        }
        ll x = l[i] % period;
        if(len > period-x){
            s.insert({x, period-1}); 
            s.insert({0, r[i]%period}); 
        }   
        else{
            s.insert({x, r[i]%period}); 
        }
    }
    ll ans = 0, l, r;
    auto it = s.begin(); 
    l = it->first, r = it->second; 
    for(auto p: s){
        if(p == *it) continue; 
        ll x = p.first, y = p.second; 

        if(x <= r){
            r = max(r, y); 
        }
        else if(x == r+1){
            r = y; 
        }
        else{
            ans += r - l + 1; 
            l = x, r = y; 
        }
    }
    ans += r - l + 1; 
    cout << ans << "\n"; 
}
int main(){
    cin >> n >> A >> B; 

    f(i,1,n+1){
        cin >> l[i] >> r[i]; 
    }

    solve(); 

    return 0; 
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	12 ms	1232 KB	Output is correct
3	Correct	11 ms	1344 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	312 KB	Output is correct
8	Correct	1 ms	308 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 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	308 KB	Output is correct
16	Correct	11 ms	1364 KB	Output is correct
17	Correct	108 ms	8568 KB	Output is correct
18	Incorrect	0 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	2 ms	360 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	2 ms	340 KB	Output is correct
5	Correct	705 ms	15980 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	1178 ms	78532 KB	Output is correct
3	Correct	1159 ms	78496 KB	Output is correct
4	Correct	1148 ms	78604 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	1178 ms	78532 KB	Output is correct
3	Correct	1159 ms	78496 KB	Output is correct
4	Correct	1148 ms	78604 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1165 ms	78500 KB	Output is correct
7	Correct	1232 ms	78484 KB	Output is correct
8	Correct	1213 ms	78600 KB	Output is correct
9	Correct	1166 ms	78612 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	1178 ms	78532 KB	Output is correct
3	Correct	1159 ms	78496 KB	Output is correct
4	Correct	1148 ms	78604 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	114 ms	8380 KB	Output is correct
7	Correct	114 ms	8636 KB	Output is correct
8	Correct	121 ms	8608 KB	Output is correct
9	Correct	120 ms	8644 KB	Output is correct
10	Correct	117 ms	8640 KB	Output is correct
11	Correct	111 ms	8572 KB	Output is correct
12	Correct	106 ms	8520 KB	Output is correct
13	Correct	111 ms	8636 KB	Output is correct
14	Correct	117 ms	8596 KB	Output is correct
15	Correct	110 ms	8516 KB	Output is correct
16	Correct	112 ms	8624 KB	Output is correct
17	Correct	108 ms	8628 KB	Output is correct
18	Correct	1143 ms	78548 KB	Output is correct
19	Correct	1221 ms	78540 KB	Output is correct
20	Correct	1170 ms	78588 KB	Output is correct
21	Correct	116 ms	8588 KB	Output is correct
22	Correct	109 ms	8628 KB	Output is correct
23	Correct	366 ms	6136 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	113 ms	8356 KB	Output is correct
3	Correct	112 ms	8552 KB	Output is correct
4	Correct	1249 ms	78528 KB	Output is correct
5	Correct	151 ms	8604 KB	Output is correct
6	Correct	126 ms	8616 KB	Output is correct
7	Correct	122 ms	8556 KB	Output is correct
8	Correct	125 ms	8616 KB	Output is correct
9	Correct	152 ms	8608 KB	Output is correct
10	Correct	111 ms	8588 KB	Output is correct
11	Correct	109 ms	8612 KB	Output is correct
12	Correct	108 ms	8580 KB	Output is correct
13	Correct	108 ms	8640 KB	Output is correct
14	Correct	1131 ms	78588 KB	Output is correct
15	Correct	108 ms	8628 KB	Output is correct
16	Correct	1099 ms	78548 KB	Output is correct
17	Correct	1151 ms	78500 KB	Output is correct
18	Incorrect	1 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	12 ms	1232 KB	Output is correct
3	Correct	11 ms	1344 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	312 KB	Output is correct
8	Correct	1 ms	308 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 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	308 KB	Output is correct
16	Correct	11 ms	1364 KB	Output is correct
17	Correct	108 ms	8568 KB	Output is correct
18	Incorrect	0 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #806626

Compilation message