oj.uz

Submission #799987

# Submission time Handle Problem Language Result Execution time Memory
799987 2023-08-01T09:09:37 Z vjudge1 Radio (COCI22_radio) C++17
110 / 110
 942 ms 208252 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
const ll maxN=1e6+10;
vector<pair<ll,ll>>vec[maxN];
set<int>s[maxN];
set<int>::iterator it;
#define fi first
#define se second
ll n;
ll st[4*maxN];
void update(ll pos,ll val,ll id=1,ll l=1,ll r=n)
{
    if(l==r)
    {
        st[id]=val;
        return;
    }
    ll mid=l+r>>1;
    if(pos<=mid) update(pos,val,id*2,l,mid);
    else update(pos,val,id*2+1,mid+1,r);
    st[id]=min(st[id*2],st[id*2+1]);
}
ll get(ll i,ll j,ll id=1,ll l=1,ll r=n)
{
    if(j<l||r<i) return n+1;
    if(i<=l&&r<=j) return st[id];
    ll mid=l+r>>1;
    return min(get(i,j,id*2,l,mid),get(i,j,id*2+1,mid+1,r));
}
void add(ll x)
{
    for(auto &cc:vec[x])
    {
        ll u=cc.fi;
        it=s[u].lower_bound(x);
        if(it==s[u].end()) cc.se=n+1;
        else cc.se=*it;
        if(it!=s[u].begin()&&s[u].size()>0)
        {
            it--;
            ll y=*it;
            for(auto &vc:vec[y])
            {
                if(vc.fi==u) vc.se=x;
            }
            ll mn=n+1;
            for(auto &vc:vec[y]) mn=min(mn,vc.se);
            update(y,mn);
        }
        s[u].insert(x);
    }
    ll mn=n+1;
    for(auto cc:vec[x]) mn=min(mn,cc.se);
    update(x,mn);
}
void del(ll x)
{
    for(auto &cc:vec[x])
    {
        ll u=cc.fi;
        it=s[u].lower_bound(x);
        ll nxt=cc.se;
        cc.se=n+1;
        if(it!=s[u].begin()&&s[u].size()>0)
        {
            it--;
            ll y=*it;
            for(auto &vc:vec[y])
            {
                if(vc.fi==u) vc.se=nxt;
            }
            ll mn=n+1;
            for(auto &vc:vec[y]) mn=min(mn,vc.se);
            update(y,mn);
        }
        s[u].erase(x);
    }
    update(x,n+1);
}
ll q,p[maxN];
#define pb push_back
int in[maxN];
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen( Task".INP", "r", stdin);
    //freopen( Task".OUT", "w", stdout);
    cin >> n >> q;
    for(int i=1;i<=n;i++) in[i]=0;
    for(int i=2;i<=n;i++)
    {
        p[i]=i;
    }
    for(int i=2;i<=n;i++)
    {
        if(p[i]==i)
        {
            for(int j=2*i;j<=n;j+=i)
            {
                p[j]=min(p[j],i);
            }
        }
    }
    for(int i=2;i<=n;i++)
    {
        ll j=i;
        while(j>1)
        {
            ll x=p[j];
            while(p[j]==x)
            {
                j/=x;
            }
            vec[i].pb({x,n+1});
        }
    }
    fill(st,st+4*maxN,n+1);
    while(q--)
    {
        char t;
        cin >> t;
        if(t=='S')
        {
            ll x;
            cin >> x;
            in[x]^=1;
            if(in[x]) add(x);
            else del(x);
        }
        else
        {
            ll l,r;
            cin >> l >> r;
            cout << (get(l,r)<=r?"DA":"NE")<<'\n';
        }
    }
}

Compilation message

Main.cpp: In function 'void update(ll, ll, ll, ll, ll)':
Main.cpp:20:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |     ll mid=l+r>>1;
      |            ~^~
Main.cpp: In function 'll get(ll, ll, ll, ll, ll)':
Main.cpp:29:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     ll mid=l+r>>1;
      |            ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 102048 KB Output is correct
2 Correct 43 ms 102024 KB Output is correct
3 Correct 43 ms 101992 KB Output is correct
4 Correct 42 ms 102020 KB Output is correct
5 Correct 46 ms 102032 KB Output is correct
6 Correct 46 ms 101980 KB Output is correct
7 Correct 42 ms 102096 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 115684 KB Output is correct
2 Correct 629 ms 159532 KB Output is correct
3 Correct 763 ms 205484 KB Output is correct
4 Correct 62 ms 110248 KB Output is correct
5 Correct 170 ms 144252 KB Output is correct
6 Correct 264 ms 187564 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 102048 KB Output is correct
2 Correct 43 ms 102024 KB Output is correct
3 Correct 43 ms 101992 KB Output is correct
4 Correct 42 ms 102020 KB Output is correct
5 Correct 46 ms 102032 KB Output is correct
6 Correct 46 ms 101980 KB Output is correct
7 Correct 42 ms 102096 KB Output is correct
8 Correct 321 ms 115684 KB Output is correct
9 Correct 629 ms 159532 KB Output is correct
10 Correct 763 ms 205484 KB Output is correct
11 Correct 62 ms 110248 KB Output is correct
12 Correct 170 ms 144252 KB Output is correct
13 Correct 264 ms 187564 KB Output is correct
14 Correct 164 ms 103632 KB Output is correct
15 Correct 359 ms 110860 KB Output is correct
16 Correct 942 ms 208252 KB Output is correct
17 Correct 765 ms 204648 KB Output is correct
18 Correct 837 ms 206544 KB Output is correct
19 Correct 784 ms 206504 KB Output is correct
20 Correct 301 ms 187572 KB Output is correct
21 Correct 277 ms 187624 KB Output is correct
22 Correct 317 ms 187660 KB Output is correct
23 Correct 268 ms 187624 KB Output is correct