Submission #768949

#	Time	Username	Problem	Language	Result	Execution time	Memory
768949		Username4132	Radio (COCI22_radio)	C++14	110 / 110	759 ms	168316 KiB

Main

#include<iostream>
#include<vector>
#include<set>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second
 
const int MAXN = 1000010, SQ=1010;
int n, q, spf[MAXN], pre[MAXN], pr[MAXN][7], nx[MAXN][7], dii[MAXN][7], tr[2*MAXN];
bool used[MAXN];
set<int> wii[MAXN];
 
void sieve(){
    forsn(i, 2, SQ) if(!spf[i]) {
        spf[i]=i;
        for(int j=i*i; j<MAXN; j+=i) if(!spf[j]) spf[j]=i;
    }
    forsn(i, SQ, MAXN) if(!spf[i]) spf[i]=i;
    forsn(i, 2, MAXN) pre[i]=i/spf[i];
}
 
vector<int> divs(int x){
    int lst = -1;
    vector<int> ret;
    while(x>1){
        int p = spf[x];
        if(lst!=p) ret.PB(lst=p);
        x = pre[x];
    }
    return ret;
}
 
int query(int l, int r){
    int ret = MAXN;
    for(l+=n, r+=n; l<r; l>>=1, r>>=1){
        if(l&1) ret = min(ret, tr[l++]);
        if(r&1) ret = min(ret, tr[--r]);
    }
    return ret;
}
 
void modify(int p, int value){
    for(tr[p+=n]=value; p>1; p>>=1) tr[p>>1] = min(tr[p], tr[p^1]);
}
 
 
void update(int x){
    int mn = MAXN;
    forn(i, 7) if(dii[x][i]) mn = min(mn, nx[x][i]);
    modify(x-1, mn);
}
 
int main(){
    sieve();
    scanf("%d %d", &n, &q);
    forn(i, 2*n) tr[i] = MAXN;
    forn(qnum, q){
        char type; scanf(" %c", &type);
        if(type == 'S'){
            int x; scanf("%d", &x);
            if(x==1) continue;
            if(used[x]){
                for(int i=0; i<7 && dii[x][i]; ++i){
                    int p = dii[x][i], ba = -1, fo = MAXN;
                    auto itr = wii[p].find(x);
                    if(itr != wii[p].begin()) ba = *prev(itr);
                    if(next(itr) != wii[p].end()) fo = *next(itr);
                    if(ba != -1){
                        int j=0;
                        for(; dii[ba][j] != p; ++j);
                        nx[ba][j] = fo;
                        update(ba);
                    }
                    if(fo != MAXN){
                        int j=0;
                        for(; dii[fo][j] != p; ++j);
                        pr[fo][j] = ba;
                        update(fo);
                    }
                    wii[p].erase(itr);
                }
                forn(i, 7) nx[x][i] = MAXN;
                forn(i, 7) pr[x][i] = -1;
                update(x);
            }
            else{
                if(!dii[x][0]){
                    vector<int> ds = divs(x);
                    forn(i, ds.size()) dii[x][i] = ds[i];
                }
                for(int i=0; i<7 && dii[x][i]; ++i){
                    int p = dii[x][i];
                    auto itr = wii[p].insert(x).F;
                    if(itr == wii[p].begin()) pr[x][i] = -1;
                    else{
                        int j=0, val = pr[x][i] = *prev(itr);
                        for(; dii[val][j] != p; ++j);
                        nx[val][j] = x;
                        update(val);
                    }
                    if(*itr == *wii[p].rbegin()) nx[x][i]=MAXN;
                    else{
                        int j=0, val = nx[x][i] = *next(itr);
                        for(; dii[val][j] != p; ++j);
                        pr[val][j] = x;
                        update(val);
                    }
                }
                update(x);
            }
            used[x]^=1;
        }
        else{
            int l, r; scanf("%d %d", &l, &r);
            int mn = query(l-1, r);
            printf("%s", mn <= r? "DA\n" : "NE\n");
        }
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:61:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         char type; scanf(" %c", &type);
      |                    ~~~~~^~~~~~~~~~~~~~
Main.cpp:63:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |             int x; scanf("%d", &x);
      |                    ~~~~~^~~~~~~~~~
Main.cpp:117:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |             int l, r; scanf("%d %d", &l, &r);
      |                       ~~~~~^~~~~~~~~~~~~~~~~

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