oj.uz

답안 #800097

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
800097 2023-08-01T10:09:05 Z detroiddh Radio (COCI22_radio) C++17
10 / 110
 1500 ms 110820 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

const ll maxn = 1e5 + 3;
const ll mod = 1e9 + 7;

int n, Q, prime[maxn];
bool vis[maxn];
multiset<int>st[4 * maxn];

void sang()
{
    for(int i = 1 ; i <= n ; ++i) prime[i] = i;

    for(ll i = 2 ; i <= n ; ++i)
    {
        if(prime[i] == i)
            for(ll j = i * i ; j <= n ; j += i)
                prime[j] = i;
    }
}

void constructST(int si, int l, int r)
{
    if(l == r)
    {
        while(l != 1)
        {
            int so = prime[l];
            st[si].insert(so);
            while(l % so == 0)
            {
                l /= so;
            }
        }
        return;
    }

    ll mid = (l + r) / 2;

    constructST(si * 2, l, mid);
    constructST(si * 2 + 1, mid + 1, r);
}

int get(int si, int sl, int sr, int l, int r)
{
    if(l <= sl && sr <= r)
    {
        auto it = st[si].begin();
        while(it != st[si].end())
        {
            int so = (*it);
            ++it;
            if(it != st[si].end() && (*it) == so)
            {
                return 1;
            }
        }
        return 0;
    }

    if(l > sr || r < sl) return 0;

    ll mid = (sl + sr) / 2;

    return get(si * 2, sl, mid, l, r) + get(si * 2 + 1, mid + 1, sr, l, r);
}

vector<int>q;
void update(int ty, int si, int sl, int sr, int pos)
{
    if(sl > pos || sr < pos) return;
    if(sl == sr)
    {
        for(auto it = st[si].begin() ; it != st[si].end() ; ++it)
            q.push_back((*it));
        return;
    }

    ll mid = (sl + sr)/2;
    update(ty, si * 2, sl, mid, pos);
    update(ty, si * 2 + 1, mid + 1, sr, pos);

    if(ty == 1) for(int so : q) st[si].insert(so);
    else for(int so : q) st[si].erase(st[si].find(so));
}

void sub2()
{
    sang();

    constructST(1, 1, n);

    while(Q--)
    {
        char ty;
        cin>>ty;

        if(ty == 'S')
        {
            int x;
            cin>>x;

            q.clear();
            vis[x] = 1 - vis[x];
            update(vis[x], 1, 1, n, x);
        }
        else
        {
            int l, r;
            cin>>l>>r;
            if(l == r)
            {
                cout<<"NE"<<'\n';
                continue;
            }

            int ans = get(1, 1, n, l, r);
            if(ans) cout<<"DA";
            else cout<<"NE";
            cout<<'\n';
        }
    }
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void sub1()
{
    while(Q--)
    {
        char ty;
        cin>>ty;

        if(ty == 'S')
        {
            int x;
            cin>>x;

            vis[x] = 1 - vis[x];
        }
        else
        {
            int l, r;
            cin>>l>>r;

            if(l == r)
            {
                cout<<"NE"<<'\n';
                continue;
            }

            for(int i = l ; i <= r ; ++i)
            {
                if(vis[i])
                {
                    for(int j = i + 1 ; j <= r ; ++j)
                        if(vis[j] && __gcd(i, j) != 1)
                        {
                            cout<<"DA"<<'\n';
                            goto done;
                        }
                }
            }

            cout<<"NE"<<'\n';
done:
            ;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("RADIO.INP","r",stdin);
//    freopen("RADIO.OUT","w",stdout);

    cin>>n>>Q;

    if(n <= 100 && Q <= 200) sub1();
    else sub2();
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 19112 KB Output is correct
2 Correct 10 ms 19116 KB Output is correct
3 Correct 10 ms 19096 KB Output is correct
4 Correct 11 ms 19000 KB Output is correct
5 Correct 12 ms 19028 KB Output is correct
6 Correct 10 ms 19116 KB Output is correct
7 Correct 9 ms 19116 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1584 ms 110820 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 19112 KB Output is correct
2 Correct 10 ms 19116 KB Output is correct
3 Correct 10 ms 19096 KB Output is correct
4 Correct 11 ms 19000 KB Output is correct
5 Correct 12 ms 19028 KB Output is correct
6 Correct 10 ms 19116 KB Output is correct
7 Correct 9 ms 19116 KB Output is correct
8 Execution timed out 1584 ms 110820 KB Time limit exceeded
9 Halted 0 ms 0 KB -