oj.uz

Submission #713515

# Submission time Handle Problem Language Result Execution time Memory
713515 2023-03-22T10:56:34 Z bin9638 Strange Device (APIO19_strange_device) C++17
10 / 100
 707 ms 39620 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 8 ms 856 KB Output is correct
3 Correct 6 ms 884 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 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 302 ms 32520 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 563 ms 39608 KB Output is correct
3 Incorrect 600 ms 39572 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 384 KB Output is correct
2 Correct 563 ms 39608 KB Output is correct
3 Incorrect 600 ms 39572 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 384 KB Output is correct
2 Correct 563 ms 39608 KB Output is correct
3 Incorrect 600 ms 39572 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 340 KB Output is correct
2 Correct 68 ms 4316 KB Output is correct
3 Correct 82 ms 4312 KB Output is correct
4 Correct 707 ms 39620 KB Output is correct
5 Correct 72 ms 4292 KB Output is correct
6 Correct 58 ms 4256 KB Output is correct
7 Correct 59 ms 4308 KB Output is correct
8 Correct 61 ms 4264 KB Output is correct
9 Correct 58 ms 4372 KB Output is correct
10 Correct 80 ms 4284 KB Output is correct
11 Correct 57 ms 4264 KB Output is correct
12 Correct 51 ms 4364 KB Output is correct
13 Correct 60 ms 4316 KB Output is correct
14 Correct 599 ms 39584 KB Output is correct
15 Incorrect 58 ms 4368 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 8 ms 856 KB Output is correct
3 Correct 6 ms 884 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -