Submission #1068806

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1068806	2024-08-21T12:17:39 Z	alexdd	Strange Device (APIO19_strange_device)	C++17	65 / 100	1232 ms	107096 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});
}
void afis(__int128 x)
{
    vector<int> cif;
    while(x>0)
    {
        cif.push_back(x%10);
        x/=10;
    }
    reverse(cif.begin(),cif.end());
    for(auto c:cif) cout<<c;
}
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);
        }
    }
    __int128 cnt=0;
    for(auto it:s)
    {
        cnt += it.second-it.first+1;
    }
    afis(cnt);
    return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	11 ms	1372 KB	Output is correct
3	Correct	11 ms	1576 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	432 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 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	0 ms	348 KB	Output is correct
13	Correct	0 ms	436 KB	Output is correct
14	Correct	0 ms	344 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	10 ms	1352 KB	Output is correct
17	Correct	109 ms	11312 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct

Subtask #2
0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	432 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	348 KB	Output is correct
2	Correct	2 ms	344 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	636 ms	19540 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1134 ms	107096 KB	Output is correct
3	Correct	1161 ms	106740 KB	Output is correct
4	Correct	1210 ms	106780 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1134 ms	107096 KB	Output is correct
3	Correct	1161 ms	106740 KB	Output is correct
4	Correct	1210 ms	106780 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1144 ms	106588 KB	Output is correct
7	Correct	1183 ms	106816 KB	Output is correct
8	Correct	1137 ms	106688 KB	Output is correct
9	Correct	1221 ms	106836 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1134 ms	107096 KB	Output is correct
3	Correct	1161 ms	106740 KB	Output is correct
4	Correct	1210 ms	106780 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	109 ms	11164 KB	Output is correct
7	Correct	103 ms	11092 KB	Output is correct
8	Correct	110 ms	11080 KB	Output is correct
9	Correct	115 ms	11092 KB	Output is correct
10	Correct	111 ms	11088 KB	Output is correct
11	Correct	111 ms	11088 KB	Output is correct
12	Correct	112 ms	11092 KB	Output is correct
13	Correct	110 ms	11092 KB	Output is correct
14	Correct	115 ms	11188 KB	Output is correct
15	Correct	115 ms	11088 KB	Output is correct
16	Correct	118 ms	11088 KB	Output is correct
17	Correct	111 ms	11084 KB	Output is correct
18	Correct	1124 ms	106688 KB	Output is correct
19	Correct	1182 ms	106836 KB	Output is correct
20	Correct	1201 ms	106792 KB	Output is correct
21	Correct	110 ms	11088 KB	Output is correct
22	Correct	108 ms	11088 KB	Output is correct
23	Correct	283 ms	10324 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	106 ms	11152 KB	Output is correct
3	Correct	118 ms	11128 KB	Output is correct
4	Correct	1183 ms	106820 KB	Output is correct
5	Correct	124 ms	11236 KB	Output is correct
6	Correct	117 ms	11104 KB	Output is correct
7	Correct	113 ms	11192 KB	Output is correct
8	Correct	120 ms	11088 KB	Output is correct
9	Correct	110 ms	11060 KB	Output is correct
10	Correct	105 ms	11092 KB	Output is correct
11	Correct	108 ms	11092 KB	Output is correct
12	Correct	102 ms	11092 KB	Output is correct
13	Correct	120 ms	11092 KB	Output is correct
14	Correct	1232 ms	106652 KB	Output is correct
15	Correct	107 ms	10320 KB	Output is correct
16	Correct	1149 ms	106724 KB	Output is correct
17	Correct	1127 ms	106672 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	11 ms	1372 KB	Output is correct
3	Correct	11 ms	1576 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	432 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 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	0 ms	348 KB	Output is correct
13	Correct	0 ms	436 KB	Output is correct
14	Correct	0 ms	344 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	10 ms	1352 KB	Output is correct
17	Correct	109 ms	11312 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Incorrect	0 ms	432 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #1068806

Compilation message