oj.uz

Submission #131675

# Submission time Handle Problem Language Result Execution time Memory
131675 2019-07-17T12:33:42 Z Swan Strange Device (APIO19_strange_device) C++14
0 / 100
 5000 ms 78632 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;
}

map<int,int> qwe;

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;
        for(int j(l); j <=r;j++){
            if(qwe.count(j%lcm) == 0)res++;
            qwe[i%lcm]++;
        }
        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:16:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
strange_device.cpp: In function 'int main()':
strange_device.cpp:43:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < v.size();i++){
                   ~~^~~~~~~~~~
strange_device.cpp:42: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 2 ms 376 KB Output is correct
2 Correct 30 ms 1400 KB Output is correct
3 Correct 45 ms 1404 KB Output is correct
4 Correct 3 ms 252 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 504 KB Output is correct
9 Correct 4 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 276 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 11 ms 424 KB Output is correct
16 Correct 26 ms 1324 KB Output is correct
17 Correct 121 ms 8676 KB Output is correct
18 Incorrect 2 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 Execution timed out 5029 ms 376 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 27 ms 568 KB Output is correct
3 Correct 27 ms 528 KB Output is correct
4 Correct 28 ms 500 KB Output is correct
5 Execution timed out 5002 ms 404 KB Time limit exceeded

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1303 ms 78632 KB Output is correct
3 Execution timed out 5022 ms 772 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1303 ms 78632 KB Output is correct
3 Execution timed out 5022 ms 772 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1303 ms 78632 KB Output is correct
3 Execution timed out 5022 ms 772 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4096 ms 10244 KB Output is correct
3 Execution timed out 5095 ms 384 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 30 ms 1400 KB Output is correct
3 Correct 45 ms 1404 KB Output is correct
4 Correct 3 ms 252 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 504 KB Output is correct
9 Correct 4 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 276 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 11 ms 424 KB Output is correct
16 Correct 26 ms 1324 KB Output is correct
17 Correct 121 ms 8676 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct