Submission #724615

#	Time	Username	Problem	Language	Result	Execution time	Memory
724615		n0sk1ll	Strange Device (APIO19_strange_device)	C++14	65 / 100	2226 ms	361280 KiB

strange_device

#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 (stderr)

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 / 10
• Subtask 2: 0 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 0 / 30