oj.uz

Submission #475910

# Submission time Handle Problem Language Result Execution time Memory
475910 2021-09-24T12:48:45 Z mat_v Strange Device (APIO19_strange_device) C++14
35 / 100
 755 ms 86164 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<ll,ll>


using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


int n;
ll a,b;
ll brt;
pii niz[1000005];
vector<pii> svi;

void ddj(ll x, ll y){
    svi.pb({x,0});
    svi.pb({y,1});
}

int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> a >> b;
    ll uk = 0;
    ff(i,1,n){
        cin >> niz[i].xx >> niz[i].yy;
        uk += (niz[i].yy - niz[i].xx);
    }
    ll tmp = __gcd(b + 1, a);
    tmp = a / tmp;
    ll sta = LLONG_MAX;
    bool flg = 0;
    if(tmp >= sta/b){
        cout << uk << "\n";
        return 0;
    }
    brt = tmp*b;
    ff(i,1,n){
        if((niz[i].yy - niz[i].xx +1) >= brt){
            cout << brt << "\n";
            return 0;
        }
        if((niz[i].yy%brt) < (niz[i].xx%brt)){
            ddj(niz[i].xx%brt, brt - 1);
            ddj(0, niz[i].yy%brt);
        }
        else ddj(niz[i].xx%brt, niz[i].yy%brt);
    }
    sort(svi.begin(), svi.end());
    int op = 0;
    ll last = -1;
    ll ans = brt;
    for(auto c:svi){

        if(c.yy == 1){
            op--;
            last = c.xx;
            continue;
        }
        else{
            if(op == 0){
                ans -= (c.xx - last);
                ans++;
            }
            last = c.xx;
            op++;
        }
    }
    ans -= (brt - last);
    ans++;
    cout << ans << "\n";



    return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
strange_device.cpp:40:5: note: in expansion of macro 'ff'
   40 |     ff(i,1,n){
      |     ^~
strange_device.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
strange_device.cpp:53:5: note: in expansion of macro 'ff'
   53 |     ff(i,1,n){
      |     ^~
strange_device.cpp:47:10: warning: unused variable 'flg' [-Wunused-variable]
   47 |     bool flg = 0;
      |          ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 6 ms 1488 KB Output is correct
3 Correct 6 ms 1616 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 6 ms 1488 KB Output is correct
17 Correct 71 ms 9816 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 332 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 0 ms 204 KB Output isn't correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 456 ms 74360 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 601 ms 59368 KB Output is correct
3 Correct 588 ms 86136 KB Output is correct
4 Correct 631 ms 86144 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 601 ms 59368 KB Output is correct
3 Correct 588 ms 86136 KB Output is correct
4 Correct 631 ms 86144 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 662 ms 86068 KB Output is correct
7 Correct 604 ms 86060 KB Output is correct
8 Correct 576 ms 86124 KB Output is correct
9 Correct 728 ms 86060 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 601 ms 59368 KB Output is correct
3 Correct 588 ms 86136 KB Output is correct
4 Correct 631 ms 86144 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 54 ms 9836 KB Output is correct
7 Correct 62 ms 9788 KB Output is correct
8 Correct 67 ms 9856 KB Output is correct
9 Correct 59 ms 9788 KB Output is correct
10 Correct 56 ms 9856 KB Output is correct
11 Correct 57 ms 9816 KB Output is correct
12 Correct 52 ms 9764 KB Output is correct
13 Correct 81 ms 9808 KB Output is correct
14 Correct 69 ms 9752 KB Output is correct
15 Correct 62 ms 9812 KB Output is correct
16 Correct 60 ms 9772 KB Output is correct
17 Correct 58 ms 9796 KB Output is correct
18 Correct 623 ms 86072 KB Output is correct
19 Correct 649 ms 86052 KB Output is correct
20 Correct 690 ms 86064 KB Output is correct
21 Correct 63 ms 9788 KB Output is correct
22 Correct 56 ms 9824 KB Output is correct
23 Correct 167 ms 34808 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 60 ms 9808 KB Output is correct
3 Correct 62 ms 9788 KB Output is correct
4 Correct 755 ms 86052 KB Output is correct
5 Correct 60 ms 9792 KB Output is correct
6 Correct 63 ms 9796 KB Output is correct
7 Correct 60 ms 9764 KB Output is correct
8 Correct 68 ms 9788 KB Output is correct
9 Correct 59 ms 9796 KB Output is correct
10 Correct 61 ms 9820 KB Output is correct
11 Correct 63 ms 9912 KB Output is correct
12 Correct 56 ms 9788 KB Output is correct
13 Correct 86 ms 9760 KB Output is correct
14 Correct 673 ms 86164 KB Output is correct
15 Correct 63 ms 9800 KB Output is correct
16 Correct 538 ms 86068 KB Output is correct
17 Correct 581 ms 86112 KB Output is correct
18 Incorrect 1 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 6 ms 1488 KB Output is correct
3 Correct 6 ms 1616 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 6 ms 1488 KB Output is correct
17 Correct 71 ms 9816 KB Output is correct
18 Incorrect 1 ms 204 KB Output isn't correct