oj.uz

Submission #582916

# Submission time Handle Problem Language Result Execution time Memory
582916 2022-06-24T15:07:11 Z groshi Strange Device (APIO19_strange_device) C++17
10 / 100
 564 ms 77752 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<queue>
using namespace std;
#define int long long
vector<pair<int,int> > Q,pom;
int32_t main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    long long n,a,b,x,y;
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++)
    {
        cin>>x>>y;
        Q.push_back({x,y});
    }
    sort(Q.begin(),Q.end());
    bool cale=0;
    if(1e18/a>=b)
        for(int i=0;i<Q.size();i++)
        {
            if(Q[i].second-Q[i].first+1>=a*b)
                cale=1;
        }
    else{
        int suma=0;
        for(int i=0;i<Q.size();i++)
            suma+=(Q[i].second-Q[i].first+1);
        cout<<suma;
        return 0;
    }
    if(cale==1)
    {
        cout<<a*b;
        return 0;
    }
    int cos=a*b;
    for(int i=0;i<Q.size();i++)
    {
        if(Q[i].second%cos>=Q[i].first%cos)
        pom.push_back({Q[i].first%cos,Q[i].second%cos});
        else{
            pom.push_back({Q[i].first%cos,cos-1});
            pom.push_back({0,Q[i].second%cos});
        }
    }
    sort(pom.begin(),pom.end());
    int wynik=0;
    int maxx=-1;
    maxx=pom[0].second;
    int pocz=pom[0].first;
    for(int i=1;i<pom.size();i++)
    {
        if(pom[i].first>maxx)
        {
            wynik+=maxx-pocz+1;
            pocz=pom[i].first;
            maxx=pom[i].second;
        }
        else maxx=max(maxx,pom[i].second);
    }
    wynik+=maxx-pocz+1;
    cout<<wynik;
    return 0;
}

Compilation message

strange_device.cpp: In function 'int32_t main()':
strange_device.cpp:25:22: 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]
   25 |         for(int i=0;i<Q.size();i++)
      |                     ~^~~~~~~~~
strange_device.cpp:32:22: 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]
   32 |         for(int i=0;i<Q.size();i++)
      |                     ~^~~~~~~~~
strange_device.cpp:43: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]
   43 |     for(int i=0;i<Q.size();i++)
      |                 ~^~~~~~~~~
strange_device.cpp:57: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]
   57 |     for(int i=1;i<pom.size();i++)
      |                 ~^~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 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 374 ms 65848 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 543 ms 77676 KB Output is correct
3 Incorrect 551 ms 77752 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 543 ms 77676 KB Output is correct
3 Incorrect 551 ms 77752 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 543 ms 77676 KB Output is correct
3 Incorrect 551 ms 77752 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 50 ms 8644 KB Output is correct
3 Correct 63 ms 8568 KB Output is correct
4 Correct 564 ms 77712 KB Output is correct
5 Correct 53 ms 8676 KB Output is correct
6 Correct 50 ms 8656 KB Output is correct
7 Correct 48 ms 8608 KB Output is correct
8 Correct 50 ms 8580 KB Output is correct
9 Correct 52 ms 8636 KB Output is correct
10 Correct 50 ms 8568 KB Output is correct
11 Correct 49 ms 8644 KB Output is correct
12 Correct 47 ms 8692 KB Output is correct
13 Correct 48 ms 8704 KB Output is correct
14 Correct 522 ms 77712 KB Output is correct
15 Incorrect 57 ms 8620 KB Output isn't correct
16 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 7 ms 1240 KB Output is correct
3 Correct 6 ms 1228 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -