| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 799968 |
2023-08-01T08:57:05 Z |
vjudge1 |
Radio (COCI22_radio) |
C++17 |
|
358 ms |
28256 KB |
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=1e5+9;
vector<int>pr[maxn];
set<int>a[maxn];
set<int>::iterator it;
set<int>c[maxn];
bool b[maxn];
int n,q;
int st[maxn*4];
void update(int id,int l,int r,int u,int val){
if (l>u||r<u)return;
if (l==r){
st[id]=val;
return;
}
int mid=(l+r)/2;
update(id*2,l,mid,u,val);
update(id*2+1,mid+1,r,u,val);
st[id]=min(st[id*2],st[id*2+1]);
}
int get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return n+1;
if (u<=l&&r<=v)return st[id];
int mid=(l+r)/2;
return min(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
void add(int x){
b[x]=1;
for (auto v:pr[x]){
it=a[v].upper_bound(x);
int l=0,r=n+1;
if (it!=a[v].end())r=(*it);
if (it!=a[v].begin()){
it--;
l=(*it);
}
if (l!=0){
if (r!=n+1){
c[l].erase(r);
}
c[l].insert(x);
update(1,1,n,l,*c[l].begin());
}
if (r!=n+1){
c[x].insert(r);
}
}
for (auto v:pr[x])a[v].insert(x);
if (c[x].empty())update(1,1,n,x,n+1);
else update(1,1,n,x,*c[x].begin());
}
void del(int x){
b[x]=0;
for (auto v:pr[x]){
a[v].erase(x);
it=a[v].upper_bound(x);
int l=0,r=n+1;
if (it!=a[v].end())r=(*it);
if (it!=a[v].begin()){
it--;
l=(*it);
}
if (l!=0){
c[l].erase(x);
if (r!=n+1){
c[l].insert(r);
}
if (c[l].empty())update(1,1,n,l,n+1);
else update(1,1,n,l,*c[l].begin());
}
}
c[x].clear();
update(1,1,n,x,n+1);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("RADIO.INP","r",stdin);
//freopen("RADIO.OUT","w",stdout);
cin>>n>>q;
for1(i,2,n){
if (pr[i].empty()){
for3(j,i,n,i){
pr[j].pb(i);
}
}
}
for1(i,1,n){
update(1,1,n,i,n+1);
}
for1(i,1,q){
char r;
cin>>r;
if (r=='S'){
int x;
cin>>x;
if (b[x])del(x);
else add(x);
}
else {
int l,r;
cin>>l>>r;
if (get(1,1,n,l,r)<=r)cout<<"YES"<<'\n';
else cout<<"NO"<<'\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
11988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
358 ms |
28256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
11988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
