제출 #724626

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
724626		n0sk1ll	이상한 기계 (APIO19_strange_device)	C++14	100 / 100	3161 ms	381044 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

const li inf=2e18;

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


int main()
{
    FAST;

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

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

    li mozdanskurans=0;

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

    if (A>=inf/B || A*B>=1'000'000'000'000'000'000ll)
        return cout<<mozdanskurans,0;

    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

/*

1 999999999 1000000000
1 1000000000000000000

*/

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30