Submission #802014

#	Time	Username	Problem	Language	Result	Execution time	Memory
802014		detroiddh	Radio (COCI22_radio)	C++17	110 / 110	994 ms	143788 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

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

int n, Q, xa[maxn];
bool on[maxn];
vector<int>prime[maxn];
set<int>s[maxn];
int st[4 * maxn];

void sang()
{
    for(ll i = 2 ; i <= n ; ++i)
    {
        if(prime[i].empty())
        {
            for(ll j = i ; j <= n ; j += i)
            {
                prime[j].push_back(i);
            }
        }
    }
}

int get(int si, int sl, int sr, int l, int r)
{
    if(l <= sl && sr <= r) return st[si];

    if(l > sr || r < sl) return n + 1;

    ll mid = (sl + sr) / 2;

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

void update(int si, int sl, int sr, int pos, ll dif)
{
    if(sl > pos || sr < pos) return;
    if(sl == sr)
    {
        st[si] = dif;
        return;
    }

    ll mid = (sl + sr) / 2;
    if(pos <= mid) update(si * 2 , sl , mid , pos , dif);
    else update(si * 2 + 1 , mid + 1 , sr , pos , dif);

    st[si] = min(st[si * 2] , st[si * 2 + 1]);
}

void solve()
{
    sang();

    fill(xa + 1, xa + n + 1 , n + 1);
    fill(st + 1, st + 4 * n + 1 , n + 1);

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

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

            on[x] = 1 - on[x];

            if(on[x])
            {
                for(int i : prime[x])
                {
                    auto it = s[i].upper_bound(x);
                    if(it != s[i].end()) xa[x] = min(xa[x], (*it));
                    if(it != s[i].begin())
                    {
                        --it;
                        xa[(*it)] = min(xa[(*it)], x);

                        update(1 , 1 , n , (*it) , xa[(*it)]);
                    }
                    s[i].insert(x);
                }

                update(1 , 1 , n , x , xa[x]);

                //if(x != 2) for(int i = 1 ; i <= 4 * n ; ++i) cout<<st[i]<<" ";
            }
            else
            {
                xa[x] = n + 1;
                update(1 , 1 , n , x , xa[x]);

                //if(x == 2) for(int i = 1 ; i <= 4 * n ; ++i) cout<<st[i]<<" ";

                for(int i : prime[x])
                {
                    s[i].erase(x);
                    auto it = s[i].upper_bound(x);

                    if(it != s[i].begin())
                    {
                        --it;
                        xa[(*it)] = n + 1;
                        for(int j : prime[(*it)])
                        {
                            auto t = s[j].upper_bound((*it));
                            if(t != s[j].end()) xa[(*it)] = min(xa[(*it)], (*t));
                        }

                        update(1 , 1 , n , (*it) , xa[(*it)]);
                    }
                }
            }
        }
        else
        {
            int l, r;
            cin>>l>>r;

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

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

    cin>>n>>Q;

    solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70