oj.uz

답안 #398284

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
398284 2021-05-04T06:08:13 Z Mazaalai 이상한 기계 (APIO19_strange_device) C++14
5 / 100
 547 ms 19532 KB 
#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, gege1 = 0;
    int AB = INFF / A / B;
    
    if (AB > 0) {
        gege = 1;
        AB = A * B;
    }
    VPI times;
    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) gege1 = 1;
        }
        if (r < AB) {
            // cout << l << ' ' << r << '\n';
            times.pb({l, r});
        } else {
            // cout << l << ' ' << AB-1 << ',' << 0 << ' ' << r%AB << '\n';
            times.pb({l, AB-1});
            times.pb({0, r%AB});
        }
    }
    if (gege1) {
        cout << AB << '\n';
        return;
    }
    int cur = 0, ans = 0;
    sort(ALL(times));
    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;
        ans += r - l + 1;
        cur = max(cur, r+1);
    }
    cout << ans << '\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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 6 ms 1032 KB Output is correct
3 Correct 5 ms 976 KB Output is correct
4 Incorrect 2 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Runtime error 1 ms 332 KB Execution killed with signal 8

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 346 ms 18052 KB Output is correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 446 ms 18408 KB Output is correct
3 Incorrect 504 ms 18340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 446 ms 18408 KB Output is correct
3 Incorrect 504 ms 18340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 446 ms 18408 KB Output is correct
3 Incorrect 504 ms 18340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 51 ms 5632 KB Output is correct
3 Correct 50 ms 5620 KB Output is correct
4 Correct 547 ms 18628 KB Output is correct
5 Correct 49 ms 5676 KB Output is correct
6 Correct 52 ms 5724 KB Output is correct
7 Correct 49 ms 5704 KB Output is correct
8 Correct 49 ms 5692 KB Output is correct
9 Correct 48 ms 5692 KB Output is correct
10 Correct 48 ms 5648 KB Output is correct
11 Correct 48 ms 5688 KB Output is correct
12 Correct 43 ms 5644 KB Output is correct
13 Correct 49 ms 5688 KB Output is correct
14 Correct 496 ms 19532 KB Output is correct
15 Incorrect 49 ms 5692 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 6 ms 1032 KB Output is correct
3 Correct 5 ms 976 KB Output is correct
4 Incorrect 2 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -