oj.uz

Submission #980595

# Submission time Handle Problem Language Result Execution time Memory
980595 2024-05-12T09:10:09 Z SamNguyen Radio (COCI22_radio) C++14
10 / 110
 1500 ms 107964 KB 
#include <bits/stdc++.h>
using namespace std;

template <class T>
inline bool MINIMISE(T &x, T y) {
    if (x > y) { x = y; return true; }
    return false;
}

template <class T>
inline bool MAXIMISE(T &x, T y) {
    if (x < y) { x = y; return true; }
    return false;
}

template <class T, class F>
void UNSAFE_FOR_LEFT_RIGHT(set<T> &x, T v, F f) {
	auto it = x.lower_bound(v);
	f(*prev(it), *it);
}

template <class T, int N>
class SegmentTree {
private:
	int n, st[4 * N];

	function<T(T, T)> fn_combine;
	T ZERO;

	void build(int id, int l, int r, int arr[]) {
		if (l == r) {
			st[id] = arr[r];
			return;
		}

		int m = (l + r) >> 1;
		build(id << 1, l, m, arr);
		build(id << 1 | 1, m + 1, r, arr);
		st[id] = fn_combine(st[id << 1], st[id << 1 | 1]);
	}

	void update(int id, int l, int r, int i, int v) {
		if (r < i or i < l)
			return;
		if (l == r) {
			st[id] = v;
			return;
		}

		int m = (l + r) >> 1;
		update(id << 1, l, m, i, v);
		update(id << 1 | 1, m + 1, r, i, v);
		st[id] = fn_combine(st[id << 1], st[id << 1 | 1]);
	}

	int query(int id, int l, int r, int left, int right) {
		if (r < left or right < l)
			return ZERO;
		if (left <= l and r <= right)
			return st[id];

		int m = (l + r) >> 1;
		return fn_combine(
			query(id << 1, l, m, left, right),
			query(id << 1 | 1, m + 1, r, left, right)
		);
	}

public:
	void init(int _n, function<T(T, T)> _fn, T _zero) {
		n = _n;
		fn_combine = _fn;
		ZERO = _zero;
		fill(st, st + 4 * n, ZERO);
	}

	void init(int _n, function<T(T, T)> _fn, T _zero, T arr[]) {
		n = _n;
		fn_combine = _fn;
		ZERO = _zero;
		build(1, 1, n, arr);
	}

	void update(int i, T v) { update(1, 1, n, i, v); }
	T query(T left, T right) { return query(1, 1, n, left, right); }
};

#define INPFILE "coci21c5p4.inp"
#define OUTFILE "coci21c5p4.out"

const int MAX = 1e6 + 7;
int PF[MAX];

void sieve() {
	iota(PF, PF + MAX, 0);
	for (int i = 2; i * i < MAX; i++) if (PF[i] == i)
	for (int j = i * i; j < MAX; j += i)
		PF[j] = i;
}

template <class F>
void FOR_PRIMES_UPTO(int N, F f) {
	for (int v = 2; v <= N; v++) if (PF[v] == v)
		f(v);
}

template <class F>
void FOR_FACTORS(int n, F f) {
	while (n > 1) {
		int p = PF[n], c = 0;
		while (n % p == 0)
			n /= p, c++;
		f(p, c);
	}
}

int N, Q;
SegmentTree<int, MAX> st_left, st_right;

bool is_online[MAX];
set<int> inds[MAX];

void init() {
	st_left .init(N, [](int x, int y) { return max(x, y); }, -MAX);
	st_right.init(N, [](int x, int y) { return min(x, y); }, +MAX);

	FOR_PRIMES_UPTO(N, [&](int p) {
		inds[p].insert(-MAX);
		inds[p].insert(+MAX);
	});

	memset(is_online, false, sizeof is_online);
}

void update_position(int i) {
    int li = -MAX, ri = +MAX;

    if (is_online[i])
        FOR_FACTORS(i, [&](int p, int c) {
            UNSAFE_FOR_LEFT_RIGHT(inds[p], i, [&](int l, int r) {
//                cerr << "p = " << p << " -> update " << l << " <-> " << i << " <-> " << r << endl;
                MAXIMISE(li, l);
                MINIMISE(ri, r);
            });
        });

    st_left .update(i, li);
    st_right.update(i, ri);
}

void update(int x) {
    is_online[x] ^= 1;

    if (not is_online[x])
        FOR_FACTORS(x, [&](int p, int c) {
            inds[p].erase(x);
        });

    vector<int> candidates;
    FOR_FACTORS(x, [&](int p, int c) {
        UNSAFE_FOR_LEFT_RIGHT(inds[p], x, [&](int l, int r) {
//            cerr << "p = " << p << " -> " << l << " " << r << endl;
            if (l >= 1 and l < x)
                candidates.push_back(l);
            if (r > x and r <= N)
                candidates.push_back(r);
        });
    });

    update_position(x);
    if (is_online[x])
        FOR_FACTORS(x, [&](int p, int c) {
            inds[p].insert(x);
        });

    for (int i : candidates)
        update_position(i);


//    cerr << "lefts:  ";
//	for (int i = 1; i <= N; i++)
//        cerr << st_left.query(i, i) << " ";
//    cerr << endl;
//    cerr << "rights: ";
//	for (int i = 1; i <= N; i++)
//        cerr << st_right.query(i, i) << " ";
//    cerr << endl;
}

bool query(int l, int r) {
//    cerr << "max_left  = " << st_left .query(l, r) << endl;
//    cerr << "min_right = " << st_right.query(l, r) << endl;
    return st_right.query(l, r) <= r and st_left .query(l, r) >= l;
}

int main(void) {
	if (fopen(INPFILE, "r")) {
		freopen(INPFILE, "r", stdin);
		freopen(OUTFILE, "w", stdout);
	}
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	sieve();
	cin >> N >> Q;

	init();
	while (Q--) {
		char t; cin >> t;
		if (t == 'S') {
			int x; cin >> x;
			update(x);
		}
		else {
			int l, r; cin >> l >> r;
			cout << (query(l, r) ? "DA" : "NE") << '\n';
			cout << flush;
		}
	}

	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:198:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  198 |   freopen(INPFILE, "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:199:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  199 |   freopen(OUTFILE, "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 56920 KB Output is correct
2 Correct 14 ms 56924 KB Output is correct
3 Correct 14 ms 56924 KB Output is correct
4 Correct 13 ms 56924 KB Output is correct
5 Correct 13 ms 56944 KB Output is correct
6 Correct 16 ms 56924 KB Output is correct
7 Correct 13 ms 56924 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 678 ms 67572 KB Output is correct
2 Correct 1308 ms 91988 KB Output is correct
3 Execution timed out 1535 ms 107964 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 56920 KB Output is correct
2 Correct 14 ms 56924 KB Output is correct
3 Correct 14 ms 56924 KB Output is correct
4 Correct 13 ms 56924 KB Output is correct
5 Correct 13 ms 56944 KB Output is correct
6 Correct 16 ms 56924 KB Output is correct
7 Correct 13 ms 56924 KB Output is correct
8 Correct 678 ms 67572 KB Output is correct
9 Correct 1308 ms 91988 KB Output is correct
10 Execution timed out 1535 ms 107964 KB Time limit exceeded
11 Halted 0 ms 0 KB -