제출 #1166785

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166785		sunflower	Vepar (COCI21_vepar)	C++17	30 / 70	1599 ms	117852 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(x) cerr << "[" << #x << " = " << (x) << "]" << endl

#define left    __left
#define right   __right
#define prev    __prev
#define fi      first
#define se      second

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

int t;

#define MAX_N 10'000'100
int minPrime[MAX_N + 2];
int f[MAX_N + 2], g[MAX_N + 2];

void sieve() {
    FOR(i, 1, MAX_N) minPrime[i] = i;

    FOR(i, 2, trunc(sqrt(MAX_N))) {
        if (minPrime[i] == i) {
            FOR(j, i, MAX_N / i) {
                if (minPrime[i * j] == i * j)
                    minPrime[i * j] = i;
            }
        }
    }
}

void process(int L, int R, int cnt[]) {
    FOR(i, 2, int(1e7)) cnt[i] = 0;

    FOR(i, L, R) {
        int x = i;
        while (x > 1) {
            int k = minPrime[x];
            cnt[k]++;
            x /= k;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
//    freopen("test.inp","r",stdin);
//    freopen("test.out","w",stdout);

    sieve();

    cin >> t;
    while (t--) {
        int L, R, X, Y;
        cin >> L >> R >> X >> Y;
        process(L, R, f);
        process(X, Y, g);

        bool ok = true;
        FOR(i, 2, max(R, Y)) if (f[i] > g[i]) {ok = false; break;}

        cout << (ok ? "DA\n" : "NE\n");
    }

    return 0;
}

/* Discipline - Calm */

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