oj.uz

답안 #879480

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
879480 2023-11-27T14:14:16 Z Alora Radio (COCI22_radio) C++17
40 / 110
 1500 ms 159376 KB 
#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define VietAnh "RADIO"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)

using namespace std;

const ll mod = 1e9 + 7;
const int maxn = 1 << 20;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

long long GetRandom(long long l, long long r)
{
    return uniform_int_distribution<long long> (l, r)(rng);
}

int n, q;
set<int> s[maxn];
int d[maxn];
int L[maxn], R[maxn], nt[maxn];
vector<int> prime[maxn], v;

struct dl{
    int val_l, val_r;

    dl(){
        val_l = 0, val_r = 1e9;
    }

    dl(int _vl, int _vr){
        val_l = _vl, val_r = _vr;
    }

} st[2 * maxn];;

void eras()
{
    fi(i, 1, maxn - 2) nt[i] = i;

    for(int i = 2; i * i < maxn;  i ++)
    {
        if(nt[i] == i)
        {
            for(int j = i * i; j < maxn; j += i)
            {
                nt[j] = min(nt[j], i);
            }
        }
    }
}

dl cb(dl x, dl y)
{
    dl k;
    k.val_l = max(x.val_l, y.val_l);
    k.val_r = min(x.val_r, y.val_r);
    return k;
}

void update(int x, dl k, int id = 1, int l = 1, int r = n)
{
    if(l > x || r < x) return;

    if(l == r)
    {
        st[id] = k;
        return;
    }

    int mid = (l + r) >> 1;

    update(x, k, _left);
    update(x, k, _right);

    st[id] = cb(st[id * 2], st[id * 2 + 1]);
}

dl get(int u, int v, int id = 1, int l = 1, int r = n)
{
    if(l > v || r < u){
        dl k;
        return k;
    }

    if(u <= l && r <= v) return st[id];

    int mid = (l + r) >> 1;

    return cb(get(u, v, _left), get(u, v, _right));
}

void pt(int x)
{
    int a = x;

    while(x > 1)
    {
        int curr = nt[x];
        prime[a].push_back(curr);

        while(x % curr == 0) x /= curr;
    }
}

void update_(int x)
{
    L[x] = 0, R[x] = n + 1;

    for(int p : prime[x])
    {
        auto it = s[p].lower_bound(x);

        if(it != s[p].begin()) L[x] = max(L[x], *prev(it));
        if(it != prev(s[p].end())) R[x] = min(R[x], *next(it));
    }
    dl k (L[x], R[x]);
    update(x, k);
}

void Add(int x)
{
    v.clear();

    L[x] = 0, R[x] = n + 1;

    for(int p : prime[x])
    {
        auto it = s[p].lower_bound(x);

        if(it != s[p].end())
        {
            R[x] = min(R[x], *it);
            v.push_back(*it);
        }

        if(it != s[p].begin())
        {
            L[x] = max(L[x], *prev(it));
            v.push_back(*prev(it));
        }

        s[p].insert(x);
    }

    resp(v);

    for(int p : v) update_(p);

    dl k (L[x], R[x]);
    update(x, k);
}

void Del(int x)
{
    v.clear();

    L[x] = 0, R[x] = n + 1;

    for(int p : prime[x])
    {
        auto it = s[p].lower_bound(x);

        if(it != prev(s[p].end())) v.push_back(*next(it));
        if(it != s[p].begin()) v.push_back(*prev(it));

        s[p].erase(it);
    }

    resp(v);

    for(int p : v) update_(p);

    dl k (L[x], R[x]);
    update(x, k);
}

void solve()
{

    cin >> n >> q;

    eras();

    fi(i, 1, n) pt(i);

    while(q--)
    {
        char type;
        int x, y;
        cin >> type >> x;

        if(type == 'C')
        {
            cin >> y;
            dl p = get(x, y);

            if(x <= p.val_l || p.val_r <= y) cout << "DA\n";
            else cout << "NE\n";
        }
        else
        {
            if(!d[x]) Add(x);
            else Del(x);

            d[x] = 1 - d[x];
        }
    }

}


int main()
{

    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


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



    int nTest = 1;
//    cin >> nTest;

    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 98944 KB Output is correct
2 Correct 24 ms 98904 KB Output is correct
3 Correct 23 ms 98904 KB Output is correct
4 Correct 23 ms 98908 KB Output is correct
5 Correct 23 ms 98908 KB Output is correct
6 Correct 22 ms 98904 KB Output is correct
7 Correct 23 ms 98908 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 512 ms 113236 KB Output is correct
2 Correct 1191 ms 136952 KB Output is correct
3 Correct 1478 ms 158524 KB Output is correct
4 Correct 52 ms 106712 KB Output is correct
5 Correct 153 ms 121644 KB Output is correct
6 Correct 244 ms 140500 KB Output is correct

Subtask #3
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 98944 KB Output is correct
2 Correct 24 ms 98904 KB Output is correct
3 Correct 23 ms 98904 KB Output is correct
4 Correct 23 ms 98908 KB Output is correct
5 Correct 23 ms 98908 KB Output is correct
6 Correct 22 ms 98904 KB Output is correct
7 Correct 23 ms 98908 KB Output is correct
8 Correct 512 ms 113236 KB Output is correct
9 Correct 1191 ms 136952 KB Output is correct
10 Correct 1478 ms 158524 KB Output is correct
11 Correct 52 ms 106712 KB Output is correct
12 Correct 153 ms 121644 KB Output is correct
13 Correct 244 ms 140500 KB Output is correct
14 Correct 316 ms 100536 KB Output is correct
15 Correct 697 ms 109472 KB Output is correct
16 Execution timed out 1539 ms 159376 KB Time limit exceeded
17 Halted 0 ms 0 KB -