oj.uz

Submission #782495

# Submission time Handle Problem Language Result Execution time Memory
782495 2023-07-14T03:09:16 Z andecaandeci Strange Device (APIO19_strange_device) C++17
0 / 100
 346 ms 17640 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;
        }
    }
    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++){
      |                 ~^~~~~~~~~~~~~~~
strange_device.cpp:30:10: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
   30 |     bool flag=false;
      |          ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 844 KB Output is correct
3 Incorrect 4 ms 856 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 320 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 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 1 ms 212 KB Output is correct
2 Correct 292 ms 16776 KB Output is correct
3 Incorrect 289 ms 17640 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 292 ms 16776 KB Output is correct
3 Incorrect 289 ms 17640 KB Output isn't correct
4 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 292 ms 16776 KB Output is correct
3 Incorrect 289 ms 17640 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 2908 KB Output is correct
3 Correct 32 ms 2972 KB Output is correct
4 Correct 346 ms 17304 KB Output is correct
5 Correct 32 ms 3000 KB Output is correct
6 Correct 32 ms 2888 KB Output is correct
7 Correct 32 ms 2888 KB Output is correct
8 Correct 33 ms 2912 KB Output is correct
9 Correct 31 ms 2952 KB Output is correct
10 Correct 34 ms 2868 KB Output is correct
11 Correct 34 ms 2900 KB Output is correct
12 Incorrect 28 ms 2960 KB Output isn't correct
13 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 Correct 4 ms 844 KB Output is correct
3 Incorrect 4 ms 856 KB Output isn't correct
4 Halted 0 ms 0 KB -