oj.uz

Submission #799989

# Submission time Handle Problem Language Result Execution time Memory
799989 2023-08-01T09:10:00 Z vjudge1 Radio (COCI22_radio) C++17
110 / 110
 1370 ms 197828 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=1e6+9;
vector<int>pr[maxn];
set<int>a[maxn];
set<int>::iterator it;
multiset<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(const 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()&&!a[v].empty())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(const 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()&&!a[v].empty())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 51 ms 117624 KB Output is correct
2 Correct 51 ms 117660 KB Output is correct
3 Correct 51 ms 117740 KB Output is correct
4 Correct 52 ms 117716 KB Output is correct
5 Correct 51 ms 117740 KB Output is correct
6 Correct 51 ms 117672 KB Output is correct
7 Correct 53 ms 117612 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 132948 KB Output is correct
2 Correct 943 ms 166524 KB Output is correct
3 Correct 1218 ms 193100 KB Output is correct
4 Correct 82 ms 121932 KB Output is correct
5 Correct 320 ms 138272 KB Output is correct
6 Correct 630 ms 158956 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 117624 KB Output is correct
2 Correct 51 ms 117660 KB Output is correct
3 Correct 51 ms 117740 KB Output is correct
4 Correct 52 ms 117716 KB Output is correct
5 Correct 51 ms 117740 KB Output is correct
6 Correct 51 ms 117672 KB Output is correct
7 Correct 53 ms 117612 KB Output is correct
8 Correct 405 ms 132948 KB Output is correct
9 Correct 943 ms 166524 KB Output is correct
10 Correct 1218 ms 193100 KB Output is correct
11 Correct 82 ms 121932 KB Output is correct
12 Correct 320 ms 138272 KB Output is correct
13 Correct 630 ms 158956 KB Output is correct
14 Correct 220 ms 118020 KB Output is correct
15 Correct 410 ms 125840 KB Output is correct
16 Correct 1351 ms 197828 KB Output is correct
17 Correct 1158 ms 190324 KB Output is correct
18 Correct 1370 ms 194280 KB Output is correct
19 Correct 1255 ms 194076 KB Output is correct
20 Correct 585 ms 159000 KB Output is correct
21 Correct 583 ms 158976 KB Output is correct
22 Correct 647 ms 158940 KB Output is correct
23 Correct 582 ms 158972 KB Output is correct