oj.uz

Submission #729403

# Submission time Handle Problem Language Result Execution time Memory
729403 2023-04-24T03:34:09 Z 1075508020060209tc Strange Device (APIO19_strange_device) C++14
35 / 100
 1463 ms 69776 KB 
#include<bits/stdc++.h>

using namespace std;
#define int long long
int n;int A;int B;
int ar[1000006];int br[1000006];


map<pair<int,int>,int>vis;

signed main(){
cin>>n>>A>>B;
for(int i=1;i<=n;i++){
    cin>>ar[i]>>br[i];
}
A=B*A/__gcd(A,B+1);


vector<pair<int,int>>seg;
for(int i=1;i<=n;i++){
    if(br[i]-ar[i]+1>=A){
        cout<<A;return 0;
    }
    int l=ar[i]%A;int r=br[i]%A;
    if(r<l){
        seg.push_back({l,A-1});
        seg.push_back({0,r});
    }else{
        seg.push_back({l,r});
    }
}
sort(seg.begin(),seg.end());
int ans=0;
int rpl=seg[0].second;
int lpl=seg[0].first;
for(int i=1;i<seg.size();i++){

    if(seg[i].first<=rpl+1){
        rpl=max(rpl,seg[i].second);
        continue;
    }else{
        ans+=rpl-lpl+1;
        lpl=seg[i].first;rpl=seg[i].second;
    }
}
ans+=rpl-lpl+1;
cout<<ans<<endl;

}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:36:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 | for(int i=1;i<seg.size();i++){
      |             ~^~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 18 ms 1140 KB Output is correct
3 Correct 20 ms 1176 KB Output is correct
4 Correct 1 ms 308 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 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 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 0 ms 308 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 308 KB Output is correct
16 Correct 17 ms 1204 KB Output is correct
17 Correct 156 ms 5436 KB Output is correct
18 Incorrect 1 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 220 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 0 ms 308 KB Output is correct
5 Incorrect 1 ms 308 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 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 958 ms 32684 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 1336 ms 32524 KB Output is correct
3 Correct 1368 ms 32640 KB Output is correct
4 Correct 1392 ms 32824 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 1336 ms 32524 KB Output is correct
3 Correct 1368 ms 32640 KB Output is correct
4 Correct 1392 ms 32824 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1379 ms 32620 KB Output is correct
7 Correct 1463 ms 69564 KB Output is correct
8 Correct 1388 ms 69568 KB Output is correct
9 Correct 1378 ms 69744 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 1336 ms 32524 KB Output is correct
3 Correct 1368 ms 32640 KB Output is correct
4 Correct 1392 ms 32824 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 132 ms 7720 KB Output is correct
7 Correct 136 ms 7776 KB Output is correct
8 Correct 134 ms 7708 KB Output is correct
9 Correct 132 ms 7772 KB Output is correct
10 Correct 141 ms 7724 KB Output is correct
11 Correct 153 ms 7768 KB Output is correct
12 Correct 134 ms 7948 KB Output is correct
13 Correct 135 ms 7748 KB Output is correct
14 Correct 142 ms 7748 KB Output is correct
15 Correct 135 ms 7776 KB Output is correct
16 Correct 137 ms 7724 KB Output is correct
17 Correct 139 ms 7792 KB Output is correct
18 Correct 1364 ms 69620 KB Output is correct
19 Correct 1335 ms 69592 KB Output is correct
20 Correct 1398 ms 69532 KB Output is correct
21 Correct 138 ms 7728 KB Output is correct
22 Correct 131 ms 7688 KB Output is correct
23 Correct 424 ms 26552 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 137 ms 5416 KB Output is correct
3 Correct 135 ms 7756 KB Output is correct
4 Correct 1365 ms 69676 KB Output is correct
5 Correct 132 ms 7664 KB Output is correct
6 Correct 132 ms 7736 KB Output is correct
7 Correct 142 ms 7724 KB Output is correct
8 Correct 131 ms 7760 KB Output is correct
9 Correct 136 ms 7764 KB Output is correct
10 Correct 133 ms 7872 KB Output is correct
11 Correct 137 ms 7884 KB Output is correct
12 Correct 125 ms 7756 KB Output is correct
13 Correct 135 ms 7768 KB Output is correct
14 Correct 1314 ms 69776 KB Output is correct
15 Correct 133 ms 7676 KB Output is correct
16 Correct 1419 ms 69624 KB Output is correct
17 Correct 1404 ms 69604 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 1 ms 212 KB Output is correct
2 Correct 18 ms 1140 KB Output is correct
3 Correct 20 ms 1176 KB Output is correct
4 Correct 1 ms 308 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 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 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 0 ms 308 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 308 KB Output is correct
16 Correct 17 ms 1204 KB Output is correct
17 Correct 156 ms 5436 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -