oj.uz

Submission #131676

# Submission time Handle Problem Language Result Execution time Memory
131676 2019-07-17T12:34:16 Z Swan Strange Device (APIO19_strange_device) C++14
35 / 100
 693 ms 19432 KB 
#include <bits/stdc++.h>
#define stop system("pause")
#define INP freopen("inpute.in","r",stdin)
#define OUTP freopen("promote.out","w",stdout)
#define double long double
#define int long long

using namespace std;

bool check(int x){
    return x != -1;
}


main()
{
    ios_base::sync_with_stdio(0);
    int n,a,b; cin >> n >> a >> b;
    double kek = a*b/__gcd(a,b+1);
    int lcm;
    if(kek >= 1e18+228)lcm = 1e18+228;
    else lcm = a*b/__gcd(a,b+1);
    vector<pair<int,int> > v;
    int res = 0;
    for(int i(0); i < n;i++){
        int l,r; cin >> l >> r;
        l%=lcm;
        r%=lcm;
        if(l <= r)v.push_back({l,r});
        else{
            if(check(lcm-1))v.push_back({l,lcm-1});
            v.push_back({0,r});
        }
    }
    sort(v.begin(),v.end());
    int ans = 0;
    int lastx,lasty; lastx = lasty = -1;
    for(int i(0); i < v.size();i++){
        int nx,ny;
        nx = max(lasty+1,v[i].first);
        ny = max(lasty,v[i].second);
        if(nx >= lcm || nx > ny)continue;
        ans+=ny-nx+1;
        lastx = nx;
        lasty = ny;
    }
    cout << ans;
    return 0;
}
/*
3 1000000000000000000 1
2 15
55 123
324 2512
*/

Compilation message

strange_device.cpp:15:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
strange_device.cpp: In function 'int main()':
strange_device.cpp:38:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < v.size();i++){
                   ~~^~~~~~~~~~
strange_device.cpp:24:9: warning: unused variable 'res' [-Wunused-variable]
     int res = 0;
         ^~~
strange_device.cpp:37:9: warning: variable 'lastx' set but not used [-Wunused-but-set-variable]
     int lastx,lasty; lastx = lasty = -1;
         ^~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 8 ms 888 KB Output is correct
3 Correct 8 ms 992 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 296 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 8 ms 888 KB Output is correct
17 Correct 64 ms 2700 KB Output is correct
18 Incorrect 1 ms 376 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 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 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 464 ms 19432 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 621 ms 17780 KB Output is correct
3 Correct 617 ms 17944 KB Output is correct
4 Correct 627 ms 18008 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 621 ms 17780 KB Output is correct
3 Correct 617 ms 17944 KB Output is correct
4 Correct 627 ms 18008 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 618 ms 17996 KB Output is correct
7 Correct 615 ms 17968 KB Output is correct
8 Correct 612 ms 18088 KB Output is correct
9 Correct 675 ms 18000 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 621 ms 17780 KB Output is correct
3 Correct 617 ms 17944 KB Output is correct
4 Correct 627 ms 18008 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 62 ms 5252 KB Output is correct
7 Correct 66 ms 5232 KB Output is correct
8 Correct 62 ms 5252 KB Output is correct
9 Correct 65 ms 5244 KB Output is correct
10 Correct 63 ms 5232 KB Output is correct
11 Correct 65 ms 5160 KB Output is correct
12 Correct 65 ms 5212 KB Output is correct
13 Correct 68 ms 5232 KB Output is correct
14 Correct 64 ms 5228 KB Output is correct
15 Correct 69 ms 5608 KB Output is correct
16 Correct 68 ms 5736 KB Output is correct
17 Correct 67 ms 5608 KB Output is correct
18 Correct 618 ms 18040 KB Output is correct
19 Correct 608 ms 18124 KB Output is correct
20 Correct 674 ms 18056 KB Output is correct
21 Correct 67 ms 5352 KB Output is correct
22 Correct 61 ms 5236 KB Output is correct
23 Correct 198 ms 14388 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 66 ms 3304 KB Output is correct
3 Correct 68 ms 5480 KB Output is correct
4 Correct 693 ms 17912 KB Output is correct
5 Correct 69 ms 5092 KB Output is correct
6 Correct 70 ms 5096 KB Output is correct
7 Correct 68 ms 4972 KB Output is correct
8 Correct 70 ms 4944 KB Output is correct
9 Correct 69 ms 4976 KB Output is correct
10 Correct 69 ms 4944 KB Output is correct
11 Correct 69 ms 5352 KB Output is correct
12 Correct 63 ms 5196 KB Output is correct
13 Correct 64 ms 5220 KB Output is correct
14 Correct 669 ms 18008 KB Output is correct
15 Correct 66 ms 5708 KB Output is correct
16 Correct 610 ms 18008 KB Output is correct
17 Correct 606 ms 18004 KB Output is correct
18 Incorrect 2 ms 256 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 8 ms 888 KB Output is correct
3 Correct 8 ms 992 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 296 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 8 ms 888 KB Output is correct
17 Correct 64 ms 2700 KB Output is correct
18 Incorrect 1 ms 376 KB Output isn't correct