oj.uz

Submission #724615

# Submission time Handle Problem Language Result Execution time Memory
724615 2023-04-15T16:36:26 Z n0sk1ll Strange Device (APIO19_strange_device) C++14
65 / 100
 2226 ms 361280 KB 
#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

#define int li

const li inf=2e18;

map<li,vector<pli>> segs;
set<li> kords;
map<li,li> cisti;


signed main()
{
    FAST;

    int n; cin>>n;
    li A,B; cin>>A>>B;

    li d=__gcd(A,B+1);
    A/=d;

    vector<pli> ulaz;
    while (n--)
    {
        li l,r; cin>>l>>r;
        if (A<inf/B) l%=(A*B),r%=(A*B);
        if (l>r) ulaz.pb({0,r}),ulaz.pb({l,A*B-1});
        else ulaz.pb({l,r});
    }

    for (auto [l,r] : ulaz)
    {
        if (r/A == l/A) segs[l/A].pb({l%A,r%A}),kords.insert(l/A);
        else
        {
            segs[l/A].pb({l%A,A-1});
            segs[r/A].pb({0,r%A});
            cisti[l/A+1]++;
            cisti[r/A]--;
            kords.insert(l/A);
            kords.insert(l/A+1);
            kords.insert(r/A);
        }
    }

    li ans=0;

    li kolkoclear=0;
    li majmuncina=-1;
    for (auto x : kords)
    {
        bool staromeso=false;
        if (kolkoclear==0) staromeso=true;
        kolkoclear+=cisti[x]; //cout<<x<<": "<<cisti[x]<<endl;
        if (kolkoclear>0 && staromeso) majmuncina=x;

        //cout<<"marmun "<<kolkoclear<<endl;

        if (kolkoclear==0 && majmuncina!=-1) ans+=(x-majmuncina)*A,majmuncina=-1;
        if (kolkoclear==0)
        {
            vector<pair<li,li>> lensi;
            for (auto it : segs[x]) lensi.pb({it.xx,1}),lensi.pb({it.yy+1,-1});
            sort(all(lensi));

            li preth=-1;
            li kolkocur=0;
            for (auto y : lensi)
            {
                if (preth!=-1 && kolkocur) ans+=y.xx-preth;
                preth=y.xx; kolkocur+=y.yy;
            }
        }
    }

    cout<<ans<<"\n";
}

//Note to self: Check for overflow

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:65:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |     for (auto [l,r] : ulaz)
      |               ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 6 ms 1112 KB Output is correct
3 Correct 6 ms 1192 KB Output is correct
4 Correct 0 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 316 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 320 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 6 ms 1104 KB Output is correct
17 Correct 48 ms 4244 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 530 ms 96968 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 564 ms 65076 KB Output is correct
3 Correct 579 ms 65148 KB Output is correct
4 Correct 545 ms 64616 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 564 ms 65076 KB Output is correct
3 Correct 579 ms 65148 KB Output is correct
4 Correct 545 ms 64616 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 611 ms 88092 KB Output is correct
7 Correct 636 ms 81036 KB Output is correct
8 Correct 606 ms 70036 KB Output is correct
9 Correct 627 ms 82984 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 564 ms 65076 KB Output is correct
3 Correct 579 ms 65148 KB Output is correct
4 Correct 545 ms 64616 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 58 ms 4916 KB Output is correct
7 Correct 58 ms 5700 KB Output is correct
8 Correct 58 ms 5696 KB Output is correct
9 Correct 53 ms 5920 KB Output is correct
10 Correct 51 ms 4348 KB Output is correct
11 Correct 53 ms 4280 KB Output is correct
12 Correct 47 ms 4228 KB Output is correct
13 Correct 43 ms 4260 KB Output is correct
14 Correct 191 ms 37728 KB Output is correct
15 Correct 49 ms 4872 KB Output is correct
16 Correct 72 ms 6056 KB Output is correct
17 Correct 232 ms 36888 KB Output is correct
18 Correct 468 ms 32972 KB Output is correct
19 Correct 441 ms 33480 KB Output is correct
20 Correct 426 ms 34348 KB Output is correct
21 Correct 50 ms 4396 KB Output is correct
22 Correct 45 ms 4476 KB Output is correct
23 Correct 204 ms 46960 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 49 ms 5332 KB Output is correct
3 Correct 80 ms 9452 KB Output is correct
4 Correct 874 ms 87512 KB Output is correct
5 Correct 240 ms 36804 KB Output is correct
6 Correct 292 ms 36868 KB Output is correct
7 Correct 254 ms 36804 KB Output is correct
8 Correct 61 ms 4420 KB Output is correct
9 Correct 97 ms 13144 KB Output is correct
10 Correct 216 ms 36896 KB Output is correct
11 Correct 191 ms 36984 KB Output is correct
12 Correct 192 ms 36916 KB Output is correct
13 Correct 46 ms 4892 KB Output is correct
14 Correct 480 ms 34156 KB Output is correct
15 Correct 75 ms 10716 KB Output is correct
16 Correct 2226 ms 361280 KB Output is correct
17 Correct 626 ms 34520 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 6 ms 1112 KB Output is correct
3 Correct 6 ms 1192 KB Output is correct
4 Correct 0 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 316 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 320 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 6 ms 1104 KB Output is correct
17 Correct 48 ms 4244 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 316 KB Output is correct
20 Incorrect 0 ms 212 KB Output isn't correct
21 Halted 0 ms 0 KB -