oj.uz

Submission #782510

# Submission time Handle Problem Language Result Execution time Memory
782510 2023-07-14T03:40:04 Z andecaandeci Strange Device (APIO19_strange_device) C++17
5 / 100
 337 ms 16876 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define v          vector
#define int        unsigned long long
#define all(a)     (a).begin(), (a).end()
#define pb         push_back
#define mk         make_pair
#define pii        pair<int, int>
#define ff         first
#define ss         second
#define inp_v(vec) for (auto &i : vec) cin >> i;
#define prt_v(vec) for (auto i : vec) cout << i << endl;
#define MS(x)     memset(x, 0, sizeof(x))
#define gcd(a,b)   __gcd(a, b);
#define lcm(a,b)   (a*(b/gcd(a,b)))
#define lb         lower_bound
#define ub         upper_bound
bool chmin(int &a, int b){return b<a?a=b, true:false;}
bool chmax(int &a, int b){return b>a?a=b, true:false;}
// bool comp(const pair<int, int>&a, const pair<int int>&b){
//     return a.second<b.second;
// }
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int N, a, b;cin>>N>>a>>b;
    double cycles=a/(__gcd(a, b+1))*b;
    int cycle=(int)cycles;
    vector<pair<int, int>>segment;
    vector<pair<int, int>>seg;
    bool flag=false;
    for(int i=0;i<N;i++){
        int x, y;cin>>x>>y;
        if(y-x+1>=cycle){
            flag=true;
        }
        if(y>=cycle){
            // cout<<i<<" "<<x<<" "<<cycle<<" "<<y%cycle<<endl;
            if(x>=cycle){
                if(y/cycle>x/cycle){
                    segment.push_back({x%cycle, cycle-1});
                    segment.push_back({0, y%cycle});
                }
                else segment.push_back({x%cycle, y%cycle});
                // segment.push_back({0, y%cycle});
            }
            else{
                segment.push_back({x, cycle-1});
                segment.push_back({0, y%cycle});
            }
        }
        else{
            segment.push_back({x, y});
        }
    }
    sort(segment.begin(), segment.end());
    int curl=segment[0].first, curr=segment[1].second;
    int ans=curr-curl+1;
    // cout<<cycle<<endl;
    for(int i=1;i<segment.size();i++){
        // cout<<segment[i].first<<" "<<segment[i].second<<endl;
        if(curr>=segment[i].second){
            continue;
        }
        else{
            curl=max(curr+1, segment[i].first);
            curr=segment[i].second;
            ans+=curr-curl+1;
        }
    }
    if(flag)cout<<cycle<<endl;
    else cout<<ans<<endl;

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 6 ms 700 KB Output isn't correct
3 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 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 329 ms 16824 KB Output is correct
3 Correct 296 ms 16800 KB Output is correct
4 Correct 318 ms 16808 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 329 ms 16824 KB Output is correct
3 Correct 296 ms 16800 KB Output is correct
4 Correct 318 ms 16808 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 306 ms 16852 KB Output is correct
7 Correct 337 ms 16824 KB Output is correct
8 Correct 317 ms 16876 KB Output is correct
9 Incorrect 331 ms 16760 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 329 ms 16824 KB Output is correct
3 Correct 296 ms 16800 KB Output is correct
4 Correct 318 ms 16808 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 28 ms 2404 KB Output is correct
7 Correct 30 ms 2512 KB Output is correct
8 Correct 35 ms 2512 KB Output is correct
9 Correct 29 ms 2476 KB Output is correct
10 Correct 29 ms 2504 KB Output is correct
11 Correct 29 ms 2440 KB Output is correct
12 Correct 28 ms 2448 KB Output is correct
13 Incorrect 31 ms 2432 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 31 ms 2472 KB Output isn't correct
3 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 Incorrect 6 ms 700 KB Output isn't correct
3 Halted 0 ms 0 KB -