oj.uz

Submission #800885

# Submission time Handle Problem Language Result Execution time Memory
800885 2023-08-02T01:20:47 Z amogususus Radio (COCI22_radio) C++17
40 / 110
 1500 ms 9936 KB 
#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2")
#include<iostream>
#include<bitset>
#include<algorithm>
#include<numeric>
#define ll int
#define endl '\n'
#define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
using namespace std;
const int maxN=1000001;
const int mod=1e9+7;
ll n,q;
ll spf[maxN],c[maxN];
bitset<maxN> a;
void Enter(){
    cin>>n>>q;
    ll cnt=0;
    while(q--){
        char t;
        ll u,v;
        cin>>t>>u;
        if(t=='S'){
            if(a[u]){
                a[u]=0;
                while(u!=1){
                    ll x=spf[u];
                    while(u%x==0)u/=x;
                    if(c[x]==2)cnt--;
                    c[x]--;
                }
            } else {
                a[u]=1;
                while(u!=1){
                    ll x=spf[u];
                    while(u%x==0)u/=x;
                    if(c[x]==1)cnt++;
                    c[x]++;
                }
            }
        } else {
            cin>>v;
            if(u==1&&v==n)cout<<(cnt?"DA":"NE")<<endl;
            else {
                bool f=0;
                for(int i=a._Find_next(u-1);i<v;i=a._Find_next(i))
                    for(int j=a._Find_next(i);j<=v;j=a._Find_next(j))
                        if(__gcd(i,j)!=1){f=1;i=v+1;break;}
                cout<<(f?"DA":"NE")<<endl;
            }
        }
    }
}
//amogus
signed main(){
    iota(spf,spf+maxN,0);
    for(int i=2;i<maxN;i++)if(spf[i]==i)for(int j=i*2;j<maxN;j+=i)spf[j]=i;
    open("RADIO");
    cin.tie(nullptr);ios_base::sync_with_stdio(NULL);
    //int t=1;cin>>t;while(t--)
    Enter();
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:9:54: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:58:5: note: in expansion of macro 'open'
   58 |     open("RADIO");
      |     ^~~~
Main.cpp:9:87: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:58:5: note: in expansion of macro 'open'
   58 |     open("RADIO");
      |     ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4180 KB Output is correct
2 Correct 5 ms 4180 KB Output is correct
3 Correct 5 ms 4180 KB Output is correct
4 Correct 5 ms 4180 KB Output is correct
5 Correct 5 ms 4180 KB Output is correct
6 Correct 5 ms 4244 KB Output is correct
7 Correct 5 ms 4220 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4680 KB Output is correct
2 Correct 31 ms 7680 KB Output is correct
3 Correct 41 ms 9792 KB Output is correct
4 Correct 7 ms 4820 KB Output is correct
5 Correct 16 ms 6996 KB Output is correct
6 Correct 24 ms 9684 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4180 KB Output is correct
2 Correct 5 ms 4180 KB Output is correct
3 Correct 5 ms 4180 KB Output is correct
4 Correct 5 ms 4180 KB Output is correct
5 Correct 5 ms 4180 KB Output is correct
6 Correct 5 ms 4244 KB Output is correct
7 Correct 5 ms 4220 KB Output is correct
8 Correct 22 ms 4680 KB Output is correct
9 Correct 31 ms 7680 KB Output is correct
10 Correct 41 ms 9792 KB Output is correct
11 Correct 7 ms 4820 KB Output is correct
12 Correct 16 ms 6996 KB Output is correct
13 Correct 24 ms 9684 KB Output is correct
14 Correct 58 ms 5528 KB Output is correct
15 Correct 577 ms 6128 KB Output is correct
16 Execution timed out 1563 ms 9936 KB Time limit exceeded
17 Halted 0 ms 0 KB -