oj.uz

Submission #782511

# Submission time Handle Problem Language Result Execution time Memory
782511 2023-07-14T03:41:15 Z makanhulia Strange Device (APIO19_strange_device) C++17
5 / 100
 335 ms 16824 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;
    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;
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 5 ms 600 KB Output isn't correct
3 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 0 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 0 ms 212 KB Output is correct
2 Correct 335 ms 16812 KB Output is correct
3 Correct 303 ms 16772 KB Output is correct
4 Correct 289 ms 16796 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 335 ms 16812 KB Output is correct
3 Correct 303 ms 16772 KB Output is correct
4 Correct 289 ms 16796 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 302 ms 16776 KB Output is correct
7 Correct 304 ms 16772 KB Output is correct
8 Correct 294 ms 16824 KB Output is correct
9 Incorrect 324 ms 16792 KB Output isn't correct
10 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 335 ms 16812 KB Output is correct
3 Correct 303 ms 16772 KB Output is correct
4 Correct 289 ms 16796 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 28 ms 2516 KB Output is correct
7 Correct 31 ms 2512 KB Output is correct
8 Correct 28 ms 2452 KB Output is correct
9 Correct 30 ms 2512 KB Output is correct
10 Correct 28 ms 2444 KB Output is correct
11 Correct 30 ms 2412 KB Output is correct
12 Correct 33 ms 2408 KB Output is correct
13 Incorrect 31 ms 2448 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 2512 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 5 ms 600 KB Output isn't correct
3 Halted 0 ms 0 KB -