oj.uz

Submission #572277

# Submission time Handle Problem Language Result Execution time Memory
572277 2022-06-04T07:39:09 Z Asylzhan Radio (COCI22_radio) C++17
10 / 110
 1500 ms 26420 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 (l > 1 || r < n){
                bool ok = 0;
                for (int i = l; i <= r; i++){
                    if (!a[i]) continue;
                    for (int j = i + 1; j <= r; j++){
                        if (!a[j]) continue;
                        if (__gcd(i, j) > 1) ok = 1;
                    }
                }
                if (ok) cout << "DA" << endl;
                else cout << "NE" << endl;
                continue;
            }
            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
10.0 / 10.0

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 6884 KB Output is correct
2 Correct 1215 ms 19396 KB Output is correct
3 Execution timed out 1555 ms 26420 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 486 ms 6884 KB Output is correct
9 Correct 1215 ms 19396 KB Output is correct
10 Execution timed out 1555 ms 26420 KB Time limit exceeded
11 Halted 0 ms 0 KB -