oj.uz

Submission #572274

# Submission time Handle Problem Language Result Execution time Memory
572274 2022-06-04T07:34:00 Z Asylzhan Radio (COCI22_radio) C++17
0 / 110
 1500 ms 25732 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"
#define all(a) a.begin(), a.end()
#define sp ' '
#define ff first
#define ss second
#define vt vector
#define pb push_back

const int MOD = 998244353;
const int inf = 1e9 + 7;
const ll  INF = 9e18;
const int N   = 1e6 + 5;

/*-------------------------main-------------------------*/

bool a[N];
map <ll, ll> mp;

void solve(){
    #define test
    int n, q;
    cin >> n >> q;
    set <ll> s;
    while (q--){
        char u;
        cin >> u;
        if (u == 'S'){
            int p;
            cin >> p;
            if (!a[p]){
                a[p] = 1;
                for (int i = 1; i * i <= p; i++){
                    if (p % i == 0){
                        if (i > 1){
                            if (mp[i]) s.insert(i);
                            mp[i]++;
                        }
                        int x = p / i;
                        if (i != x){
                            if (mp[x]) s.insert(x);
                            mp[x]++;
                        }
                    }
                }
            }
            else {
                a[p] = 0;
                for (int i = 1; i * i <= p; i++){
                    if (p % i == 0){
                        if (i > 1){
                            mp[i]--;
                            if (mp[i] <= 1) s.erase(i);
                        }
                        int x = p / i;
                        if (i != x){
                            mp[x]--;
                            if (mp[x] <= 1) s.erase(x);
                        }
                    }
                }
            }
        }
        else {
            int l, r;
            cin >> l >> r;
            if (!s.empty()) cout << "DA" << endl;
            else cout << "NE" << endl;
        }
    }
}

signed main() {
	//freopen("exam.in", "r", stdin);
	//freopen("exam.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	#ifdef tests
		cin >> t;
	#endif
	#ifdef test
		t = 1;
	#endif
	while (t--) {
		solve();
	}
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 6880 KB Output is correct
2 Correct 1302 ms 19236 KB Output is correct
3 Execution timed out 1602 ms 25732 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

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