oj.uz

Submission #440422

# Submission time Handle Problem Language Result Execution time Memory
440422 2021-07-02T09:06:08 Z DJeniUp Strange Device (APIO19_strange_device) C++17
35 / 100
 1827 ms 63192 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll>pairll;
typedef pair<ll,pairll>pairlll;
typedef pair<pairll,pairll>pairllll;
typedef long double ld;
typedef pair<ll,string>pairls;

#define INF 1000000000000007
#define pb push_back
#define fr first
#define sc second

ll n,a,b,m,g;

struct D{
    ll x,y;
}d[1000007],t[4000007];

bool mcp(D d1, D d2){
    return d1.x<d2.x;
}

int main()
{
    cin>>n>>a>>b;
    ll k=__gcd(a,b+1);
    k=a/k;
    k*=b;
    for(int i=1;i<=n;i++){
        cin>>d[i].x>>d[i].y;
        d[i].y++;
        if(d[i].y-d[i].x>=k){
            m++;
            t[m]={0,1};
            m++;
            t[m]={k,-1};
        }else{
            d[i].x%=k;
            d[i].y%=k;
            m++;
            if(d[i].x<=d[i].y){
                m++;
                t[m]={d[i].x,1};
                m++;
                t[m]={d[i].y,-1};
            }else{
                m++;
                t[m]={d[i].x,1};
                m++;
                t[m]={d[i].y,-1};
                m++;
                t[m]={0,1};
                m++;
                t[m]={k,-1};
            }
        }
    }

    m++;
    t[m].x=k;
    sort(t+1,t+1+m,mcp);
    ll r=0;
    ll h=0;
    t[0].x=0;
    for(int i=1;i<=m;i++){
        if(h>0){
            r+=(t[i].x-t[i-1].x);
        }
        h+=(t[i].y);
    }
    cout<<r<<endl;

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 17 ms 844 KB Output is correct
3 Correct 19 ms 844 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 17 ms 856 KB Output is correct
17 Correct 173 ms 6664 KB Output is correct
18 Incorrect 1 ms 204 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 1 ms 204 KB Output isn't correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1236 ms 62872 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1753 ms 62932 KB Output is correct
3 Correct 1783 ms 62908 KB Output is correct
4 Correct 1714 ms 62980 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1753 ms 62932 KB Output is correct
3 Correct 1783 ms 62908 KB Output is correct
4 Correct 1714 ms 62980 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1703 ms 62896 KB Output is correct
7 Correct 1688 ms 63192 KB Output is correct
8 Correct 1737 ms 62812 KB Output is correct
9 Correct 1672 ms 62868 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1753 ms 62932 KB Output is correct
3 Correct 1783 ms 62908 KB Output is correct
4 Correct 1714 ms 62980 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 168 ms 6516 KB Output is correct
7 Correct 163 ms 6468 KB Output is correct
8 Correct 169 ms 6508 KB Output is correct
9 Correct 170 ms 6556 KB Output is correct
10 Correct 204 ms 6468 KB Output is correct
11 Correct 172 ms 6548 KB Output is correct
12 Correct 214 ms 6452 KB Output is correct
13 Correct 167 ms 6552 KB Output is correct
14 Correct 172 ms 6512 KB Output is correct
15 Correct 163 ms 6468 KB Output is correct
16 Correct 167 ms 6468 KB Output is correct
17 Correct 235 ms 6540 KB Output is correct
18 Correct 1827 ms 62944 KB Output is correct
19 Correct 1812 ms 62904 KB Output is correct
20 Correct 1750 ms 62908 KB Output is correct
21 Correct 170 ms 6468 KB Output is correct
22 Correct 192 ms 6440 KB Output is correct
23 Correct 567 ms 21536 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 193 ms 6556 KB Output is correct
3 Correct 168 ms 6548 KB Output is correct
4 Correct 1708 ms 62968 KB Output is correct
5 Correct 164 ms 6536 KB Output is correct
6 Correct 165 ms 6468 KB Output is correct
7 Correct 164 ms 6596 KB Output is correct
8 Correct 165 ms 6580 KB Output is correct
9 Correct 170 ms 6612 KB Output is correct
10 Correct 170 ms 6560 KB Output is correct
11 Correct 168 ms 6556 KB Output is correct
12 Correct 160 ms 6468 KB Output is correct
13 Correct 164 ms 6596 KB Output is correct
14 Correct 1723 ms 63088 KB Output is correct
15 Correct 172 ms 6468 KB Output is correct
16 Correct 1726 ms 63004 KB Output is correct
17 Correct 1711 ms 62972 KB Output is correct
18 Incorrect 0 ms 204 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 17 ms 844 KB Output is correct
3 Correct 19 ms 844 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 17 ms 856 KB Output is correct
17 Correct 173 ms 6664 KB Output is correct
18 Incorrect 1 ms 204 KB Output isn't correct