oj.uz

Submission #142674

# Submission time Handle Problem Language Result Execution time Memory
142674 2019-08-10T12:10:52 Z Bodo171 Strange Device (APIO19_strange_device) C++14
15 / 100
 1279 ms 64564 KB 
#include <iostream>
#include <set>
#include <fstream>
using namespace std;
const long long lim=(long long)(1LL*1e18)+1;
long long n,i,j,l,r,A,B,L,R;
long long ans;
bool brk;
struct pct
{
    long long x,y;
}nl;
bool operator <(pct unu,pct doi)
{
    return unu.x<doi.x;
}
bool operator !=(pct unu,pct doi)
{
    return (unu.x!=doi.x||unu.y!=doi.y);
}
set <pct> s;
set <pct>::iterator it,it1;
long long gcd(long long x,long long y)
{
    if((!x)||(!y)) return (x+y);
    return gcd(y,x%y);
}
void baga(long long st,long long dr)
{
    pct S=nl,D=nl;
    it=s.lower_bound({st,dr});
    if(it!=s.end()&&(*it).x<=dr)
    {
        D=(*it);
        dr=D.y;
    }
    if(it!=s.begin())
    {
        it--;
        if((*it).y>=st)
        {
            S=(*it);
            st=S.x;
        }
    }
    if(S!=nl) s.erase(S);
    if(D!=nl) s.erase(D);
    s.insert({st,dr});
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>A>>B;
    long long t=gcd(A,B+1);
    A/=t;
    long long per;
    if(lim/A<=B) per=1LL*lim;
    else per=1LL*A*B;
    for(i=1;i<=n;i++)
    {
        cin>>l>>r;
        if(l/per==r/per)
        {
            baga(l%per,r%per);
        }
        else
        {
            if(l/per+1<r/per)
                baga(0,per-1);
            baga(l%per,per-1);
            baga(0,r%per);
        }
    }
    for(it=s.begin();it!=s.end();it++)
    {
        ans+=1LL*((*it).y-(*it).x+1);
    }
    cout<<ans;
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 352 KB Output is correct
2 Incorrect 10 ms 888 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #3
0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 1128 ms 63448 KB Output is correct
3 Correct 1177 ms 64564 KB Output is correct
4 Correct 1218 ms 64440 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 1128 ms 63448 KB Output is correct
3 Correct 1177 ms 64564 KB Output is correct
4 Correct 1218 ms 64440 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 1158 ms 64032 KB Output is correct
7 Correct 1183 ms 63936 KB Output is correct
8 Correct 1151 ms 63864 KB Output is correct
9 Correct 1263 ms 64084 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 1128 ms 63448 KB Output is correct
3 Correct 1177 ms 64564 KB Output is correct
4 Correct 1218 ms 64440 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 94 ms 7928 KB Output is correct
7 Correct 98 ms 7580 KB Output is correct
8 Correct 100 ms 7572 KB Output is correct
9 Correct 110 ms 7592 KB Output is correct
10 Correct 95 ms 7444 KB Output is correct
11 Correct 95 ms 7544 KB Output is correct
12 Correct 99 ms 7516 KB Output is correct
13 Correct 111 ms 7416 KB Output is correct
14 Correct 93 ms 7544 KB Output is correct
15 Incorrect 113 ms 7416 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 109 ms 8312 KB Output is correct
3 Correct 113 ms 7672 KB Output is correct
4 Correct 1212 ms 63972 KB Output is correct
5 Correct 114 ms 7888 KB Output is correct
6 Correct 115 ms 7848 KB Output is correct
7 Correct 116 ms 7596 KB Output is correct
8 Correct 114 ms 7468 KB Output is correct
9 Correct 110 ms 7440 KB Output is correct
10 Correct 101 ms 7496 KB Output is correct
11 Correct 105 ms 7416 KB Output is correct
12 Correct 108 ms 7464 KB Output is correct
13 Correct 115 ms 7444 KB Output is correct
14 Incorrect 1279 ms 63976 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 352 KB Output is correct
2 Incorrect 10 ms 888 KB Output isn't correct
3 Halted 0 ms 0 KB -