Submission #983039

#	Time	Username	Problem	Language	Result	Execution time	Memory
983039		vjudge1	Strange Device (APIO19_strange_device)	C++17	15 / 100	5057 ms	524288 KiB

strange_device

#include<bits/stdc++.h>
#define sz size()
#define ll long long
using namespace std;

void out(__int128 a)
{
    string s;
    while(a)
        s += char(a % 10 + '0'),
             a /= 10;
    reverse(s.begin(), s.end());
    cout << s;
}

void solve()
{
    ll n, A, B, i, j, k;
    cin >> n >> A >> B;
    ll l[n + 1], r[n + 1];
    for(i = 1; i <= n; ++i)
        cin >> l[i] >> r[i];

    if(n == 1)
    {
        ll g = __gcd(A, B);
        __int128 x = A, y = B, z = g, x0 = (r[1] - l[1] + 1);
        x = x * y;
        if(x0 < x) x = x0;
        out(x);
        return;
    }

    map<pair<ll, ll>, bool> m;
    for(i = 1; i <= n; ++i)
        for(j = l[i]; j <= r[i]; ++j)
            m[{(j + j / B) % A, j % B}] = 1;
    cout << m.sz;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    solve();
}

Compilation message (stderr)

strange_device.cpp: In function 'void solve()':
strange_device.cpp:27:32: warning: unused variable 'z' [-Wunused-variable]
   27 |         __int128 x = A, y = B, z = g, x0 = (r[1] - l[1] + 1);
      |                                ^
strange_device.cpp:18:23: warning: unused variable 'k' [-Wunused-variable]
   18 |     ll n, A, B, i, j, k;
      |                       ^

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