oj.uz

Submission #877810

# Submission time Handle Problem Language Result Execution time Memory
877810 2023-11-23T15:11:04 Z Ahmed_Solyman Radio (COCI22_radio) C++14
110 / 110
 1434 ms 276304 KB 
/*
In the name of Allah
made by: Ahmed_Solyman
*/
#include <bits/stdc++.h>
#include <ext/rope>
 
using namespace std;
using namespace __gnu_cxx;
#pragma GCC optimize("-Ofast")
#pragma GCC optimize("-O1")
//-------------------------------------------------------------//
typedef long long ll;
typedef unsigned long long ull;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PI acos(-1)
#define lb lower_bound
#define ub upper_bound
#define endl '\n'
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define sum_to(n) (n*(n+1))/2
#define pb push_back
#define pf push_front
#define fil(arr,x) memset(arr,x,sizeof(arr))
const ll mod=1e9+7;
int dx[8]={0,1,0,-1,1,1,-1,-1};
int dy[8]={1,0,-1,0,1,-1,-1,1};
//-------------------------------------------------------------//
ll lcm(ll a,ll b)
{
    return (max(a,b)/__gcd(a,b))*min(a,b);
}
void person_bool(bool x)
{
    cout<<(x?"DA":"NE")<<endl;
}
const int N=1e6+5;
vector<int>p[N];
struct segtree{
    vector<ll>tree;
    int size;
    void init(int n){
        size=n;
        tree.assign(n*4+5,0LL);
    }
    void set(int l,int r,int p,int i,int v){
        if(l==r){
            tree[p]=v;
            return;
        }
        int mid=(l+r)/2;
        if(i>mid)set(mid+1,r,p*2+1,i,v);
        else set(l,mid,p*2,i,v);
        tree[p]=max(tree[p*2],tree[p*2+1]);
    }
    void set(int i,int v){
        set(1,size,1,i,v);
    }
    ll query(int l,int r,int p,int l_q,int r_q){
        if(l>=l_q && r<=r_q){
            return tree[p];
        }
        if(r<l_q || l>r_q){
            return 0;
        }
        int mid=(l+r)/2;
        return max(query(l,mid,p*2,l_q,r_q),query(mid+1,r,p*2+1,l_q,r_q));
    }
    ll query(int l,int r){
        return query(1,size,1,l,r);
    }
}s;
set<int>a[N],c[N];
vector<int>b[N];
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    #ifndef ONLINE_JUDGE
 // /  freopen("input.in", "r", stdin);
    ///freopen("output.out", "w", stdout);
    #endif
    fast
    int n,q;cin>>n>>q;
    s.init(n);
    for(int i=2;i<=n;i++){
        if(p[i].size()==0){
            for(int j=i;j<=n;j+=i){
                p[j].push_back(i);
            }
        }
    }
    vector<int>state(n+5);
    vector<int>v(n+5);
    while(q--){
        char t;cin>>t;
        if(t=='S'){
            int x;cin>>x;
            state[x]=1-state[x];
            if(state[x]){
                for(auto i:p[x]){
                    auto j=c[i].upper_bound(x);
                    if(j!=c[i].begin()){
                        j--;
                        a[x].insert(*j);
                        b[*j].pb(x);
                        v[x]=*(--a[x].end());
                        s.set(x,v[x]);
                        j++;
                    }
                    if(j!=c[i].end()){
                        a[*j].insert(x);
                        b[x].pb(*j);
                        v[*j]=*(--a[*j].end());
                        s.set(*j,v[*j]);
                    }
                    c[i].insert(x);
                }
            }
            else{
                for(auto i:b[x]){
                    a[i].erase(x);
                    if(!a[i].size())a[i].insert(0);
                    v[i]=*(--a[i].end());
                    s.set(i,v[i]);
                }
                b[x].clear();
                a[x].clear();
                a[x].insert(0);
                v[x]=0;
                s.set(x,0);
                for(auto i:p[x]){
                    c[i].erase(x);
                    auto j=c[i].upper_bound(x);
                    if(j!=c[i].end()){
                        a[*j].erase(x);
                        if(j!=c[i].begin()){
                            auto k=j;k--;
                            a[*j].insert(*k);
                            b[*k].pb(*j);
                        }
                        if(!a[*j].size()){
                            a[*j].insert(0);
                        }
                        v[*j]=*(--a[*j].end());
                        s.set(*j,v[*j]);
                    }
                }
            }
        }
        else{
            int a,b;cin>>a>>b;
            person_bool(s.query(a, b)>=a);
        }
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 141148 KB Output is correct
2 Correct 28 ms 141148 KB Output is correct
3 Correct 29 ms 141336 KB Output is correct
4 Correct 29 ms 141148 KB Output is correct
5 Correct 29 ms 141148 KB Output is correct
6 Correct 29 ms 141148 KB Output is correct
7 Correct 28 ms 141136 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 167628 KB Output is correct
2 Correct 1018 ms 223012 KB Output is correct
3 Correct 1260 ms 266944 KB Output is correct
4 Correct 47 ms 148560 KB Output is correct
5 Correct 178 ms 178048 KB Output is correct
6 Correct 396 ms 214924 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 141148 KB Output is correct
2 Correct 28 ms 141148 KB Output is correct
3 Correct 29 ms 141336 KB Output is correct
4 Correct 29 ms 141148 KB Output is correct
5 Correct 29 ms 141148 KB Output is correct
6 Correct 29 ms 141148 KB Output is correct
7 Correct 28 ms 141136 KB Output is correct
8 Correct 571 ms 167628 KB Output is correct
9 Correct 1018 ms 223012 KB Output is correct
10 Correct 1260 ms 266944 KB Output is correct
11 Correct 47 ms 148560 KB Output is correct
12 Correct 178 ms 178048 KB Output is correct
13 Correct 396 ms 214924 KB Output is correct
14 Correct 294 ms 143428 KB Output is correct
15 Correct 641 ms 158852 KB Output is correct
16 Correct 1434 ms 276304 KB Output is correct
17 Correct 1183 ms 264396 KB Output is correct
18 Correct 1322 ms 270380 KB Output is correct
19 Correct 1311 ms 270488 KB Output is correct
20 Correct 390 ms 216380 KB Output is correct
21 Correct 387 ms 216284 KB Output is correct
22 Correct 379 ms 216408 KB Output is correct
23 Correct 385 ms 216400 KB Output is correct