oj.uz

Submission #902304

# Submission time Handle Problem Language Result Execution time Memory
902304 2024-01-10T08:17:05 Z Boycl07 Strange Device (APIO19_strange_device) C++17
45 / 100
 549 ms 90096 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define int ll
#define rep(i, n) for(int i = 1; i <= n; ++i)
#define forn(i, l, r) for(int i = l; i <= r; ++i)
#define ford(i, r, l) for(int i = r; i >= l; --i)
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define endl "\n"
#define task ""
#define sz(a) int(a.size())
#define C(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)

template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }

inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}


const int N =  2e5 + 10;
const int M = 1e3 + 3;
const int N1 = 2e3 + 10;
const int K = 1e2 + 1;
const int MOD = 1e9 + 7;
const ll INF = 1e18;
const ll LINF = 1e17 + 2;
const int block_size = 500;
const int LOG = 29;
const int offset = N;
const int LIM = 1e4 ;
const int AL = 26;

int n;
ll a, b;

vector<pii> p;

void add(int l, int r)
{
    p.pb({l, 1});
    p.pb({r + 1, -1});
}

void solve()
{
    cin >> n >> a >> b;
	ll period = a / __gcd(a, b + 1)  > INF / b ? INF : a / __gcd(a, b + 1) * b;
    rep(i, n)
    {
        ll l, r;
        cin >> l >> r;
        --l;
        --r;
        if(r - l + 1 >= period) return cout << period, void();
        l %= period;
        r %= period;
        if(l > r)
            add(0, r), add(l, period - 1);
        else
            add(l, r);
    }
    sort(all(p));
    int cnt = 0;
    ll last = 0;
    ll res = 0;
    for(int i = 0; i < sz(p); ++i)
    {
        int j = i;
        if(i > 0 && cnt)
            res += (p[i].fi - p[i - 1].fi);
        while(j < sz(p) && p[i].fi == p[j].fi)
        {
            cnt += p[j].se;
            ++j;
        }
        i = j - 1;
    }
    cout << res;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int TC = 1;


    while(TC--)
    {
        solve();
        cout << endl;
    }

    return 0;
}
//ha

Compilation message

strange_device.cpp: In function 'void solve()':
strange_device.cpp:76:8: warning: unused variable 'last' [-Wunused-variable]
   76 |     ll last = 0;
      |        ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 1364 KB Output is correct
3 Correct 4 ms 1240 KB Output is correct
4 Correct 0 ms 452 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 352 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 5 ms 1244 KB Output is correct
17 Correct 63 ms 8148 KB Output is correct
18 Correct 0 ms 344 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 394 ms 68896 KB Output is correct
3 Correct 398 ms 69028 KB Output is correct
4 Correct 371 ms 68832 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 394 ms 68896 KB Output is correct
3 Correct 398 ms 69028 KB Output is correct
4 Correct 371 ms 68832 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 405 ms 69092 KB Output is correct
7 Correct 402 ms 69036 KB Output is correct
8 Correct 390 ms 68744 KB Output is correct
9 Correct 491 ms 69756 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 394 ms 68896 KB Output is correct
3 Correct 398 ms 69028 KB Output is correct
4 Correct 371 ms 68832 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 41 ms 7648 KB Output is correct
7 Correct 46 ms 7624 KB Output is correct
8 Correct 49 ms 7520 KB Output is correct
9 Correct 40 ms 7632 KB Output is correct
10 Correct 37 ms 8660 KB Output is correct
11 Correct 39 ms 7880 KB Output is correct
12 Correct 50 ms 8392 KB Output is correct
13 Correct 42 ms 7896 KB Output is correct
14 Correct 52 ms 7424 KB Output is correct
15 Correct 48 ms 8916 KB Output is correct
16 Correct 49 ms 7908 KB Output is correct
17 Correct 39 ms 8540 KB Output is correct
18 Correct 405 ms 68880 KB Output is correct
19 Correct 371 ms 69288 KB Output is correct
20 Correct 509 ms 68732 KB Output is correct
21 Correct 51 ms 8676 KB Output is correct
22 Correct 41 ms 8336 KB Output is correct
23 Incorrect 135 ms 45060 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 53 ms 9208 KB Output is correct
3 Correct 44 ms 8916 KB Output is correct
4 Correct 549 ms 69108 KB Output is correct
5 Correct 49 ms 9000 KB Output is correct
6 Correct 51 ms 8296 KB Output is correct
7 Correct 42 ms 7372 KB Output is correct
8 Correct 51 ms 7908 KB Output is correct
9 Correct 41 ms 8984 KB Output is correct
10 Correct 61 ms 9184 KB Output is correct
11 Correct 52 ms 8188 KB Output is correct
12 Correct 37 ms 7624 KB Output is correct
13 Correct 44 ms 8128 KB Output is correct
14 Correct 484 ms 69028 KB Output is correct
15 Correct 47 ms 8676 KB Output is correct
16 Correct 390 ms 69544 KB Output is correct
17 Correct 381 ms 69752 KB Output is correct
18 Correct 1 ms 348 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 1364 KB Output is correct
3 Correct 4 ms 1240 KB Output is correct
4 Correct 0 ms 452 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 352 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 5 ms 1244 KB Output is correct
17 Correct 63 ms 8148 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 360 KB Output is correct
28 Incorrect 371 ms 90096 KB Output isn't correct
29 Halted 0 ms 0 KB -