oj.uz

Submission #713512

# Submission time Handle Problem Language Result Execution time Memory
713512 2023-03-22T10:51:36 Z bin9638 Strange Device (APIO19_strange_device) C++17
10 / 100
 649 ms 39708 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define N 4000010
#define ii pair<int,int>
#define fs first
#define sc second
#define ld double
#define int ll

const int MAX_VAL=2e18;

int cnt[N],n,A,B,dem=0,ans=0;
vector<int>s;

void sub_AB()
{
    int res=0;
    for(int i=1;i<=n;i++)
    {
        int l,r;
        cin>>l>>r;
        res+=(r-l+1);
    }
    cout<<res;
    exit(0);
}

ii a[N];

int32_t main()
{
    #ifdef SKY
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    #endif // SKY
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>A>>B;
    if(MAX_VAL/A<=B)
        sub_AB();
    for(int i=1;i<=n;i++)
    {
        int l,r;
        cin>>l>>r;
        if(r-l+1>=A*B)
        {
            cout<<A*B;
            return 0;
        }
        int lef=l%(A*B),righ=r%(A*B);
        if(lef<=righ)
        {
            a[++dem]={lef,righ};
        }else
        {
            a[++dem]={lef,A*B-1};
            a[++dem]={0,righ};
        }
    }
    for(int i=1;i<=dem;i++)
    {
        s.pb(a[i].fs);
        s.pb(a[i].sc+1);
    }
    sort(s.begin(),s.end());
    s.erase(unique(s.begin(),s.end()),s.end());
    for(int i=1;i<=dem;i++)
    {
        cnt[lower_bound(s.begin(),s.end(),a[i].fs)-s.begin()]++;
        cnt[lower_bound(s.begin(),s.end(),a[i].sc+1)-s.begin()]--;
    }
    for(int i=0;i<s.size()-1;i++)
    {
        if(i>0)
            cnt[i]+=cnt[i-1];
        if(cnt[i]>0)
            ans+=(s[i+1]-s[i]);
    }
    cout<<ans;
    return 0;
}

Compilation message

strange_device.cpp: In function 'int32_t main()':
strange_device.cpp:77:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i=0;i<s.size()-1;i++)
      |                 ~^~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 5 ms 856 KB Output is correct
3 Correct 6 ms 856 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 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

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 352 KB Output is correct
5 Correct 286 ms 32548 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 530 ms 39624 KB Output is correct
3 Incorrect 522 ms 39708 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 530 ms 39624 KB Output is correct
3 Incorrect 522 ms 39708 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 530 ms 39624 KB Output is correct
3 Incorrect 522 ms 39708 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 57 ms 4368 KB Output is correct
3 Correct 58 ms 4288 KB Output is correct
4 Correct 649 ms 39692 KB Output is correct
5 Correct 57 ms 4360 KB Output is correct
6 Correct 60 ms 4316 KB Output is correct
7 Correct 59 ms 4360 KB Output is correct
8 Correct 72 ms 4256 KB Output is correct
9 Correct 79 ms 4292 KB Output is correct
10 Correct 66 ms 4316 KB Output is correct
11 Correct 60 ms 4364 KB Output is correct
12 Correct 54 ms 4340 KB Output is correct
13 Correct 62 ms 4368 KB Output is correct
14 Correct 628 ms 39640 KB Output is correct
15 Incorrect 58 ms 4364 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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