oj.uz

Submission #782498

# Submission time Handle Problem Language Result Execution time Memory
782498 2023-07-14T03:10:34 Z makanhulia Strange Device (APIO19_strange_device) C++17
0 / 100
 347 ms 16868 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define v          vector
#define int        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;
    int cycle=a*b/(__gcd(a, b+1));
    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>=cycle){
            flag=true;
        }
        if(y>=cycle){
            // cout<<i<<" "<<x<<" "<<cycle<<" "<<y%cycle<<endl;
            if(x>=cycle){
                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=-1, curr=-1;
    int ans=0;
    // cout<<cycle<<endl;
    for(int i=0;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;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:55:18: 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]
   55 |     for(int i=0;i<segment.size();i++){
      |                 ~^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 5.0

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

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 305 ms 16868 KB Output is correct
3 Incorrect 295 ms 16788 KB Output isn't correct
4 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 Correct 32 ms 2520 KB Output is correct
3 Correct 37 ms 2552 KB Output is correct
4 Correct 347 ms 16852 KB Output is correct
5 Correct 32 ms 2512 KB Output is correct
6 Correct 42 ms 2412 KB Output is correct
7 Correct 32 ms 2420 KB Output is correct
8 Correct 40 ms 2376 KB Output is correct
9 Correct 31 ms 2500 KB Output is correct
10 Correct 32 ms 2504 KB Output is correct
11 Correct 31 ms 2476 KB Output is correct
12 Incorrect 28 ms 2428 KB Output isn't correct
13 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 3 ms 600 KB Output is correct
3 Incorrect 3 ms 600 KB Output isn't correct
4 Halted 0 ms 0 KB -