Submission #1068799

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1068799	2024-08-21T12:15:26 Z	alexdd	Strange Device (APIO19_strange_device)	C++17	65 / 100	1351 ms	115796 KB

strange_device

#include<bits/stdc++.h>
using namespace std;
#define int long long
int gcd(int x, int y)
{
    while(x>0)
    {
        int r = y%x;
        y=x;
        x=r;
    }
    return y;
}
set<pair<__int128,__int128>> s;
void baga(__int128 le, __int128 ri)
{
    if(s.empty())
    {
        s.insert({le,ri});
        return;
    }
    auto it = s.lower_bound({le+1,-1});
    if(it!=s.begin()) it--;
    while(it!=s.end())
    {
        if((*it).first > ri)
            break;
        if((*it).second < le)
        {
            it++;
        }
        else if((*it).first <= le && (*it).second >= ri)
        {
            return;
        }
        else
        {
            le = min(le, (*it).first);
            ri = max(ri, (*it).second);
            it = s.erase(it);
        }
    }
    s.insert({le,ri});
}
signed main()
{
    int n,A,B;
    cin>>n>>A>>B;
    A = A / gcd(A,B+1);
    __int128 le,ri;

    __int128 copA=A,copB=B;
    __int128 prod=copA*copB;

    int cle,cri;
    for(int i=1;i<=n;i++)
    {
        cin>>cle>>cri;
        le=cle;
        ri=cri;
        if(le==ri)
        {
            baga(le%prod,le%prod);
            continue;
        }
        le = le%prod;
        ri = ri%prod;
        if(le<ri)
        {
            baga(le,ri);
        }
        else
        {
            baga(le,prod-1);
            baga(0,ri);
        }
    }
    int cnt=0;
    for(auto it:s)
    {
        cnt += it.second-it.first+1;
    }
    cout<<cnt;
    return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	23 ms	1512 KB	Output is correct
3	Correct	23 ms	1372 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	432 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	12 ms	1372 KB	Output is correct
17	Correct	114 ms	11196 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct

Subtask #2
0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	436 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1185 ms	106700 KB	Output is correct
3	Correct	1191 ms	115792 KB	Output is correct
4	Correct	1313 ms	115796 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	1185 ms	106700 KB	Output is correct
3	Correct	1191 ms	115792 KB	Output is correct
4	Correct	1313 ms	115796 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1202 ms	115784 KB	Output is correct
7	Correct	1253 ms	115572 KB	Output is correct
8	Correct	1234 ms	115760 KB	Output is correct
9	Correct	1247 ms	115712 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1185 ms	106700 KB	Output is correct
3	Correct	1191 ms	115792 KB	Output is correct
4	Correct	1313 ms	115796 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	128 ms	11840 KB	Output is correct
7	Correct	108 ms	11812 KB	Output is correct
8	Correct	108 ms	11860 KB	Output is correct
9	Correct	112 ms	11708 KB	Output is correct
10	Correct	112 ms	11860 KB	Output is correct
11	Correct	107 ms	11860 KB	Output is correct
12	Correct	114 ms	11856 KB	Output is correct
13	Correct	109 ms	11856 KB	Output is correct
14	Correct	116 ms	11680 KB	Output is correct
15	Correct	130 ms	11864 KB	Output is correct
16	Correct	112 ms	11756 KB	Output is correct
17	Correct	136 ms	11860 KB	Output is correct
18	Correct	1106 ms	115540 KB	Output is correct
19	Correct	1215 ms	115676 KB	Output is correct
20	Correct	1288 ms	115692 KB	Output is correct
21	Correct	105 ms	11864 KB	Output is correct
22	Correct	147 ms	11808 KB	Output is correct
23	Correct	336 ms	12932 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	133 ms	11768 KB	Output is correct
3	Correct	124 ms	11900 KB	Output is correct
4	Correct	1263 ms	115792 KB	Output is correct
5	Correct	155 ms	11928 KB	Output is correct
6	Correct	128 ms	11872 KB	Output is correct
7	Correct	162 ms	11860 KB	Output is correct
8	Correct	116 ms	11732 KB	Output is correct
9	Correct	144 ms	11860 KB	Output is correct
10	Correct	111 ms	11860 KB	Output is correct
11	Correct	121 ms	11788 KB	Output is correct
12	Correct	108 ms	11856 KB	Output is correct
13	Correct	136 ms	11856 KB	Output is correct
14	Correct	1351 ms	115588 KB	Output is correct
15	Correct	109 ms	11088 KB	Output is correct
16	Correct	1241 ms	115628 KB	Output is correct
17	Correct	1249 ms	115612 KB	Output is correct
18	Correct	0 ms	344 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	23 ms	1512 KB	Output is correct
3	Correct	23 ms	1372 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	432 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	12 ms	1372 KB	Output is correct
17	Correct	114 ms	11196 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Incorrect	0 ms	436 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #1068799

Compilation message