oj.uz

Submission #555228

# Submission time Handle Problem Language Result Execution time Memory
555228 2022-04-30T09:48:57 Z BT21tata Radio (COCI22_radio) C++17
30 / 110
 397 ms 61152 KB 
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define SPEED ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0)
#define rall(v) (v).rbegin(),(v).rend()
#define all(v) (v).begin(),(v).end()
#define setp fixed<<setprecision
#define OK cerr<<"OK"<<endl<<flush
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define F first
#define S second
#define y0 jahdakdh
#define y1 jahsadakdakdh
#define endl '\n'
const ll MOD=1e9+7;
const ll mod=(1ll<<31)-1;
const ld eps=1e-8;
using namespace std;
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());

bool a[1000005];
vector<int>primes[1000005];
int cnt, pr[1000005], n, Q;

int main()
{
    SPEED;
    for(ll i=2; i<=1000000; i++)
    {
        if(pr[i]==0)
        {
            for(ll j=i; j<=1000000; j+=i)
            {
                primes[j].pb(i);
                pr[j]=1;
            }
        }
    }

    memset(pr, 0, sizeof(pr));

    cin>>n>>Q;
    while(Q--)
    {
        char q;
        int x;
        cin>>q>>x;
        if(q=='S')
        {
            if(a[x]==0)
            {
                a[x]=1;
                for(int u : primes[x])
                {
                    pr[u]++;
                    //cout<<u<<' '<<x<<' '<<pr[u]<<endl;
                    if(pr[u]==2) cnt++;
                }
            }
            else
            {
                a[x]=0;
                for(int u : primes[x])
                {
                    pr[u]--;
                    if(pr[u]==1) cnt--;
                }
            }
        }
        else
        {
            cin>>x;
            if(cnt) cout<<"DA\n";
            else cout<<"NE\n";
        }
    }    
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 339 ms 59724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 60144 KB Output is correct
2 Correct 397 ms 60784 KB Output is correct
3 Correct 391 ms 61052 KB Output is correct
4 Correct 357 ms 59980 KB Output is correct
5 Correct 351 ms 60616 KB Output is correct
6 Correct 367 ms 61152 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 339 ms 59724 KB Output isn't correct
2 Halted 0 ms 0 KB -