제출 #1109935

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1109935		vjudge1	Radio (COCI22_radio)	C++14	30 / 110	589 ms	100544 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

const int MAXN = 1e6 + 505;

int n, m;

vector<int> Prime;
bool notprime[MAXN];
int factor[MAXN];
void Euler() {
    factor[1] = 1, notprime[1] = 1;
    for (int i = 2; i < MAXN; ++i) {
        if (!notprime[i]) {
            Prime.push_back(i);
            factor[i] = i;
        }
        for (int j : Prime) {
            if (i * j >= MAXN) break;
            notprime[i * j] = 1, factor[i * j] = j;
            if (i % j == 0) break;
        }
    }
    return ;
}

bool vis[MAXN];
set<int> S[MAXN], D;
void Div(int x) {
    D.clear();
    while (x != 1) {
        D.insert(factor[x]);
        x /= factor[x];
    }
    return ;
}
pii Get(int x, set<int> &S) {
    pii res;
    if (S.empty()) return res;
    auto it1 = S.upper_bound(x);
    if (it1 != S.end()) res.second = *it1;
    if (x > *S.begin()) res.first = *--S.lower_bound(x);
    return res;
}

struct SGT {
    int l[MAXN << 2], r[MAXN << 2], a[MAXN << 2];
#define lc(r1) (r1 << 1)
#define rc(r1) (r1 << 1 | 1)
#define mid (l[pos] + r[pos] >> 1)
    inline void UP(int pos) {a[pos] = max(a[lc(pos)], a[rc(pos)]);}
    void Build(int L, int R, int pos) {
        l[pos] = L, r[pos] = R;
        if (L == R) return ;
        return Build(L, mid, lc(pos)), Build(mid + 1, R, rc(pos));
    }
    void Modify(int q, int pos, int k) {
        if (l[pos] == r[pos]) return a[pos] = k, void();
        Modify(q, q <= mid ? lc(pos) : rc(pos), k);
        return UP(pos);
    }
    int Query(int q, int w, int pos) {
        if (q <= l[pos] && w >= r[pos]) return a[pos];
        if (q >  mid) return Query(q, w, rc(pos));
        if (w <= mid) return Query(q, w, lc(pos));
        return max(Query(q, w, lc(pos)), Query(q, w, rc(pos)));
    }
#undef mid
} T;


int main() {
    Euler();
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;

    T.Build(1, n, 1);
    char op;
    int x, y, a, b;
    while (m--) {
        cin >> op >> x;
        if (op == 'S') {
            Div(x);
            if (vis[x]) {
                for (int v : D) {
                    S[v].erase(x);
                    tie(a, b) = Get(x, S[v]);
                    T.Modify(x, 1, 0);
                    if (b) {
                        int tmp = T.Query(b, b, 1);
                        if (a > tmp) T.Modify(b, 1, a);
                    }
                }
            } else {
                for (int v : D) {
                    S[v].insert(x);
                    tie(a, b) = Get(x, S[v]);
                    if (a) {
                        int tmp = T.Query(x, x, 1);
                        if (a > tmp) T.Modify(x, 1, a);
                    }
                    if (b) {
                        int tmp = T.Query(b, b, 1);
                        if (x > tmp) T.Modify(b, 1, x);
                    }
                }
            }
            vis[x] ^= 1;
        } else {
            cin >> y;
            cout << (T.Query(x, y, 1) >= x ? "DA" : "NE") << '\n';
        }
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In member function 'void SGT::Build(int, int, int)':
Main.cpp:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 | #define mid (l[pos] + r[pos] >> 1)
      |              ~~~~~~~^~~~~~~~
Main.cpp:57:25: note: in expansion of macro 'mid'
   57 |         return Build(L, mid, lc(pos)), Build(mid + 1, R, rc(pos));
      |                         ^~~
Main.cpp:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 | #define mid (l[pos] + r[pos] >> 1)
      |              ~~~~~~~^~~~~~~~
Main.cpp:57:46: note: in expansion of macro 'mid'
   57 |         return Build(L, mid, lc(pos)), Build(mid + 1, R, rc(pos));
      |                                              ^~~
Main.cpp: In member function 'void SGT::Modify(int, int, int)':
Main.cpp:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 | #define mid (l[pos] + r[pos] >> 1)
      |              ~~~~~~~^~~~~~~~
Main.cpp:61:24: note: in expansion of macro 'mid'
   61 |         Modify(q, q <= mid ? lc(pos) : rc(pos), k);
      |                        ^~~
Main.cpp: In member function 'int SGT::Query(int, int, int)':
Main.cpp:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 | #define mid (l[pos] + r[pos] >> 1)
      |              ~~~~~~~^~~~~~~~
Main.cpp:66:18: note: in expansion of macro 'mid'
   66 |         if (q >  mid) return Query(q, w, rc(pos));
      |                  ^~~
Main.cpp:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 | #define mid (l[pos] + r[pos] >> 1)
      |              ~~~~~~~^~~~~~~~
Main.cpp:67:18: note: in expansion of macro 'mid'
   67 |         if (w <= mid) return Query(q, w, lc(pos));
      |                  ^~~

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