oj.uz

Submission #138689

# Submission time Handle Problem Language Result Execution time Memory
138689 2019-07-30T08:34:19 Z Angelos Strange Device (APIO19_strange_device) C++11
35 / 100
 2914 ms 48168 KB 
#include <bits/stdc++.h>
#define MAXN 1001001
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair< pair<ll,ll> , pair<ll,ll> > ter;

vector < ter > vct;
int n;
ll A , B , D ,l[MAXN] , r[MAXN];

ll gcd(ll a , ll b){
    if(a > b) swap(a,b);

    if(a == 0) return b;
    return gcd(a , b%a);
}

int equall(pll a, pll b){
    if(a.x == b.x && a.y == b.y) return 2;
    if(a.x == b.x) return a.y > b.y;
    return a.x > b.x;
}

pll nxt(pll a){
    if(a.y == B-1 && a.x == D-1) return {0,0};
    if(a.y == B-1) return {a.x+1 , 0};

    return pll(a.x , a.y+1);
}

pll mx(pll a , pll b){
    if(a.x == b.x){
        if(a.y >b.y) return a;
        else return b;
    }
    else{
        if(a.x > b.x) return a;
        else return b;
    }
}

ll dist(pll a , pll b){
    ll u = a.x*B + a.y , v = b.x*B + b.y;

    if(v-u+1ll > 0) return (ll)v-u+1ll;
    return 0;
}

int main(){
    cin >> n >> A >> B;

    //cout << gcd(100000 , 3) << endl;

    ll D = A / gcd(A, B+1);

    for(int i=0; i<n; i++){
        cin >> l[i] >> r[i];

        ll a1 = l[i]/B , a2 = l[i]%B , b1 = r[i]/B , b2 = r[i]%B;

        if(r[i] - l[i] + 1 >= D*B) vct.push_back({{0,0} , {D-1,B-1}});
        else{
            a1 = a1%D , b1 = b1%D;
            if(a1 > b1 || (a1 == b1 && a2 > b2)){
                vct.push_back({{a1,a2} , {D-1,B-1}});
                vct.push_back({{0ll,0ll} , {b1,b2}});
            }
            else vct.push_back({{a1,a2} , {b1,b2}});
        }
    }

    sort(vct.begin() , vct.end());

    /*for(int i=0; i<vct.size(); i++){
        cout << vct[i].x.x << "," << vct[i].x.y << "," << vct[i].y.x << "," << vct[i].y.y << "  " ;
    }

    cout << endl;*/

    pll cur = pll(-1ll , -1ll);
    for(int i=0; i<vct.size(); i++){
        if(equall(cur , vct[i].first)){ ///0 greater is vct[i] , 1 greater is cur , 2 are eqial
            vct[i].first = nxt(cur);
        }
        cur = mx(vct[i].second , cur);
    }

    /*for(int i=0; i<vct.size(); i++){
        cout << vct[i].x.x << "," << vct[i].x.y << "," << vct[i].y.x << "," << vct[i].y.y << "  " ;
    }
    cout << endl;*/

    ll ans = 0;
    for(int i=0; i<vct.size(); i++){
        if(equall(vct[i].y , vct[i].x)) ans += dist(vct[i].first , vct[i].second);
    }



    cout << ans << endl;

    return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<vct.size(); i++){
                  ~^~~~~~~~~~~
strange_device.cpp:97:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<vct.size(); i++){
                  ~^~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 30 ms 1400 KB Output is correct
3 Correct 32 ms 1524 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 29 ms 1396 KB Output is correct
17 Correct 284 ms 6352 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct

Subtask #2
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 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 508 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 1980 ms 48168 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2736 ms 47788 KB Output is correct
3 Correct 2736 ms 47884 KB Output is correct
4 Correct 2741 ms 47772 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 2736 ms 47788 KB Output is correct
3 Correct 2736 ms 47884 KB Output is correct
4 Correct 2741 ms 47772 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2755 ms 47892 KB Output is correct
7 Correct 2705 ms 47936 KB Output is correct
8 Correct 2729 ms 47776 KB Output is correct
9 Correct 2808 ms 47748 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2736 ms 47788 KB Output is correct
3 Correct 2736 ms 47884 KB Output is correct
4 Correct 2741 ms 47772 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 268 ms 5860 KB Output is correct
7 Correct 279 ms 5952 KB Output is correct
8 Correct 275 ms 5992 KB Output is correct
9 Correct 273 ms 5828 KB Output is correct
10 Correct 273 ms 5824 KB Output is correct
11 Correct 277 ms 5916 KB Output is correct
12 Correct 272 ms 5860 KB Output is correct
13 Correct 281 ms 5856 KB Output is correct
14 Correct 274 ms 5864 KB Output is correct
15 Correct 282 ms 5992 KB Output is correct
16 Correct 282 ms 5968 KB Output is correct
17 Correct 276 ms 5988 KB Output is correct
18 Correct 2881 ms 47864 KB Output is correct
19 Correct 2808 ms 47740 KB Output is correct
20 Correct 2825 ms 47776 KB Output is correct
21 Correct 281 ms 6144 KB Output is correct
22 Correct 271 ms 5996 KB Output is correct
23 Correct 917 ms 22260 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 281 ms 5996 KB Output is correct
3 Correct 281 ms 6048 KB Output is correct
4 Correct 2914 ms 47856 KB Output is correct
5 Correct 283 ms 5912 KB Output is correct
6 Correct 283 ms 6044 KB Output is correct
7 Correct 282 ms 5992 KB Output is correct
8 Correct 307 ms 5884 KB Output is correct
9 Correct 281 ms 5836 KB Output is correct
10 Correct 281 ms 5860 KB Output is correct
11 Correct 282 ms 5860 KB Output is correct
12 Correct 276 ms 5892 KB Output is correct
13 Correct 283 ms 5928 KB Output is correct
14 Correct 2813 ms 47860 KB Output is correct
15 Correct 280 ms 5980 KB Output is correct
16 Correct 2743 ms 47960 KB Output is correct
17 Correct 2731 ms 48008 KB Output is correct
18 Incorrect 3 ms 376 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 30 ms 1400 KB Output is correct
3 Correct 32 ms 1524 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 29 ms 1396 KB Output is correct
17 Correct 284 ms 6352 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct