oj.uz

Submission #782513

# Submission time Handle Problem Language Result Execution time Memory
782513 2023-07-14T03:43:35 Z christinelynn Strange Device (APIO19_strange_device) C++17
35 / 100
 348 ms 16932 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[0].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 Correct 3 ms 600 KB Output is correct
3 Correct 5 ms 620 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 3 ms 600 KB Output is correct
17 Correct 32 ms 2512 KB Output is correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 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 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 201 ms 16780 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 312 ms 16856 KB Output is correct
3 Correct 289 ms 16816 KB Output is correct
4 Correct 280 ms 16756 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 312 ms 16856 KB Output is correct
3 Correct 289 ms 16816 KB Output is correct
4 Correct 280 ms 16756 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 289 ms 16820 KB Output is correct
7 Correct 294 ms 16812 KB Output is correct
8 Correct 286 ms 16776 KB Output is correct
9 Correct 311 ms 16788 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 312 ms 16856 KB Output is correct
3 Correct 289 ms 16816 KB Output is correct
4 Correct 280 ms 16756 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 32 ms 2512 KB Output is correct
7 Correct 30 ms 2512 KB Output is correct
8 Correct 28 ms 2464 KB Output is correct
9 Correct 34 ms 2504 KB Output is correct
10 Correct 28 ms 2512 KB Output is correct
11 Correct 29 ms 2512 KB Output is correct
12 Correct 33 ms 2448 KB Output is correct
13 Correct 30 ms 2484 KB Output is correct
14 Correct 28 ms 2456 KB Output is correct
15 Correct 35 ms 2444 KB Output is correct
16 Correct 34 ms 2492 KB Output is correct
17 Correct 29 ms 2512 KB Output is correct
18 Correct 298 ms 16800 KB Output is correct
19 Correct 286 ms 16812 KB Output is correct
20 Correct 323 ms 16932 KB Output is correct
21 Correct 31 ms 2512 KB Output is correct
22 Correct 26 ms 2500 KB Output is correct
23 Correct 87 ms 8552 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 31 ms 2512 KB Output is correct
3 Correct 31 ms 2456 KB Output is correct
4 Correct 348 ms 16820 KB Output is correct
5 Correct 30 ms 2512 KB Output is correct
6 Correct 30 ms 2512 KB Output is correct
7 Correct 30 ms 2512 KB Output is correct
8 Correct 35 ms 2504 KB Output is correct
9 Correct 31 ms 2500 KB Output is correct
10 Correct 30 ms 2512 KB Output is correct
11 Correct 31 ms 2512 KB Output is correct
12 Correct 28 ms 2432 KB Output is correct
13 Correct 31 ms 2412 KB Output is correct
14 Correct 321 ms 16840 KB Output is correct
15 Correct 31 ms 2512 KB Output is correct
16 Correct 297 ms 16740 KB Output is correct
17 Correct 285 ms 16832 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 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 3 ms 600 KB Output is correct
3 Correct 5 ms 620 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 3 ms 600 KB Output is correct
17 Correct 32 ms 2512 KB Output is correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -