제출 #1144731

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144731		nasir_bashirov	Radio (COCI22_radio)	C++20	110 / 110	789 ms	84256 KiB

Main

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define db long double
#define vll vector<pll>
#define F first
#define S second
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

// #define int long long 

const int sz = 1e6 + 5;
vi primes;
int n, q, x, y, t[sz * 4];
bool used[sz];
set<int> st[sz];
char op;

bool isPrime(int x){
	if(x == 1)	return false;
	if(x == 2)	return true;
	for(int i = 2; i <= sqrt(x); i++){
		if(x % 2 == 0)	return false;
	}
	return true;
}

void update(int i, int v, int x, int lx, int rx){
	if(lx == rx){
		t[x] = v;
		return;
	}
	int mid = (lx + rx) / 2;
	if(i <= mid)	update(i, v, x * 2, lx, mid);
	else	update(i, v, x * 2 + 1, mid + 1, rx);
	t[x] = min(t[x * 2], t[x * 2 + 1]);
}

int query(int l, int r, int x, int lx, int rx){
	if(lx >= l and rx <= r)	return t[x];
	if(l > rx or lx > r)	return 1e9;
	int mid = (lx + rx) / 2;
	return min(query(l, r, x * 2, lx, mid), query(l, r, x * 2 + 1, mid + 1, rx));
}

void fmain(){
	for(int i = 2; i <= 1000; i++){
		if(isPrime(i))	primes.push_back(i);
	}
	cin >> n >> q;
	for(int i = 1; i <= 4 * n; i++)	t[i] = 1e9;
	while(q--){
		cin >> op >> x;
		if(op == 'S'){
			vi recalc;
			int cur = x, mn = 1e9;
			for(int i : primes){
				bool f = false;
				while(cur % i == 0){
					cur /= i;
					f = true;
				}
				if(f){
					if(used[x]){
						st[i].erase(x);
						auto it = st[i].upper_bound(x);
						if(it != st[i].begin()){
							--it;
							int qry = query(*it, *it, 1, 1, n);
							if(qry == x){
								recalc.push_back(*it);
							}
						}
					}
					else{
						auto it = st[i].upper_bound(x);
						if(it != st[i].end()){
							mn = min(mn, *it);
						}
						if(it != st[i].begin()){
							--it;
							int qry = query(*it, *it, 1, 1, n);
							if(qry > x)	update(*it, x, 1, 1, n);
						}
						st[i].insert(x);
					}
				}
			}
			if(cur > 1){
				if(used[x]){
					st[cur].erase(x);
					auto it = st[cur].upper_bound(x);
					if(it != st[cur].begin()){
						--it;
						int qry = query(*it, *it, 1, 1, n);
						if(qry == x){
							recalc.push_back(*it);
						}
					}
				}
				else{
					auto it = st[cur].upper_bound(x);
					if(it != st[cur].end()){
						mn = min(mn, *it);
					}
					if(it != st[cur].begin()){
						--it;
						int qry = query(*it, *it, 1, 1, n);
						if(qry > x)	update(*it, x, 1, 1, n);
					}
					st[cur].insert(x);
				}
			}
			if(!used[x]){
				update(x, mn, 1, 1, n);
			}
			else{
				for(int cr : recalc){
					int cur = cr, nw = 1e9;
					for(int i : primes){
						bool f = false;
						while(cur % i == 0){
							f = true;
							cur /= i;
						}
						if(f){
							auto it = st[i].upper_bound(cr);
							if(it != st[i].end()){
								nw = min(nw, *it);
							}
						}
					}
					if(cur > 1){
						auto it = st[cur].upper_bound(cr);
						if(it != st[cur].end()){
							nw = min(nw, *it);
						}
					}
					update(cr, nw, 1, 1, n);
				}
				update(x, 1e9, 1, 1, n);
			}
			used[x] = !used[x];
		}
		else{
			cin >> y;
			cout << (query(x, y, 1, 1, n) <= y ? "DA" : "NE") << endl;
		}
	}
}

signed main(){
	fastio;
	int tmr = 1;
	// cin >> tmr;
	while(tmr--){
		fmain();
	}
	
}

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