| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 692257 |
2023-02-01T09:03:18 Z |
vjudge1 |
Radio (COCI22_radio) |
C++17 |
|
1500 ms |
106356 KB |
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/* DEFINES */
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define vv(a) vector<a>
#define pp(a, b) pair<a, b>
#define pq(a) priority_queue<a>
#define qq(a) queue<a>
#define ss(a) set<a>
#define mm(a, b) map<a, b>
#define ump(a, b) unordered_map<a, b>
#define sync \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define elif else if
#define endl "\n"
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define pb push_back
#define logi(a) __lg(a)
#define sqrt(a) sqrtl(a)
#define mpr make_pair
#define ins insert
using namespace std;
using namespace __gnu_pbds;
using namespace __cxx11;
typedef char chr;
typedef basic_string<chr> str;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll sz = 1e6 + 5;
ll prime[sz];
void precomp()
{
for (ll i = 2; i < sz; i++)
prime[i] = i;
for (ll i = 2; i < sqrt(sz); i++)
if (prime[i] == i)
for (ll j = i * i; j < sz; j += i)
prime[j] = i;
}
pp(ll, ll) cmp(pp(ll, ll) a, pp(ll, ll) b)
{
return mpr(max(a.F, b.F), min(a.S, b.S));
}
struct SegTree
{
ll n;
vv(pp(ll, ll)) st;
SegTree(ll Sz = 0, bool input = false)
{
n = Sz;
st.resize((n + 1) << 1, mpr(0, sz));
}
void set(ll i, pp(ll, ll) val)
{
st[i + n - 1] = val;
}
void build()
{
for (ll i = n - 1; i >= 1; i--)
st[i] = cmp(st[i << 1], st[i << 1 | 1]);
}
void modify(ll p, pp(ll, ll) val)
{
for (st[p += n - 1] = val; p > 1; p >>= 1)
st[p >> 1] = cmp(st[p], st[p ^ 1]);
}
pp(ll, ll) query(ll l, ll r)
{
pp(ll, ll) ans = mpr(0, sz);
for (l += n - 1, r += n; l < r; l >>= 1, r >>= 1)
{
if (l & 1)
ans = cmp(ans, st[l++]);
if (r & 1)
ans = cmp(ans, st[--r]);
}
return ans;
}
};
SegTree st(sz);
ss(ll) s[sz];
void calc(ll x)
{
ll v = x;
pp(ll, ll) best = mpr(0, sz);
while (v > 1)
{
ll p = prime[v];
while (v % p == 0)
v /= p;
if (s[p].empty())
continue;
if (*s[p].begin() > x)
best = cmp(best, mpr(0, *s[p].begin()));
elif (*s[p].rbegin() < x)
best = cmp(best, mpr(*s[p].rbegin(), sz));
else
best = cmp(best, mpr(*--s[p].lower_bound(x), *s[p].upper_bound(x)));
}
st.modify(x, best);
}
void add(ll x)
{
ll v = x;
pp(ll, ll) best = mpr(0, sz);
while (v > 1)
{
ll p = prime[v];
while (v % p == 0) v /= p;
if (s[p].empty())
s[p].ins(x);
elif (*s[p].begin() > x)
best = cmp(best, mpr(0, *s[p].begin())), s[p].ins(x), calc(*s[p].begin());
elif (*s[p].rbegin() < x)
best = cmp(best, mpr(*s[p].rbegin(), sz)), s[p].ins(x), calc(*s[p].rbegin());
else
best = cmp(best, mpr(*--s[p].lower_bound(x), *s[p].upper_bound(x))), s[p].ins(x), calc(*--s[p].lower_bound(x)), calc(*s[p].upper_bound(x));
}
}
void remove(ll x)
{
ll v = x;
st.modify(x, mpr(0, sz));
while (v > 1)
{
ll p = prime[v];
while (v % p == 0) v /= p;
s[p].erase(x);
if (s[p].empty())
continue;
if (*s[p].begin() > x)
calc(*s[p].begin());
elif (*s[p].rbegin() < x)
calc(*s[p].rbegin());
else
calc(*--s[p].lower_bound(x)), calc(*s[p].upper_bound(x));
}
}
bool query(ll l, ll r)
{
pp(ll, ll) ans = st.query(l, r);
return ans.F >= l or ans.S <= r;
}
void solve()
{
ll n, q;
cin >> n >> q;
bool us[n + 1];
memset(us, 0, sizeof(us));
while (q--)
{
chr c;
cin >> c;
if (c == 'S')
{
ll x;
cin >> x;
us[x] = !us[x];
if (!us[x])
remove(x);
else
add(x);
}
else
{
ll l, r;
cin >> l >> r;
cout << (query(l, r) ? "DA\n" : "NE\n");
}
}
}
/*
*/
int main()
{
sync
precomp();
ll t = 1;
// cin >> t;
for (ll i = 1; i <= t; i++)
// cout << "Case #" << i << ": ",
solve();
cerr << "\nTime elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
86424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
718 ms |
93284 KB |
Output is correct |
| 2 |
Correct |
1404 ms |
102928 KB |
Output is correct |
| 3 |
Execution timed out |
1600 ms |
106356 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
86424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
