oj.uz

Submission #799982

# Submission time Handle Problem Language Result Execution time Memory
799982 2023-08-01T09:06:50 Z vjudge1 Radio (COCI22_radio) C++17
10 / 110
 223 ms 66736 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
const ll maxN=2e5+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 10 ms 20692 KB Output is correct
2 Correct 10 ms 20692 KB Output is correct
3 Correct 10 ms 20692 KB Output is correct
4 Correct 9 ms 20692 KB Output is correct
5 Correct 11 ms 20692 KB Output is correct
6 Correct 9 ms 20696 KB Output is correct
7 Correct 10 ms 20692 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 34612 KB Output is correct
2 Runtime error 59 ms 66736 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20692 KB Output is correct
2 Correct 10 ms 20692 KB Output is correct
3 Correct 10 ms 20692 KB Output is correct
4 Correct 9 ms 20692 KB Output is correct
5 Correct 11 ms 20692 KB Output is correct
6 Correct 9 ms 20696 KB Output is correct
7 Correct 10 ms 20692 KB Output is correct
8 Correct 223 ms 34612 KB Output is correct
9 Runtime error 59 ms 66736 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -