Submission #1271134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271134		SmuggingSpun	Radio (COCI22_radio)	C++20	0 / 110	16 ms	28100 KiB

Main

#include<bits/stdc++.h>
#define taskname "D"
using namespace std;
const int LIM = 1e6 + 5;
const int CNT_PRIME = 78500;
const int SQRT_LIM = 1e3 + 1;
vector<int>prime;
bitset<LIM>app;
int n, q, lpf[LIM], idp[LIM], st[LIM << 2];
set<int>s[CNT_PRIME];
pair<int, int>find_neighbor(int ip, int x){
	auto it = s[ip].lower_bound(x);
	int right = *it;
	it--;
	return make_pair(*it, right);
}
void update(int id, int l, int r, int p, int x){
	if(l == r){
		st[id] = x;
		return;
	}
	int m = (l + r) >> 1;
	if(m < p){
		update(id << 1 | 1, m + 1, r, p, x);
	}
	else{
		update(id << 1, l, m, p, x);
	}
	st[id] = min(st[id << 1], st[id << 1 | 1]);
}
int get(int id, int l, int r, int u, int v){
	if(l > v || r < u){
		return LIM;
	}
	if(u <= l && v >= r){
		return st[id];
	}
	int m = (l + r) >> 1;
	return min(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
}
void solve(int l, int r){
	if(get(1, 1, n, l, r) <= r){
		return void(cout << "DA\n");
	}
	for(int i = 0; prime[i] < SQRT_LIM; i++){
		if(!s[i].empty()){
			auto it = s[i].lower_bound(l);
			if(*it != *s[i].rbegin()){
				it++;
				if(*it <= r){
					return void(cout << "DA\n");
				}
			}
		}
	}
	cout << "NE\n";
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	memset(lpf, idp[2] = 0, sizeof(lpf));
	for(int i = 2; i < LIM; i += 2){
		lpf[i] = 2;
	}
	prime.emplace_back(2);
	for(int i = 3; i < LIM; i += 2){
		if(lpf[i] == 0){
			idp[lpf[i] = i] = prime.size();
			prime.emplace_back(i);
		}
		for(int& j : prime){
			int t = i * j;
			if(t >= LIM || (lpf[t] = j) == i){
				break;
			}
		}
	}
	app.reset();
	memset(st, 0x3f, sizeof(st));
	cin >> n >> q;
	for(int _ = 0; _ < q; _++){
		char c;
		cin >> c;
		if(c == 'S'){
			int x;
			cin >> x;
			int dx = x;
			while(dx > 1){
				int p = lpf[dx], ip = idp[p];
				if(p >= SQRT_LIM){
					if(app[x]){
						if(!s[ip].empty()){
							if(*s[ip].begin() > x){
								update(1, 1, n, x, *s[ip].begin());
							}
							else if(*s[ip].rbegin() < x){
								update(1, 1, n, *s[ip].rbegin(), x);
							}
							else{
								pair<int, int>xner = find_neighbor(ip, x);
								update(1, 1, n, xner.first, x);
								update(1, 1, n, x, xner.second);
							}
						}
						s[ip].insert(x);
					}
					else{
						if(x == *s[ip].begin()){
							update(1, 1, n, x, LIM);
						}
						else if(x == *s[ip].rbegin()){
							auto it = s[ip].end();
							it--;
							it--;
							update(1, 1, n, *it, LIM);
						}
						else{
							pair<int, int>xner = find_neighbor(ip, x);
							update(1, 1, n, xner.first, xner.second);
							update(1, 1, n, x, LIM);
						}
						s[ip].erase(x);
					}
					break;
				}
				if(app[x]){
					s[ip].erase(x);
				}
				else{
					s[ip].insert(x);
				}
				do{
					dx /= p;
				} while(dx % p == 0);
			}
			app[x] = !app[x];
		}
		else{
			int l, r;
			cin >> l >> r;
			solve(l, r);
		}
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:61:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 70