Submission #398303

#	Time	Username	Problem	Language	Result	Execution time	Memory
398303		Mazaalai	Strange Device (APIO19_strange_device)	C++14	10 / 100	761 ms	78560 KiB

strange_device

#include <bits/stdc++.h>
#define int long long
using namespace std;
// #define FOR(i, begin, end) for (__typeof(end) i = (begin); i != (end) + 1 - 2 * ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
 
#define _upgrade ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORB(i, a, b) for (int i = a; i >= b; i--)
#define REP(i, a) for (int i = 0; i < a; i++)
#define REP1(i, a) for (int i = 1; i < a; i++)
#define REPB(i, a) for (int i = a - 1; i >= 0; i--)
#define TRAV(a,x) for (auto& a: x)
#define ALL(A) A.begin(), A.end()
#define LLA(A) A.rbegin(), A.rend()
#define II <int, int>
#define Q queue
#define ff first
#define bk back()
#define ss second
#define rs resize
#define ins insert 
#define fr front() 
#define ts to_string
#define pb push_back
#define mp make_pair
#define lb lower_bound 
#define ub upper_bound 
#define PQ priority_queue
#define umap unordered_map
#define sz(x) (int)x.size()
 
typedef long long ll;
typedef double db;
typedef unsigned uint;
typedef unsigned long long ull;
typedef unordered_map<int, int> umapII;
// PQ going up <int, VI, greater<int> >
typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<VB> VVB;
typedef vector<VVB> VVVB;
typedef vector<umapII> VumapII;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<VVLL> VVVLL;
typedef vector<VVVLL> VVVVLL;
typedef vector<db> VD;
typedef set<int> SI;
typedef set<string> SS;
typedef map<int, int> MII;
typedef map<string, int> MSI;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<PII> VPI;
typedef vector<VPI> VVPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VVVI> VVVVI;
typedef vector<VVVVI> VVVVVI;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
void eraseDups(VI& a) {
    a.erase(unique(a.begin(), a.end()), a.end());
}
int strToInt(string&a) {
    stringstream x(a);
    int b;
    x >> b;
    return b;
}
void readI(int& a) {
    cin >> a;
}
void readI(int& a, int&b) {
    cin >> a >> b;
}
void readI(int& a, int&b, int&c) {
    cin >> a >> b >> c;
}
VI readVI(int n) {
    VI a(n);
    REP(i, n) cin >> a[i];
    return a;
}
VVI readVVI(int n, int m) {
    VVI a(n, VI(m));
    REP(i, n) a[i] = readVI(m);
    return a;
}
VLL readVLL(ll n) {
    VLL a(n);
    REP(i, n) cin >> a[i];
    return a;
}
VVLL readVVLL(ll n, ll m) {
    VVLL a(n, VLL(m));
    REP(i, n) a[i] = readVLL(m);
    return a;
}
 
 
int gcd(int a, int b) {
   if (b == 0) return a;
   return gcd(b, a % b);
}
 
void print(VI& a) {
    for (auto el : a) {
        cout << el << ' ';
    }
    cout << '\n';
}
 
