oj.uz

Submission #750467

# Submission time Handle Problem Language Result Execution time Memory
750467 2023-05-29T14:26:35 Z bgnbvnbv Radio (COCI22_radio) C++14
110 / 110
 995 ms 151572 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=int;
const ll maxN=1e6+10;
const ll inf=1e18;
const ll mod=1e9+7;
vector<pli>vec[maxN];
set<int>s[maxN];
set<int>::iterator it;
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 &zz:vec[x])
    {
        ll v=zz.fi;
        it=s[v].lower_bound(x);
        if(it!=s[v].end())
        {
            zz.se=*it;
        }
        else zz.se=n+1;
        if(it!=s[v].begin())
        {
            it--;
            ll cc=*it;
            ll mn=n+1;
            for(auto &vv:vec[cc])
            {
                if(vv.fi==v) vv.se=min(vv.se,x);
                mn=min(mn,vv.se);
            }
            //cout << x<<' '<<cc<<' '<<mn<<'\n';
            update(cc,mn);
        }
        s[v].insert(x);
    }
    ll mn=n+1;
    for(auto &zz:vec[x]) mn=min(mn,zz.se);
    update(x,mn);
}
void ers(ll x)
{
    for(auto &zz:vec[x])
    {
        ll v=zz.fi;
        it=s[v].upper_bound(x);
        ll val=n+1;
        if(it!=s[v].end()) val=*it;
        it--;
        if(it!=s[v].begin())
        {
            it--;
            ll cc=*it;
            ll mn=n+1;
            for(auto &vv:vec[cc])
            {
                if(vv.fi==v) vv.se=val;
                mn=min(mn,vv.se);
            }
            update(cc,mn);
        }
        s[v].erase(x);
        zz.se=n+1;
    }
    ll mn=n+1;
    for(auto &zz:vec[x]) mn=min(mn,zz.se);
    update(x,n+1);
}
ll q;
ll p[maxN];
ll in[maxN];
void solve()
{
    cin >> n >> q;
    for(int i=1;i<=n;i++) p[i]=i;
    p[1]=0;
    for(int i=1;i<=n;i++) update(i,n+1),in[i]=0;
    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=1;i<=n;i++)
    {
        ll x=i;
        while(x>1)
        {
            ll c=p[x];
            while(p[x]==c) x/=c;
            vec[i].pb({c,n+1});
        }
    }
    while(q--)
    {
        char t;
        cin >> t;
        if(t=='S')
        {
            ll x;
            cin >> x;
            if(in[x]==0)
            {
                in[x]=1;
                add(x);
            }
            else
            {
                in[x]=0;
                ers(x);
            }
        }
        else
        {
            ll l,r;
            cin >> l >> r;
            if(get(l,r)>r) cout << "NE\n";
            else cout <<"DA\n";
        }
    }
    //cout << get(1,6)<<'\n';
    //for(auto zz:vec[3]) cout << zz.se<<'\n';
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

Main.cpp:11:14: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   11 | const ll inf=1e18;
      |              ^~~~
Main.cpp: In function 'void update(ll, ll, ll, ll, ll)':
Main.cpp:25:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     ll mid=l+r>>1;
      |            ~^~
Main.cpp: In function 'll get(ll, ll, ll, ll, ll)':
Main.cpp:34:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     ll mid=l+r>>1;
      |            ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70732 KB Output is correct
2 Correct 34 ms 70732 KB Output is correct
3 Correct 33 ms 70768 KB Output is correct
4 Correct 33 ms 70732 KB Output is correct
5 Correct 32 ms 70764 KB Output is correct
6 Correct 36 ms 70740 KB Output is correct
7 Correct 42 ms 70740 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 83424 KB Output is correct
2 Correct 734 ms 115876 KB Output is correct
3 Correct 964 ms 148768 KB Output is correct
4 Correct 65 ms 76864 KB Output is correct
5 Correct 197 ms 100536 KB Output is correct
6 Correct 401 ms 130824 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70732 KB Output is correct
2 Correct 34 ms 70732 KB Output is correct
3 Correct 33 ms 70768 KB Output is correct
4 Correct 33 ms 70732 KB Output is correct
5 Correct 32 ms 70764 KB Output is correct
6 Correct 36 ms 70740 KB Output is correct
7 Correct 42 ms 70740 KB Output is correct
8 Correct 366 ms 83424 KB Output is correct
9 Correct 734 ms 115876 KB Output is correct
10 Correct 964 ms 148768 KB Output is correct
11 Correct 65 ms 76864 KB Output is correct
12 Correct 197 ms 100536 KB Output is correct
13 Correct 401 ms 130824 KB Output is correct
14 Correct 193 ms 72404 KB Output is correct
15 Correct 369 ms 78448 KB Output is correct
16 Correct 995 ms 151572 KB Output is correct
17 Correct 903 ms 148192 KB Output is correct
18 Correct 964 ms 149908 KB Output is correct
19 Correct 893 ms 149860 KB Output is correct
20 Correct 400 ms 130824 KB Output is correct
21 Correct 370 ms 130952 KB Output is correct
22 Correct 378 ms 130960 KB Output is correct
23 Correct 421 ms 130932 KB Output is correct