oj.uz

Submission #785873

# Submission time Handle Problem Language Result Execution time Memory
785873 2023-07-17T17:28:45 Z aykhn Strange Device (APIO19_strange_device) C++14
35 / 100
 1220 ms 66304 KB 
#include <bits/stdc++.h>

// author: aykhn

using namespace std;

typedef long long ll;

#define TC int t; cin >> t; while (t--) _();
#define OPT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define mpr make_pair
#define eb emplace_back
#define new int32_t
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define int ll
#define ins insert
#define inf 0x3F3F3F3F
#define infll 0x3F3F3F3F3F3F3F3FLL
#define bpc __builtin_popcount

int n, a, b;

/*int x(int i)
{
    return (i + i/b) % a;
}
int y(int i)
{
    return i % b;
}*/

new main()
{
    cin >> n >> a >> b;

    int x = a/__gcd(a, b + 1) * b;

    set<pii> s;

    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;

        if (b - a + 1 >= x)
        {
            s.ins(mpr(0, x - 1));
        }
        else
        {
            int l = a % x;
            int r = b % x;

            if (l <= r)
            {
                s.ins(mpr(l, r));
            }
            else
            {
                s.ins(mpr(l, x - 1));
                s.ins(mpr(0, r));
            }
        }
    }

    stack<pii> nw;

    nw.push(*s.begin());
    s.erase(s.begin());

    while (!s.empty())
    {
        pii t = nw.top();
        pii a = *s.begin();

        if (t.se < a.fi) nw.push(a);
        else
        {
            nw.pop();
            nw.push(mpr(min(t.fi, a.fi), max(t.se, a.se)));
        }

        s.erase(s.begin());
    }


    int res = 0;

    while (!nw.empty())
    {
        res += nw.top().se - nw.top().fi + 1;
        nw.pop();
    }

    cout << res << endl;
    return 0;
}
// 4, 5 -> 10;
// 3, 6 -> 18;

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 12 ms 1236 KB Output is correct
3 Correct 11 ms 1304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 1 ms 296 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 11 ms 1328 KB Output is correct
17 Correct 113 ms 10156 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 746 ms 1928 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1148 ms 66120 KB Output is correct
3 Correct 1145 ms 66208 KB Output is correct
4 Correct 1207 ms 66232 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1148 ms 66120 KB Output is correct
3 Correct 1145 ms 66208 KB Output is correct
4 Correct 1207 ms 66232 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1220 ms 66116 KB Output is correct
7 Correct 1148 ms 66304 KB Output is correct
8 Correct 1197 ms 66212 KB Output is correct
9 Correct 1198 ms 66264 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1148 ms 66120 KB Output is correct
3 Correct 1145 ms 66208 KB Output is correct
4 Correct 1207 ms 66232 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 111 ms 10232 KB Output is correct
7 Correct 115 ms 10264 KB Output is correct
8 Correct 113 ms 10232 KB Output is correct
9 Correct 112 ms 10228 KB Output is correct
10 Correct 111 ms 10140 KB Output is correct
11 Correct 113 ms 10208 KB Output is correct
12 Correct 110 ms 10224 KB Output is correct
13 Correct 116 ms 10188 KB Output is correct
14 Correct 138 ms 10232 KB Output is correct
15 Correct 119 ms 10200 KB Output is correct
16 Correct 116 ms 10248 KB Output is correct
17 Correct 116 ms 10160 KB Output is correct
18 Correct 1204 ms 66056 KB Output is correct
19 Correct 1166 ms 66012 KB Output is correct
20 Correct 1188 ms 66016 KB Output is correct
21 Correct 110 ms 10184 KB Output is correct
22 Correct 112 ms 10200 KB Output is correct
23 Correct 324 ms 12800 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 114 ms 10156 KB Output is correct
3 Correct 113 ms 10152 KB Output is correct
4 Correct 1174 ms 66028 KB Output is correct
5 Correct 111 ms 10228 KB Output is correct
6 Correct 113 ms 10176 KB Output is correct
7 Correct 114 ms 10216 KB Output is correct
8 Correct 112 ms 10212 KB Output is correct
9 Correct 116 ms 10236 KB Output is correct
10 Correct 112 ms 10192 KB Output is correct
11 Correct 112 ms 10188 KB Output is correct
12 Correct 112 ms 10220 KB Output is correct
13 Correct 113 ms 10200 KB Output is correct
14 Correct 1206 ms 65884 KB Output is correct
15 Correct 110 ms 10188 KB Output is correct
16 Correct 1190 ms 65224 KB Output is correct
17 Correct 1163 ms 64568 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 12 ms 1236 KB Output is correct
3 Correct 11 ms 1304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 1 ms 296 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 11 ms 1328 KB Output is correct
17 Correct 113 ms 10156 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -