| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 879978 |
2023-11-28T12:41:17 Z |
HossamHero7 |
Radio (COCI22_radio) |
C++14 |
|
1028 ms |
109476 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 1e6+5;
int spf[N] , isprime[N];
set<int> primes[N];
bool on[N];
struct segTree{
int n;
vector<int> tree;
bool b;
int fun(int x,int y){
return b ? max(x,y) : min(x,y);
}
segTree(int _n, bool _b){
n = _n , b = _b;
tree.resize(4*n+5,(b ? 0 : 1e9));
}
void update(int node,int l,int r,int idx,int val){
if(l == r) return tree[node] = fun(tree[node] , val) , void();
int md = l + r >> 1;
idx <= md ? update(node<<1,l,md,idx,val) : update(node<<1|1,md+1,r,idx,val);
tree[node] = fun(tree[node<<1],tree[node<<1|1]);
}
void set(int node,int l,int r,int idx,int val){
if(l == r) return tree[node] = val , void();
int md = l + r >> 1;
idx <= md ? set(node<<1,l,md,idx,val) : set(node<<1|1,md+1,r,idx,val);
tree[node] = fun(tree[node<<1],tree[node<<1|1]);
}
int query(int node,int l,int r,int lQ,int rQ){
if(l > r || lQ > r || l > rQ) return (b ? 0 : 1e9);
if(lQ <= l && r <= rQ) return tree[node];
int md = l + r >> 1;
return fun(query(node<<1,l,md,lQ,rQ) , query(node<<1|1,md+1,r,lQ,rQ));
}
void update(int idx,int x){
update(1,1,n,idx,x);
}
void set(int idx,int x){
set(1,1,n,idx,x);
}
int query(int l,int r){
return query(1,1,n,l,r);
}
};
vector<int> pFactors(int x){
vector<int> tmp;
int y = x;
while(y != 1){
if(tmp.empty() || tmp.back() != spf[y]) tmp.push_back(spf[y]);
y /= spf[y];
}
return tmp;
}
segTree nxt(1e6,0);
segTree bef(1e6,1);
void calc(int x,bool b){
vector<int> tmp = pFactors(x);
for(auto p : tmp){
if(!b) primes[p].erase(x);
auto it = primes[p].lower_bound(x);
if(it != primes[p].end()){
if(b) bef.update(*it,x);
nxt.update(x,*it);
}
if(it != primes[p].begin()){
it --;
if(b) nxt.update(*it,x);
bef.update(x,*it);
}
primes[p].insert(x);
}
}
void solve(){
int n,q;
cin>>n>>q;
while(q--){
char c;
cin>>c;
if(c == 'S'){
int x;
cin>>x;
if(!on[x]){
calc(x,1);
on[x] = 1;
}
else {
on[x] = 0;
nxt.set(x,1e9);
bef.set(x,0);
vector<int> effected;
vector<int> tmp = pFactors(x);
for(auto p : tmp){
primes[p].erase(x);
auto it = primes[p].lower_bound(x);
if(it != primes[p].end()) effected.push_back(*it);
if(it != primes[p].begin()) effected.push_back(*(--it));
}
for(auto y : effected) nxt.set(y,1e9) , bef.set(y,0) , calc(y,0);
}
}
else {
int l,r;
cin>>l>>r;
int mxbef = bef.query(l,r);
int mnnxt = nxt.query(l,r);
cout<<(mxbef >= l || mnnxt <= r ? "DA" : "NE")<<endl;
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t=1;
//cin>>t;
memset(isprime,1,sizeof(isprime));
isprime[1] = 0;
for(ll i=2;i<N;i++){
if(!isprime[i]) continue;
spf[i] = i;
for(ll j=i*i;j<N;j+=i){
if(!isprime[j]) continue;
spf[j] = i;
isprime[j] = 0;
}
}
while(t--){
solve();
}
return 0;
}
Compilation message
Main.cpp: In member function 'void segTree::update(int, int, int, int, int)':
Main.cpp:22:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
22 | int md = l + r >> 1;
| ~~^~~
Main.cpp: In member function 'void segTree::set(int, int, int, int, int)':
Main.cpp:28:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
28 | int md = l + r >> 1;
| ~~^~~
Main.cpp: In member function 'int segTree::query(int, int, int, int, int)':
Main.cpp:35:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int md = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
87112 KB |
Output is correct |
| 2 |
Correct |
28 ms |
87544 KB |
Output is correct |
| 3 |
Correct |
25 ms |
87384 KB |
Output is correct |
| 4 |
Correct |
25 ms |
87388 KB |
Output is correct |
| 5 |
Correct |
26 ms |
87388 KB |
Output is correct |
| 6 |
Correct |
22 ms |
87384 KB |
Output is correct |
| 7 |
Correct |
22 ms |
87384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
557 ms |
93156 KB |
Output is correct |
| 2 |
Correct |
777 ms |
103084 KB |
Output is correct |
| 3 |
Correct |
777 ms |
106824 KB |
Output is correct |
| 4 |
Correct |
29 ms |
87608 KB |
Output is correct |
| 5 |
Correct |
53 ms |
88200 KB |
Output is correct |
| 6 |
Correct |
110 ms |
88820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
87112 KB |
Output is correct |
| 2 |
Correct |
28 ms |
87544 KB |
Output is correct |
| 3 |
Correct |
25 ms |
87384 KB |
Output is correct |
| 4 |
Correct |
25 ms |
87388 KB |
Output is correct |
| 5 |
Correct |
26 ms |
87388 KB |
Output is correct |
| 6 |
Correct |
22 ms |
87384 KB |
Output is correct |
| 7 |
Correct |
22 ms |
87384 KB |
Output is correct |
| 8 |
Correct |
557 ms |
93156 KB |
Output is correct |
| 9 |
Correct |
777 ms |
103084 KB |
Output is correct |
| 10 |
Correct |
777 ms |
106824 KB |
Output is correct |
| 11 |
Correct |
29 ms |
87608 KB |
Output is correct |
| 12 |
Correct |
53 ms |
88200 KB |
Output is correct |
| 13 |
Correct |
110 ms |
88820 KB |
Output is correct |
| 14 |
Correct |
637 ms |
88904 KB |
Output is correct |
| 15 |
Correct |
964 ms |
92404 KB |
Output is correct |
| 16 |
Correct |
1028 ms |
109476 KB |
Output is correct |
| 17 |
Correct |
799 ms |
106072 KB |
Output is correct |
| 18 |
Correct |
915 ms |
108008 KB |
Output is correct |
| 19 |
Correct |
890 ms |
107748 KB |
Output is correct |
| 20 |
Correct |
102 ms |
88916 KB |
Output is correct |
| 21 |
Correct |
96 ms |
88920 KB |
Output is correct |
| 22 |
Correct |
107 ms |
88980 KB |
Output is correct |
| 23 |
Correct |
119 ms |
88984 KB |
Output is correct |
