oj.uz

답안 #935568

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
935568 2024-02-29T09:20:28 Z sysia 이상한 기계 (APIO19_strange_device) C++17
5 / 100
 982 ms 162808 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;

void solve(){
    int n, A, B; cin >> n >> A >> B; 
    //po obrzydliwych obliczeniach dostajemy ze co AB to sie powtarza + dziala na samplach
    //jesli s \neq t mod AB, to daja rozne pary, nie wprost daja
    //wiec musi s \equiv t mod B, ale wtedy s \neq t mod A (bo gdyby zachodzilo przystawanie, to mozna wymnozyc(?))
    //czy to ze AB niekoniecznie wzglednie pierwsze przeszkadza w czyms?
    //wiec wtedy pierwsza wartosc daje inna reszte
    set<T>s;//przedzialy mod AB
    int C = A*B;
    for (int i = 0; i<n; i++){
        int l, r; cin >> l >> r;
        int L = l%C;
        int R = r%C;
        if (r-l+1 >= C) {
            s.insert({0, C-1});
        } else {
            if (L <= R) s.insert({L, R});
            else {
                s.insert({L, C-1});
                s.insert({0, R});
            }
        }
    }
    debug(s);
    map<int, int>sweep;
    for (auto [a, b]: s){
        sweep[a]++;
        sweep[b+1]--;
    }
    int prev = -1;
    int open = 0, ans = 0;
    for (auto [a, val]: sweep){
        debug(a, val, open);
        if (open) {
            ans += a-prev;
        }
        open += val;
        prev = a;
    }
    cout << ans << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 191 ms 25504 KB Output is correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 775 ms 162692 KB Output is correct
3 Incorrect 778 ms 162560 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 775 ms 162692 KB Output is correct
3 Incorrect 778 ms 162560 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 775 ms 162692 KB Output is correct
3 Incorrect 778 ms 162560 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 69 ms 16544 KB Output is correct
3 Correct 77 ms 16536 KB Output is correct
4 Correct 761 ms 162684 KB Output is correct
5 Correct 81 ms 16604 KB Output is correct
6 Correct 66 ms 16456 KB Output is correct
7 Correct 66 ms 16508 KB Output is correct
8 Correct 68 ms 16464 KB Output is correct
9 Correct 65 ms 16468 KB Output is correct
10 Correct 72 ms 16572 KB Output is correct
11 Correct 69 ms 16464 KB Output is correct
12 Correct 65 ms 16444 KB Output is correct
13 Correct 66 ms 16464 KB Output is correct
14 Correct 982 ms 162808 KB Output is correct
15 Incorrect 69 ms 16520 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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