oj.uz

Submission #799970

# Submission time Handle Problem Language Result Execution time Memory
799970 2023-08-01T08:57:38 Z vjudge1 Radio (COCI22_radio) C++17
10 / 110
 438 ms 27472 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=1e5+9;
vector<int>pr[maxn];
set<int>a[maxn];
set<int>::iterator it;
set<int>c[maxn];
bool b[maxn];
int n,q;
int st[maxn*4];
void update(int id,int l,int r,int u,int val){
if (l>u||r<u)return;
if (l==r){
    st[id]=val;
    return;
}
int mid=(l+r)/2;
update(id*2,l,mid,u,val);
update(id*2+1,mid+1,r,u,val);
st[id]=min(st[id*2],st[id*2+1]);
}
int get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return n+1;
if (u<=l&&r<=v)return st[id];
int mid=(l+r)/2;
return min(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
void add(int x){
b[x]=1;
for (auto v:pr[x]){
    it=a[v].upper_bound(x);
    int l=0,r=n+1;
    if (it!=a[v].end())r=(*it);
    if (it!=a[v].begin()){
        it--;
        l=(*it);
    }
    if (l!=0){
        if (r!=n+1){
            c[l].erase(r);
        }
        c[l].insert(x);
        update(1,1,n,l,*c[l].begin());
    }
    if (r!=n+1){
        c[x].insert(r);
    }
}
for (auto v:pr[x])a[v].insert(x);
if (c[x].empty())update(1,1,n,x,n+1);
else update(1,1,n,x,*c[x].begin());
}
void del(int x){
b[x]=0;
for (auto v:pr[x]){
    a[v].erase(x);
    it=a[v].upper_bound(x);
    int l=0,r=n+1;
    if (it!=a[v].end())r=(*it);
    if (it!=a[v].begin()){
        it--;
        l=(*it);
    }
    if (l!=0){
        c[l].erase(x);
        if (r!=n+1){
            c[l].insert(r);
        }
        if (c[l].empty())update(1,1,n,l,n+1);
        else update(1,1,n,l,*c[l].begin());
    }
}
c[x].clear();
update(1,1,n,x,n+1);
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("RADIO.INP","r",stdin);
    //freopen("RADIO.OUT","w",stdout);
    cin>>n>>q;
    for1(i,2,n){
    if (pr[i].empty()){
        for3(j,i,n,i){
        pr[j].pb(i);
        }
    }
    }
    for1(i,1,n){
    update(1,1,n,i,n+1);
    }
    for1(i,1,q){
    char r;
    cin>>r;
    if (r=='S'){
        int x;
        cin>>x;
        if (b[x])del(x);
        else add(x);
    }
    else {
        int l,r;
        cin>>l>>r;
        if (get(1,1,n,l,r)<=r)cout<<"DA"<<'\n';
        else cout<<"NE"<<'\n';
    }
    }

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 12068 KB Output is correct
4 Correct 5 ms 12072 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 7 ms 12076 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 27248 KB Output is correct
2 Runtime error 17 ms 27472 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 5 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 12068 KB Output is correct
4 Correct 5 ms 12072 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 7 ms 12076 KB Output is correct
8 Correct 438 ms 27248 KB Output is correct
9 Runtime error 17 ms 27472 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -