oj.uz

Submission #802004

# Submission time Handle Problem Language Result Execution time Memory
802004 2023-08-02T09:01:06 Z hat0412 Radio (COCI22_radio) C++14
10 / 110
 247 ms 116348 KB 
#include <bits/stdc++.h>

#define lli long long
#define lld long double
#define pb push_back
#define fi first
#define se second
#define name "radio"

using namespace std;

const int N = 1e6 + 10;
const int inf = 1e9 + 7;

struct Segment
{
    vector<int> st;

    void init (int n)
    {
        st.resize(n * 4 + 10);
        for (int i = 1; i <= n * 4; i++) st[i] = inf;
    }

    void update(int id, int l, int r, int u, int val)
    {
        if (u < l || u > r) return;
        if (l == r)
        {
            st[id] = val;
            return;
        }

        int m = (l + r) >> 1;
        update(id << 1, l, m, u, val);
        update(id << 1 | 1, m + 1, r, u, val);

        st[id] = min(st[id << 1], st[id << 1 | 1]);
    }

    int query (int id, int l, int r, int u, int v)
    {
        if (v < l || u > r) return inf;
        if (u <= l && r <= v) return st[id];

        int m = (l + r) >> 1;
        return min(query(id << 1, l, m, u, v),
                   query(id << 1 | 1, m + 1, r, u, v));
    }
} seg;
int n, q, prime[N], nxt[N];
set<int> pos[N];
bool check[N];

void read()
{
    cin >> n >> q;
}

void solve()
{
    for (int i = 1; i <= n; i++) nxt[i] = inf;
    for (int i = 2; i <= 100000; i++)
        if (!prime[i])
            for (int j = i; j <= 100000; j += i) if (!prime[j]) prime[j] = i;

    seg.init(n);
    while (q--)
    {
        char c; cin >> c;
        if (c == 'C')
        {
            int l, r; cin >> l >> r;
            if (seg.query(1, 1, n, l, r) <= r) cout << "DA\n";
            else cout << "NE\n";
            continue;
        }
        int x, t; cin >> x; t = x;
        if (check[x])
        {
            while (x != 1)
            {
                int s = prime[x];
                while (x % s == 0) x /= s;
                auto it1 = pos[s].upper_bound(t),
                     it2 = pos[s].lower_bound(t);

                if (it2 != pos[s].begin())
                {
                    it2--;
                    int tmp = inf;
                    if (it1 != pos[s].end()) tmp = *it1;
                    if (nxt[*it2] == t)
                    {
                        int z = *it2;
                        nxt[*it2] = tmp;

                        while (z > 1)
                        {
                            int ss = prime[z];
                            while (z % ss == 0) z /= ss;
                            auto it = pos[ss].upper_bound(t);
                            if (it != pos[ss].end()) nxt[*it2] = min(nxt[*it2], *it);
                        }

                        seg.update(1, 1, n, *it2, nxt[*it2]);
                    }
                }
                pos[s].erase(t);
            }
            nxt[t] = inf;
            seg.update(1, 1, n, t, nxt[t]);
        }
        else
        {
            while (x != 1)
            {
                int s = prime[x];
                while (x % s == 0) x /= s;
                auto it = pos[s].upper_bound(t);
                if (it != pos[s].end()) nxt[t] = min(nxt[t], *it);
                if (it != pos[s].begin())
                {
                    it--;
                    nxt[*it] = min(nxt[*it], t);
                    seg.update(1, 1, n, *it, nxt[*it]);
                }
                pos[s].insert(t);
            }
            seg.update(1, 1, n, t, nxt[t]);
        }
        check[t] ^= 1;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }

    read();
    solve();
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47700 KB Output is correct
2 Correct 24 ms 47596 KB Output is correct
3 Correct 19 ms 47700 KB Output is correct
4 Correct 20 ms 47700 KB Output is correct
5 Correct 22 ms 47632 KB Output is correct
6 Correct 25 ms 47632 KB Output is correct
7 Correct 23 ms 47664 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 55344 KB Output is correct
2 Runtime error 71 ms 116348 KB Execution killed with signal 8
3 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47700 KB Output is correct
2 Correct 24 ms 47596 KB Output is correct
3 Correct 19 ms 47700 KB Output is correct
4 Correct 20 ms 47700 KB Output is correct
5 Correct 22 ms 47632 KB Output is correct
6 Correct 25 ms 47632 KB Output is correct
7 Correct 23 ms 47664 KB Output is correct
8 Correct 247 ms 55344 KB Output is correct
9 Runtime error 71 ms 116348 KB Execution killed with signal 8
10 Halted 0 ms 0 KB -