oj.uz

Submission #138685

# Submission time Handle Problem Language Result Execution time Memory
138685 2019-07-30T08:32:44 Z Angelos Strange Device (APIO19_strange_device) C++11
0 / 100
 285 ms 10332 KB 
#include <bits/stdc++.h>
#define MAXN 100100
#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 256 KB Output is correct
2 Correct 30 ms 1192 KB Output is correct
3 Correct 30 ms 1268 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 248 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 0 ms 376 KB Output is correct
10 Correct 2 ms 376 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 252 KB Output is correct
14 Correct 2 ms 292 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 30 ms 1240 KB Output is correct
17 Correct 284 ms 5588 KB Output is correct
18 Incorrect 2 ms 256 KB Output isn't correct

Subtask #2
0 / 5.0

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

Subtask #3
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 504 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Runtime error 189 ms 10332 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 283 ms 6848 KB Output is correct
3 Correct 285 ms 6904 KB Output is correct
4 Incorrect 279 ms 6688 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 30 ms 1192 KB Output is correct
3 Correct 30 ms 1268 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 248 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 0 ms 376 KB Output is correct
10 Correct 2 ms 376 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 252 KB Output is correct
14 Correct 2 ms 292 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 30 ms 1240 KB Output is correct
17 Correct 284 ms 5588 KB Output is correct
18 Incorrect 2 ms 256 KB Output isn't correct