Submission #484573

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
484573	2021-11-04T12:51:00 Z	CyberSleeper	Strange Device (APIO19_strange_device)	C++14	35 / 100	455 ms	53404 KB

strange_device

#include <bits/stdc++.h>
#define fastio      ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug(x)    cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define fi          first
#define se          second
#define mp          make_pair
#define pb          push_back
#define ll          long long
#define pll         pair<ll, ll>
#define ull         unsigned long long
#define ld          long double
#define pii         pair<ll, ll>
#define nl          '\n'
#define tb          '\t'
#define sp          ' '
using namespace std;

const ll MX=1000001, MOD=998244353, BLOCK=330, INF=1e9+7, INFF=2e18;
const ld ERR=1e-7, pi=3.14159265358979323846;

ll N, A, B, cyc, last=0;
vector<pll> L;

int main(){
    fastio;
    cin >> N >> A >> B;
    cyc=(INFF+A-1)/A;
    if(B>=cyc)
        cyc=INFF;
    else
        cyc=A*B;
    if((A==2 && B&1) || (A%2==0 && B==1))
        cyc/=2;
    for(ll i=0, x, y; i<N; i++){
        cin >> x >> y;
        if(y-x+1>=cyc){
            L.pb({0, cyc-1});
        }else{
            x%=cyc;
            y%=cyc;
            if(x<=y)
                L.pb({x, y});
            else{
                L.pb({0, y});
                L.pb({x, cyc-1});
            }
        }
    }
    N=L.size();
    sort(L.begin(), L.end());
    ll ans=0;
    for(auto i:L){
        ll x=i.fi, y=i.se;
        if(y<last)
            continue;
        x=max(last, x);
        ans+=y-x+1;
        last=max(last, y+1);
    }
    cout << ans << nl;
}

Subtask #1
0 / 10.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 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	296 ms	41272 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	380 ms	18504 KB	Output is correct
3	Correct	382 ms	53404 KB	Output is correct
4	Correct	370 ms	53136 KB	Output is correct

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	380 ms	18504 KB	Output is correct
3	Correct	382 ms	53404 KB	Output is correct
4	Correct	370 ms	53136 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	398 ms	53348 KB	Output is correct
7	Correct	388 ms	53136 KB	Output is correct
8	Incorrect	405 ms	53204 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	380 ms	18504 KB	Output is correct
3	Correct	382 ms	53404 KB	Output is correct
4	Correct	370 ms	53136 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	39 ms	5680 KB	Output is correct
7	Correct	40 ms	5668 KB	Output is correct
8	Correct	40 ms	5688 KB	Output is correct
9	Correct	44 ms	5676 KB	Output is correct
10	Correct	38 ms	5692 KB	Output is correct
11	Correct	39 ms	5684 KB	Output is correct
12	Correct	42 ms	5704 KB	Output is correct
13	Correct	43 ms	5656 KB	Output is correct
14	Correct	38 ms	5680 KB	Output is correct
15	Correct	42 ms	5684 KB	Output is correct
16	Correct	40 ms	5692 KB	Output is correct
17	Correct	41 ms	5680 KB	Output is correct
18	Correct	388 ms	53168 KB	Output is correct
19	Correct	392 ms	53192 KB	Output is correct
20	Correct	436 ms	53200 KB	Output is correct
21	Correct	41 ms	5668 KB	Output is correct
22	Correct	36 ms	5660 KB	Output is correct
23	Correct	132 ms	18496 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	312 KB	Output is correct
2	Correct	45 ms	5696 KB	Output is correct
3	Correct	46 ms	5620 KB	Output is correct
4	Correct	455 ms	53176 KB	Output is correct
5	Correct	41 ms	5708 KB	Output is correct
6	Correct	45 ms	5696 KB	Output is correct
7	Correct	42 ms	5712 KB	Output is correct
8	Correct	42 ms	5692 KB	Output is correct
9	Correct	40 ms	5680 KB	Output is correct
10	Correct	41 ms	5612 KB	Output is correct
11	Correct	48 ms	5636 KB	Output is correct
12	Correct	41 ms	5736 KB	Output is correct
13	Correct	46 ms	5592 KB	Output is correct
14	Correct	421 ms	53072 KB	Output is correct
15	Incorrect	45 ms	5700 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #8
0 / 30.0

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

Submission #484573

Compilation message