oj.uz

Submission #595784

# Submission time Handle Problem Language Result Execution time Memory
595784 2022-07-14T06:40:38 Z nguyen31hoang08minh2003 Vepar (COCI21_vepar) C++14
70 / 70
 335 ms 14404 KB 
/*
 /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\
/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \
\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /
 \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/
\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /
 \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/
 /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \
/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \
\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /
 \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /
 /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\
/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \
 /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\
/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \
\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /
 \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/
\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /
 \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/
  \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /
   \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/
   /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\
  /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \
 /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\
/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \
 /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\
/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \
\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /
 \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/
*/
#include <bits/stdc++.h>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

const int maxD = 1e7 + 7;

int t, a, b, c, d;
bool sieve[maxD];
vi primes;

int ceilint(ll x, ll y) {
    return x / y + !!(x % y);
}

int countDivisors(int l, int r, int p) {
    int res = 0, x, y;
    for (ll z = p;; z *= p) {
        x = ceilint(l, z);
        y = r / z;
        if (x > y)
            break;
        res += y - x + 1;
    }
    return res;
}

bool solve(int a, int b, int c, int d) {
    const int n = max({a, b, c, d});
    for (const int &p : primes) {
        if (p > n)
            break;
        if (countDivisors(a, b, p) > countDivisors(c, d, p))
            return false;
    }
    return true;
}

int main() {
    #ifdef LOCAL
        freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
    d = 1e7;
    for (ll i = 2, j; i <= d; ++i)
        if (!sieve[i]) {
            primes.pb(i);
            for (j = i * i; j <= d; j += i)
                sieve[j] = true;
        }
    for (cin >> t; t--;) {
        cin >> a >> b >> c >> d;
        if (solve(a, b, c, d))
            cout << "DA\n";
        else
            cout << "NE\n";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 14276 KB Output is correct
2 Correct 60 ms 14304 KB Output is correct
3 Correct 64 ms 14304 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 14308 KB Output is correct
2 Correct 60 ms 14296 KB Output is correct
3 Correct 62 ms 14224 KB Output is correct
4 Correct 78 ms 14300 KB Output is correct
5 Correct 70 ms 14308 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 14244 KB Output is correct
2 Correct 70 ms 14312 KB Output is correct
3 Correct 77 ms 14304 KB Output is correct
4 Correct 81 ms 14236 KB Output is correct
5 Correct 71 ms 14304 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 14248 KB Output is correct
2 Correct 90 ms 14304 KB Output is correct
3 Correct 84 ms 14276 KB Output is correct
4 Correct 130 ms 14312 KB Output is correct
5 Correct 105 ms 14308 KB Output is correct
6 Correct 129 ms 14320 KB Output is correct
7 Correct 335 ms 14404 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 14312 KB Output is correct
2 Correct 64 ms 14312 KB Output is correct
3 Correct 81 ms 14300 KB Output is correct
4 Correct 91 ms 14284 KB Output is correct
5 Correct 94 ms 14228 KB Output is correct
6 Correct 181 ms 14304 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 14312 KB Output is correct
2 Correct 79 ms 14304 KB Output is correct
3 Correct 71 ms 14304 KB Output is correct
4 Correct 87 ms 14312 KB Output is correct
5 Correct 85 ms 14276 KB Output is correct
6 Correct 192 ms 14300 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 14304 KB Output is correct
2 Correct 75 ms 14308 KB Output is correct
3 Correct 68 ms 14276 KB Output is correct
4 Correct 107 ms 14300 KB Output is correct
5 Correct 90 ms 14312 KB Output is correct
6 Correct 182 ms 14296 KB Output is correct
7 Correct 317 ms 14228 KB Output is correct