oj.uz

Submission #402064

# Submission time Handle Problem Language Result Execution time Memory
402064 2021-05-11T09:22:09 Z Blobo2_Blobo2 Strange Device (APIO19_strange_device) C++14
25 / 100
 575 ms 29616 KB 
/*
Editor: Abdelrahman Hossam
Nickname: Blobo2_Blobo2
IOI next year isA :)
*/

//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define all(v)  v.begin(),v.end()
#define gen(arr,n,nxt)  generate(arr,arr+n,nxt)
#define base ios_base::sync_with_stdio(false);cin.tie(0);

using namespace std;
const int mo=1e9+7;
int nxt(){int x;cin>>x;return x;}

signed main(){
    base
    int n=nxt(),a=nxt(),b=nxt();
    a/=__gcd(a,b+1);
    int x=a*b;
    vector<pair<int,int> >v;
    if(a!=x/b)
        x=1000000000000000001;
    bool flag=0;
    for(int i=0;i<n;i++){
        int first=nxt(),sec=nxt();
        if(sec-first+1==x)flag=1;
        else if(sec%x<first%x){
            first%=x;
            sec%=x;
            v.push_back({first,x-1});
            v.push_back({0,sec});
        }
        else v.push_back({first%x,sec%x});
    }
    if(flag){
        cout<<x<<endl;
        return 0;
    }
    sort(all(v));
    int cnt=0,now=-1;
    for(int i=0;i<v.size();i++){
        if(now==-1){
            now=v[i].second+1;
            cnt+=v[i].second-v[i].first+1;
        }
        else if(now>=v[i].second)
            continue;
        else if(now<v[i].first){
            cnt+=v[i].second-v[i].first+1;
            now=v[i].second+1;
        }
        else if(now>=v[i].first){
            cnt+=v[i].second-now+1;
            now=v[i].second+1;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

Compilation message

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

Subtask #1
0 / 10.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 364 ms 16848 KB Output is correct

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

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

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 54 ms 2400 KB Output is correct
3 Correct 62 ms 2448 KB Output is correct
4 Correct 575 ms 16800 KB Output is correct
5 Correct 48 ms 2368 KB Output is correct
6 Correct 53 ms 2452 KB Output is correct
7 Correct 59 ms 2500 KB Output is correct
8 Correct 60 ms 2436 KB Output is correct
9 Correct 50 ms 2516 KB Output is correct
10 Correct 49 ms 2424 KB Output is correct
11 Correct 50 ms 2456 KB Output is correct
12 Correct 45 ms 2484 KB Output is correct
13 Correct 50 ms 2404 KB Output is correct
14 Correct 525 ms 16908 KB Output is correct
15 Correct 49 ms 2496 KB Output is correct
16 Correct 483 ms 29616 KB Output is correct
17 Correct 482 ms 29596 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #8
0 / 30.0

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