oj.uz

Submission #142676

# Submission time Handle Problem Language Result Execution time Memory
142676 2019-08-10T12:24:24 Z Bodo171 Strange Device (APIO19_strange_device) C++14
15 / 100
 1487 ms 63656 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)
{
    if(unu.x==doi.x) return unu.y<doi.y;
    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)
{
    it=s.lower_bound({st,0});
    while(it!=s.end()&&(*it).x<=dr)
    {
        dr=max(dr,(*it).y);
        it1=it;it1++;s.erase(it);
        it=it1;
    }
    it=s.lower_bound({st,0});
    if(it!=s.begin())
    {
        it--;
        if((*it).y>=st)
        {
            st=min(st,(*it).x);
            s.erase(it);
        }
    }
    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 376 KB Output is correct
2 Incorrect 12 ms 1144 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 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 296 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 348 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 392 KB Output is correct
2 Incorrect 3 ms 380 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 376 KB Output is correct
2 Correct 1281 ms 63016 KB Output is correct
3 Correct 1334 ms 63516 KB Output is correct
4 Correct 1422 ms 63656 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1281 ms 63016 KB Output is correct
3 Correct 1334 ms 63516 KB Output is correct
4 Correct 1422 ms 63656 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 1306 ms 63288 KB Output is correct
7 Correct 1384 ms 63548 KB Output is correct
8 Correct 1314 ms 63476 KB Output is correct
9 Correct 1471 ms 63392 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1281 ms 63016 KB Output is correct
3 Correct 1334 ms 63516 KB Output is correct
4 Correct 1422 ms 63656 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 104 ms 7128 KB Output is correct
7 Correct 104 ms 6904 KB Output is correct
8 Correct 112 ms 6980 KB Output is correct
9 Correct 121 ms 6904 KB Output is correct
10 Correct 105 ms 6904 KB Output is correct
11 Correct 110 ms 6904 KB Output is correct
12 Correct 109 ms 6904 KB Output is correct
13 Correct 131 ms 6972 KB Output is correct
14 Correct 114 ms 7032 KB Output is correct
15 Correct 154 ms 7004 KB Output is correct
16 Incorrect 127 ms 7768 KB Output isn't correct
17 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 129 ms 6884 KB Output is correct
3 Correct 153 ms 6904 KB Output is correct
4 Correct 1487 ms 63436 KB Output is correct
5 Correct 129 ms 7204 KB Output is correct
6 Correct 130 ms 7272 KB Output is correct
7 Correct 131 ms 7264 KB Output is correct
8 Correct 134 ms 7292 KB Output is correct
9 Correct 128 ms 7208 KB Output is correct
10 Correct 112 ms 7200 KB Output is correct
11 Correct 116 ms 7264 KB Output is correct
12 Correct 118 ms 7228 KB Output is correct
13 Correct 128 ms 7388 KB Output is correct
14 Correct 1467 ms 63508 KB Output is correct
15 Incorrect 107 ms 8312 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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