oj.uz

Submission #902299

# Submission time Handle Problem Language Result Execution time Memory
902299 2024-01-10T08:14:38 Z Boycl07 Strange Device (APIO19_strange_device) C++17
10 / 100
 568 ms 89848 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)
    {
        int 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 4 ms 1324 KB Output is correct
3 Correct 6 ms 1248 KB Output is correct
4 Correct 1 ms 360 KB Output is correct
5 Correct 0 ms 360 KB Output is correct
6 Correct 0 ms 360 KB Output is correct
7 Correct 0 ms 360 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 4 ms 1248 KB Output is correct
17 Correct 48 ms 7760 KB Output is correct
18 Incorrect 1 ms 344 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
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 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

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 348 KB Output is correct
5 Incorrect 349 ms 89848 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 348 KB Output is correct
2 Correct 383 ms 70220 KB Output is correct
3 Correct 444 ms 70392 KB Output is correct
4 Correct 362 ms 68712 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 383 ms 70220 KB Output is correct
3 Correct 444 ms 70392 KB Output is correct
4 Correct 362 ms 68712 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 420 ms 70404 KB Output is correct
7 Correct 394 ms 69936 KB Output is correct
8 Correct 376 ms 69772 KB Output is correct
9 Correct 455 ms 70564 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 383 ms 70220 KB Output is correct
3 Correct 444 ms 70392 KB Output is correct
4 Correct 362 ms 68712 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 43 ms 8848 KB Output is correct
7 Correct 46 ms 7948 KB Output is correct
8 Correct 38 ms 8404 KB Output is correct
9 Correct 37 ms 8392 KB Output is correct
10 Correct 37 ms 8148 KB Output is correct
11 Correct 39 ms 8536 KB Output is correct
12 Correct 37 ms 8144 KB Output is correct
13 Correct 44 ms 8300 KB Output is correct
14 Correct 39 ms 8828 KB Output is correct
15 Correct 50 ms 7948 KB Output is correct
16 Correct 48 ms 8076 KB Output is correct
17 Correct 47 ms 8708 KB Output is correct
18 Correct 430 ms 69072 KB Output is correct
19 Correct 377 ms 70096 KB Output is correct
20 Correct 478 ms 70132 KB Output is correct
21 Correct 52 ms 8396 KB Output is correct
22 Correct 36 ms 8912 KB Output is correct
23 Incorrect 155 ms 43672 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB Output is correct
2 Correct 43 ms 8924 KB Output is correct
3 Correct 60 ms 8148 KB Output is correct
4 Correct 568 ms 70328 KB Output is correct
5 Correct 47 ms 9164 KB Output is correct
6 Correct 50 ms 9016 KB Output is correct
7 Correct 57 ms 8400 KB Output is correct
8 Correct 55 ms 8488 KB Output is correct
9 Correct 57 ms 7936 KB Output is correct
10 Correct 50 ms 8596 KB Output is correct
11 Correct 41 ms 8392 KB Output is correct
12 Correct 36 ms 7372 KB Output is correct
13 Correct 43 ms 8656 KB Output is correct
14 Correct 543 ms 68632 KB Output is correct
15 Correct 48 ms 7892 KB Output is correct
16 Correct 383 ms 70084 KB Output is correct
17 Correct 422 ms 69464 KB Output is correct
18 Incorrect 0 ms 344 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 352 KB Output is correct
2 Correct 4 ms 1324 KB Output is correct
3 Correct 6 ms 1248 KB Output is correct
4 Correct 1 ms 360 KB Output is correct
5 Correct 0 ms 360 KB Output is correct
6 Correct 0 ms 360 KB Output is correct
7 Correct 0 ms 360 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 4 ms 1248 KB Output is correct
17 Correct 48 ms 7760 KB Output is correct
18 Incorrect 1 ms 344 KB Output isn't correct
19 Halted 0 ms 0 KB -