void print(VI& a, int n) {
    int cnt = 0;
    for (auto el : a) {
        if (cnt++ == n) break;
        cout << el << ' ';
    }
    cout << '\n';
}
const int MOD = 1e9 + 7;
const int MOD1 = 998244353;//119*2^23 +1;
const int INF = 2e9;
const ll INFF = INT64_MAX;
const db EPS = 1e-9;
const db PI = acos(-1.0); //M_PI;
const int moveX[] = {-1, 0, 1, 0};
const int moveY[] = {0, 1, 0, -1};
/*
|      ⣠⣶⡾⠏⠉⠙⠳⢦⡀⠀  ⠀⢠⠞⠉⠙⠲⡀
|    ⣴⠿⠏⠀⠀⠀⠀⠀⠀⢳⡀⠀  ⡏⠀⠀ ⠀⠀ ⢷
|⠀⠀⢠⣟⣋⡀⢀⣀⣀⡀⠀⣀⡀⣧⠀  ⢸⠀⠀⠀⠀   ⡇ ⠀
| ⠀⢸⣯⡭⠁⠸⣛⣟⠆⡴⣻⡲⣿   ⣸⠀⠀OK.  ⡇
|⠀⠀⣟⣿⡭⠀⠀⠀⠀⠀⢱⠀⠀⣿   ⢹⠀⠀⠀⠀⠀ ⡇
|⠀⠀⠙⢿⣯⠄⠀⠀⠀⢀⡀⠀⠀⡿⠀  ⡇⠀⠀ ⠀ ⡼
|⠀⠀⠀⠀⠹⣶⠆⠀⠀⠀⠀⠀⡴⠃ ⠀ ⠘⠤⣄⣠⠞⠀ ⠀
|⠀⠀⠀⠀⢸⣷⡦⢤⡤⢤⣞⣁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀
|⠀⢀⣤⣴⣿⣏⠁⠀⠀⠸⣏⢯⣷⣖⣦⡀⠀⠀⠀⠀⠀⠀
|⢀⣾⣽⣿⣿⣿⣿⠛⢲⣶⣾⢉⡷⣿⣿⠵⣿⠀⠀⠀⠀⠀
|⣼⣿⠍⠉⣿⡭⠉⠙⢺⣇⣼⡏⠀ ⠀⣄⢸⣿
|⣿⣿⣧⣀⣿.........⣀⣰⣏⣘⣆⣀
      
|                                                   _         _   _
|                                                   (_)       | | | |
 _ __  _ __ ___   __ _ _ __ __ _ _ __ ___  _ __ ___  _ ___ ___| |_| |_
| '_ \| '__/ _ \ / _` | '__/ _` | '_ ` _ \| '_ ` _ \| / __/ __| __| __|
| |_) | | | (_) | (_| | | | (_| | | | | | | | | | | | \__ \__ \ |_| |_
| .__/|_|  \___/ \__, |_|  \__,_|_| |_| |_|_| |_| |_|_|___/___/\__|\__|
| |               __/ |
|_|              |___/
 _   _      _ _    __        __         _     _ 
| | | | ___| | | __\ \      / /__  _ __| | __| |
| |_| |/ _ \ | |/ _ \ \ /\ / / _ \| '__| |/ _` |
|  _  |  __/ | | (_) \ V  V / (_) | |  | | (_| |
|_| |_|\___|_|_|\___/ \_/\_/ \___/|_|  |_|\__,_|                                  
 ____     __    _______    _______   __________
|     \  |  |  |  _____|  /  _____) |____  ____|
|  |\  \ |  |  | |__     (  (_____      |  |
|  | \  \|  |  |  __|     \_____  \     |  | 
|  |  \     |  | |_____    _____)  )    |  | 
|__|   \____|  |_______|  (_______/     |__| 
 
 
 
 
 
*/
 
 
 
 
 
 
 
 
 
 
 
 
int n, A, B;
void go () {
    cin >> n >> A >> B;
    // x, y = (t + (t / B)) % A, t % B
    bool gege = 0, gogo = 0;
    int AB = INFF / A / B;
    
    if (AB > 0) {
        gege = 1;
        AB = A * B;
    } else {
        AB = INFF;
    }
    VPI times;
    int sum = 0;
    REP(i, n) {
        int l, r;
        cin >> l >> r;
        // cout << l << ' ' << r << ": ";
        if (gege) {
            int minus = l - (l % AB);
            l -= minus;
            r -= minus;
            if (r - l + 1 >= AB)  {
                cout << AB << '\n';
                return;
            }
        }
        if (r < AB) {
            // cout << l << ' ' << r << '\n';
            times.pb({l, r});
            if (!gogo && INFF - (r - l+1) > sum)
            sum += r - l+1;
            else gogo = 1;
        } else {
            // cout << l << ' ' << AB-1 << ',' << 0 << ' ' << r%AB << '\n';

            if (!gogo && INFF - (AB - l+1) > sum)
            sum += AB - l+1;
            else gogo = 1;
            times.pb({l, AB-1});
            if (!gogo && INFF - (r%AB + 1) > sum)
            sum += r%AB + 1;
            else gogo = 1;
            times.pb({0, r%AB});
        }
    }
    int cur = 0, ans = 0;
    sort(ALL(times));
    set <PII> seen;

    for (int i = 0; i < (ll)(times.size()) && cur < AB; i++) {
        int l = times[i].ff, r = times[i].ss;
        // cout << l << ' ' << r << '\n';
        l = max(l, cur);
        if (l > r) continue;
        if (!gogo && sum < (ll)1e7) {
            for (int i = l; i <= r; i++) {
                // cout << i << ": " << (i + (i / m))%n << ',' << i % m << '\n';
                seen.insert({(i + (i / B))%A, i%B});
            }
        } else {
            ans += (r - l + 1);
        }
        cur = max(cur, r+1);
    }
    cout << seen.size() << '\n';
}
 
 
 
signed main () {
 
#ifdef ONLINE_JUDGE
#else
    // freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
#endif
    _upgrade
    int T = 1;
    while(T--) go();
    return 0;
}
 
/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
    
*/

• Subtask 1: 10 / 10
• Subtask 2: 0 / 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