oj.uz

Submission #547093

# Submission time Handle Problem Language Result Execution time Memory
547093 2022-04-09T14:05:16 Z errorgorn Radio (COCI22_radio) C++17
40 / 110
 1500 ms 221960 KB 
// 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 433 ms 180052 KB Output is correct
2 Correct 505 ms 179968 KB Output is correct
3 Correct 448 ms 180060 KB Output is correct
4 Correct 510 ms 180136 KB Output is correct
5 Correct 450 ms 180064 KB Output is correct
6 Correct 491 ms 180016 KB Output is correct
7 Correct 489 ms 180040 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 872 ms 191860 KB Output is correct
2 Correct 1122 ms 210188 KB Output is correct
3 Correct 1248 ms 216856 KB Output is correct
4 Correct 507 ms 180240 KB Output is correct
5 Correct 513 ms 181112 KB Output is correct
6 Correct 557 ms 182216 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 180052 KB Output is correct
2 Correct 505 ms 179968 KB Output is correct
3 Correct 448 ms 180060 KB Output is correct
4 Correct 510 ms 180136 KB Output is correct
5 Correct 450 ms 180064 KB Output is correct
6 Correct 491 ms 180016 KB Output is correct
7 Correct 489 ms 180040 KB Output is correct
8 Correct 872 ms 191860 KB Output is correct
9 Correct 1122 ms 210188 KB Output is correct
10 Correct 1248 ms 216856 KB Output is correct
11 Correct 507 ms 180240 KB Output is correct
12 Correct 513 ms 181112 KB Output is correct
13 Correct 557 ms 182216 KB Output is correct
14 Correct 667 ms 181456 KB Output is correct
15 Correct 1057 ms 187408 KB Output is correct
16 Execution timed out 1509 ms 221960 KB Time limit exceeded
17 Halted 0 ms 0 KB -