oj.uz

답안 #381913

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
381913 2021-03-26T06:46:11 Z VEGAnn Vepar (COCI21_vepar) C++14
70 / 70
 349 ms 43876 KB 
#include <bits/stdc++.h>
#define PB push_back
using namespace std;
typedef long long ll;
const int MX = int(1e7) + 10;
const int oo = 2e9;
vector<int> prms;
int mn[MX];

int get_cnt(int l, int r, int cr){
    ll po = cr;
    int res = 0;

    while (po <= r){
        res += (r / po) - ((l - 1) / po);
        po *= cr;
    }

    return res;
}

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    fill(mn, mn + MX, oo);

    for (int i = 2; i < MX; i++){
        if (mn[i] < oo) continue;

        mn[i] = i;

        prms.PB(i);

        if (ll(i) * ll(i) > MX) continue;

        for (int j = i * i; j < MX; j += i)
            mn[j] = min(mn[j], i);
    }

    int qq; cin >> qq;

    for (; qq; qq--){
        int a, b, c, d;

        cin >> a >> b >> c >> d;

        bool ok = 1;

        for (int cr : prms){
            int fi = get_cnt(a, b, cr);
            int se = get_cnt(c, d, cr);

            if (fi > se){
                ok = 0;
                break;
            }
        }

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

    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 218 ms 43748 KB Output is correct
2 Correct 218 ms 43748 KB Output is correct
3 Correct 217 ms 43876 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 216 ms 43748 KB Output is correct
2 Correct 211 ms 43748 KB Output is correct
3 Correct 215 ms 43748 KB Output is correct
4 Correct 209 ms 43748 KB Output is correct
5 Correct 204 ms 43876 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 219 ms 43748 KB Output is correct
2 Correct 214 ms 43748 KB Output is correct
3 Correct 208 ms 43748 KB Output is correct
4 Correct 209 ms 43748 KB Output is correct
5 Correct 214 ms 43748 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 254 ms 43780 KB Output is correct
2 Correct 227 ms 43748 KB Output is correct
3 Correct 216 ms 43748 KB Output is correct
4 Correct 239 ms 43748 KB Output is correct
5 Correct 229 ms 43748 KB Output is correct
6 Correct 247 ms 43748 KB Output is correct
7 Correct 347 ms 43748 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 258 ms 43748 KB Output is correct
2 Correct 211 ms 43876 KB Output is correct
3 Correct 218 ms 43748 KB Output is correct
4 Correct 227 ms 43876 KB Output is correct
5 Correct 237 ms 43772 KB Output is correct
6 Correct 281 ms 43748 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 264 ms 43752 KB Output is correct
2 Correct 212 ms 43748 KB Output is correct
3 Correct 221 ms 43876 KB Output is correct
4 Correct 223 ms 43748 KB Output is correct
5 Correct 224 ms 43748 KB Output is correct
6 Correct 292 ms 43748 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 260 ms 43748 KB Output is correct
2 Correct 217 ms 43748 KB Output is correct
3 Correct 212 ms 43748 KB Output is correct
4 Correct 228 ms 43748 KB Output is correct
5 Correct 220 ms 43748 KB Output is correct
6 Correct 282 ms 43860 KB Output is correct
7 Correct 349 ms 43748 KB Output is correct