oj.uz

답안 #404035

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
404035 2021-05-13T17:09:48 Z ScarletS Vepar (COCI21_vepar) C++17
70 / 70
 1089 ms 1860 KB 
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;

const int mn = 1e7+1;
int t,a[10][4],s[10][2];
bitset<mn> composite;
bitset<10> bad;

void check()
{
    for (int i=0;i<t;++i)
    {
        if (s[i][0]>s[i][1])
            bad[i]=1;
        s[i][0]=s[i][1]=0;
    }
}

void sieve()
{
    int x,c;
    for (int i=2;i<mn;i+=2)
    {
        c=0;
        x=i;
        while (!(x&1))
        {
            ++c;
            x>>=1;
        }
        for (int j=0;j<t;++j)
        {
            if (a[j][0]<=i&&i<=a[j][1])
                s[j][0]+=c;
            if (a[j][2]<=i&&i<=a[j][3])
                s[j][1]+=c;
        }
    }
    check();
    for (int i=3;i<mn;i+=2)
        if (!composite[i])
        {
            for (int j=i;j<mn;j+=i)
            {
                composite[j]=1;
                c=0;
                x=j;
                while (!(x%i))
                {
                    ++c;
                    x/=i;
                }
                for (int k=0;k<t;++k)
                {
                    if (a[k][0]<=j&&j<=a[k][1])
                        s[k][0]+=c;
                    if (a[k][2]<=j&&j<=a[k][3])
                        s[k][1]+=c;
                }
            }
            check();
        }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>t;
    for (int i=0;i<t;++i)
        for (int j=0;j<4;++j)
            cin>>a[i][j];
    sieve();
    for (int i=0;i<t;++i)
    {
        if (bad[i])
            cout<<"NE\n";
        else
            cout<<"DA\n";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1037 ms 1520 KB Output is correct
2 Correct 1044 ms 1604 KB Output is correct
3 Correct 1035 ms 1576 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 993 ms 1512 KB Output is correct
2 Correct 1031 ms 1516 KB Output is correct
3 Correct 1037 ms 1516 KB Output is correct
4 Correct 1035 ms 1588 KB Output is correct
5 Correct 1046 ms 1612 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1006 ms 1520 KB Output is correct
2 Correct 1049 ms 1516 KB Output is correct
3 Correct 1034 ms 1416 KB Output is correct
4 Correct 1031 ms 1860 KB Output is correct
5 Correct 1041 ms 1568 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1018 ms 1516 KB Output is correct
2 Correct 1012 ms 1588 KB Output is correct
3 Correct 963 ms 1604 KB Output is correct
4 Correct 1006 ms 1512 KB Output is correct
5 Correct 994 ms 1520 KB Output is correct
6 Correct 712 ms 1604 KB Output is correct
7 Correct 852 ms 1480 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1002 ms 1548 KB Output is correct
2 Correct 1032 ms 1508 KB Output is correct
3 Correct 1026 ms 1580 KB Output is correct
4 Correct 1033 ms 1524 KB Output is correct
5 Correct 1045 ms 1520 KB Output is correct
6 Correct 978 ms 1516 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1034 ms 1516 KB Output is correct
2 Correct 1035 ms 1512 KB Output is correct
3 Correct 1035 ms 1512 KB Output is correct
4 Correct 1027 ms 1516 KB Output is correct
5 Correct 1029 ms 1580 KB Output is correct
6 Correct 995 ms 1516 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1026 ms 1516 KB Output is correct
2 Correct 1034 ms 1520 KB Output is correct
3 Correct 1089 ms 1516 KB Output is correct
4 Correct 1066 ms 1520 KB Output is correct
5 Correct 1035 ms 1536 KB Output is correct
6 Correct 979 ms 1512 KB Output is correct
7 Correct 834 ms 1592 KB Output is correct