oj.uz

Submission #713511

# Submission time Handle Problem Language Result Execution time Memory
713511 2023-03-22T10:50:24 Z bin9638 Strange Device (APIO19_strange_device) C++17
5 / 100
 5000 ms 39592 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define N 2000010
#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()
{
    while(1);
    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:78: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]
   78 |     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 6 ms 856 KB Output is correct
3 Correct 6 ms 856 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 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 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Execution timed out 5025 ms 212 KB Time limit exceeded
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 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 307 ms 32556 KB Output is correct

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 560 ms 39504 KB Output is correct
3 Incorrect 549 ms 39504 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 4288 KB Output is correct
3 Correct 63 ms 4296 KB Output is correct
4 Correct 668 ms 39592 KB Output is correct
5 Correct 57 ms 4252 KB Output is correct
6 Correct 58 ms 4360 KB Output is correct
7 Correct 57 ms 4312 KB Output is correct
8 Correct 64 ms 4324 KB Output is correct
9 Correct 76 ms 4332 KB Output is correct
10 Correct 63 ms 4256 KB Output is correct
11 Correct 58 ms 4356 KB Output is correct
12 Correct 57 ms 4296 KB Output is correct
13 Correct 60 ms 4288 KB Output is correct
14 Correct 611 ms 39516 KB Output is correct
15 Incorrect 61 ms 4296 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 6 ms 856 KB Output is correct
3 Correct 6 ms 856 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -