oj.uz

Submission #802014

# Submission time Handle Problem Language Result Execution time Memory
802014 2023-08-02T09:05:34 Z detroiddh Radio (COCI22_radio) C++17
110 / 110
 994 ms 143788 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70732 KB Output is correct
2 Correct 30 ms 70780 KB Output is correct
3 Correct 30 ms 70716 KB Output is correct
4 Correct 30 ms 70700 KB Output is correct
5 Correct 31 ms 70696 KB Output is correct
6 Correct 30 ms 70772 KB Output is correct
7 Correct 36 ms 70708 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 81592 KB Output is correct
2 Correct 573 ms 111956 KB Output is correct
3 Correct 830 ms 141428 KB Output is correct
4 Correct 56 ms 76160 KB Output is correct
5 Correct 183 ms 97256 KB Output is correct
6 Correct 433 ms 123588 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70732 KB Output is correct
2 Correct 30 ms 70780 KB Output is correct
3 Correct 30 ms 70716 KB Output is correct
4 Correct 30 ms 70700 KB Output is correct
5 Correct 31 ms 70696 KB Output is correct
6 Correct 30 ms 70772 KB Output is correct
7 Correct 36 ms 70708 KB Output is correct
8 Correct 253 ms 81592 KB Output is correct
9 Correct 573 ms 111956 KB Output is correct
10 Correct 830 ms 141428 KB Output is correct
11 Correct 56 ms 76160 KB Output is correct
12 Correct 183 ms 97256 KB Output is correct
13 Correct 433 ms 123588 KB Output is correct
14 Correct 179 ms 71208 KB Output is correct
15 Correct 343 ms 76712 KB Output is correct
16 Correct 994 ms 143788 KB Output is correct
17 Correct 862 ms 139992 KB Output is correct
18 Correct 945 ms 141968 KB Output is correct
19 Correct 885 ms 142012 KB Output is correct
20 Correct 423 ms 123584 KB Output is correct
21 Correct 446 ms 123616 KB Output is correct
22 Correct 433 ms 123544 KB Output is correct
23 Correct 424 ms 123612 KB Output is correct