oj.uz

Submission #555107

# Submission time Handle Problem Language Result Execution time Memory
555107 2022-04-30T07:30:01 Z fuad27 Radio (COCI22_radio) C++17
40 / 110
 808 ms 8404 KB 
#include<bits/stdc++.h>
using namespace std;
template<typename T>
auto operator<<(ostream &os, T&v)->decltype(v.begin(), os){
	os << "[";
	int f = 0;
	for(auto i:v) {
		if(f++)os << ", ";
		os << i;
	}
	os << "]";
	return os;
}
template<typename F, typename S>
ostream& operator<<(ostream &os, pair<F, S> const &p) {
	return os << "(" << p.first << ", " << p.second << ")";
}
ostream& operator<<(ostream &os, string& s) {
	for(char i:s){
		os << i;
	}
	return os;
}
void debug(){}
template<typename T, typename... V>
void debug(T t, V... v) {
	cerr << t;
	if(sizeof...(v)) {
		cerr << ", "; debug(v...);
	}
}
#ifdef LOCAL
#define dbg(x...) cerr << "[" << #x << "]: " << "["; debug(x); cerr << "]\n";
#else
#define dbg(x...)
#endif


int main () {
	int n, q;
	cin >> n >> q;
//	if(0) {
	if(n <= 100 and q <= 200) {
		vector<int> v(n+1);
		while(q--) {
			char c;
			cin >> c;
			if(c == 'S') {
				long long in;
				cin >> in;
				v[in] ^= 1;
			}
			else if(c == 'C') {
				long long l, r;
				cin >> l >> r;
				bool check = false;
				for(int i =l;i<=r;i++) {
					for(int j = l;j<=r;j++) {
						if(j == i)continue;
						if(!v[j] or !v[i])continue;
						if(__gcd(i, j)!=1) {
							check = true;
						}
					}
				}
				cout << (check?"DA":"NE") << "\n";
			}
		}
	}
	else {
		vector<bool> used(n+1);
		vector<long long> cnt(n+1);
		long long c = 0;
		while(q--) {
			char ch;
			cin >> ch;
			if(ch == 'S') {
				long long in;
				cin >> in;
				if(!used[in]) {
					used[in] = true;
					cnt[in]++;
					if(cnt[in] == 2)c++;
					for(int i = 2;i*i<=in;i++) {
						if(in%i == 0) {
							cnt[i]++;
							if(cnt[i] == 2)c++;
							if(in/i!=i)  {
								cnt[in/i]++;
								if(cnt[in/i] == 2)c++;
							}
						}
					}
				}
				else {
					used[in] = false;
					cnt[in]--;
					if(cnt[in] == 1)c--;
					for(int i = 2;i*i<=in;i++) {
						if(in%i == 0) {
							cnt[i]--;
							if(cnt[i] == 1)c--;
							if(in/i!=i)  {
								cnt[in/i]--;
								if(cnt[in/i] == 1)c--;
							}
						}
					}
				}
				dbg(cnt);
			}
			else {
				long long l, r;
				cin >> l >> r;
				cout << (c?"DA":"NE") << "\n";
			}
		}
	}
}

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 2 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 1232 KB Output is correct
2 Correct 543 ms 4436 KB Output is correct
3 Correct 769 ms 8404 KB Output is correct
4 Correct 34 ms 1108 KB Output is correct
5 Correct 298 ms 4180 KB Output is correct
6 Correct 808 ms 8148 KB Output is correct

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 2 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 220 ms 1232 KB Output is correct
9 Correct 543 ms 4436 KB Output is correct
10 Correct 769 ms 8404 KB Output is correct
11 Correct 34 ms 1108 KB Output is correct
12 Correct 298 ms 4180 KB Output is correct
13 Correct 808 ms 8148 KB Output is correct
14 Incorrect 134 ms 1568 KB Output isn't correct
15 Halted 0 ms 0 KB -