oj.uz

Submission #547097

# Submission time Handle Problem Language Result Execution time Memory
547097 2022-04-09T14:06:49 Z errorgorn Radio (COCI22_radio) C++17
110 / 110
 1329 ms 220300 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

// Super Idol的笑容
//    都没你的甜
//  八月正午的阳光
//    都没你耀眼
//  热爱105°C的你
// 滴滴清纯的蒸馏水
 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl
 
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
 
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
 
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug
 
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
 
struct node{
	const int BUF=1000010;
	int tree[2000100];
	
	node(){
		memset(tree,63,sizeof(tree));
	}
	
	void upd(int i,int k){
		i+=BUF;
		tree[i]=k;
		while (i>>=1){
			tree[i]=min(tree[i<<1],tree[i<<1|1]);
		}
	}
	
	int query(int i,int j){
		i+=BUF,j+=BUF+1;
		
		int res=1e9;
		while (i<j){
			if (i&1){
				res=min(res,tree[i]);
				i++;
			}
			if (j&1){
				j--;
				res=min(res,tree[j]);
			}
			
			i>>=1,j>>=1;
		}
		
		return res;
	}
} root;
 
int n,q;
vector<int> primes[1000005];
 
bool has[1000005];
set<int> pos[1000005];
multiset<int> s[1000005];
 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	rep(x,2,1000005) if (primes[x].empty()){
		for (int y=x;y<1000005;y+=x) primes[y].pub(x);
	}
	
	//rep(x,2,11) for (auto it:primes[x]) cout<<it<<" "; cout<<endl;
	
	cin>>n>>q;
	
	char c;
	int a,b;
	while (q--){
		cin>>c;
		if (c=='S'){
			cin>>a;
			
			if (!has[a]){
				for (auto it:primes[a]){
					auto iter=pos[it].insert(a).fi;
					
					int l=-1,r=-1;
					if (iter!=pos[it].begin()) l=*prev(iter);
					if (iter!=prev(pos[it].end())) r=*next(iter);
					
					if (l!=-1 && r!=-1) s[l].erase(s[l].find(r));
					if (l!=-1) s[l].insert(a);
					if (r!=-1) s[a].insert(r);
					
					if (l!=-1) root.upd(l,s[l].empty()?1e9:*s[l].begin());
					root.upd(a,s[a].empty()?1e9:*s[a].begin());
				}
			}
			else{
				for (auto it:primes[a]){
					auto iter=pos[it].find(a);
					
					int l=-1,r=-1;
					if (iter!=pos[it].begin()) l=*prev(iter);
					if (iter!=prev(pos[it].end())) r=*next(iter);
					
					if (l!=-1 && r!=-1) s[l].insert(r);
					if (l!=-1) s[l].erase(s[l].find(a));
					if (r!=-1) s[a].erase(s[a].find(r));
					
					if (l!=-1) root.upd(l,s[l].empty()?1e9:*s[l].begin());
					root.upd(a,s[a].empty()?1e9:*s[a].begin());
					
					pos[it].erase(a);
				}
			}
			
			has[a]^=true;
		}
		else{
			cin>>a>>b;
			
			if (root.query(a,b)<=b) cout<<"DA"<<endl;
			else cout<<"NE"<<endl;
		}
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 180052 KB Output is correct
2 Correct 487 ms 180232 KB Output is correct
3 Correct 470 ms 180040 KB Output is correct
4 Correct 500 ms 180180 KB Output is correct
5 Correct 491 ms 180172 KB Output is correct
6 Correct 449 ms 180040 KB Output is correct
7 Correct 474 ms 180196 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 893 ms 191072 KB Output is correct
2 Correct 1138 ms 209016 KB Output is correct
3 Correct 1243 ms 215472 KB Output is correct
4 Correct 479 ms 180060 KB Output is correct
5 Correct 524 ms 180668 KB Output is correct
6 Correct 562 ms 181012 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 180052 KB Output is correct
2 Correct 487 ms 180232 KB Output is correct
3 Correct 470 ms 180040 KB Output is correct
4 Correct 500 ms 180180 KB Output is correct
5 Correct 491 ms 180172 KB Output is correct
6 Correct 449 ms 180040 KB Output is correct
7 Correct 474 ms 180196 KB Output is correct
8 Correct 893 ms 191072 KB Output is correct
9 Correct 1138 ms 209016 KB Output is correct
10 Correct 1243 ms 215472 KB Output is correct
11 Correct 479 ms 180060 KB Output is correct
12 Correct 524 ms 180668 KB Output is correct
13 Correct 562 ms 181012 KB Output is correct
14 Correct 645 ms 180300 KB Output is correct
15 Correct 1091 ms 186136 KB Output is correct
16 Correct 1329 ms 220300 KB Output is correct
17 Correct 1156 ms 214820 KB Output is correct
18 Correct 1261 ms 218220 KB Output is correct
19 Correct 1253 ms 218580 KB Output is correct
20 Correct 538 ms 182432 KB Output is correct
21 Correct 564 ms 182140 KB Output is correct
22 Correct 566 ms 182340 KB Output is correct
23 Correct 560 ms 182524 KB Output is correct