| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 789170 |
2023-07-21T06:57:43 Z |
이성호(#10043) |
Tourism (JOI23_tourism) |
C++17 |
|
5000 ms |
666724 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
int c[100005], verc[100005], ans[100005], ver[100005];
int N, K, M, Q, pv = 0;
vector<int> adj[100005];
const int inf = 1e9;
pair<int, int> ett[100005]; //(first, second)
vector<int> dot[300005];
struct Query
{
int sgn;
int id;
int y;
};
struct Calc
{
int id;
int l, r;
bool operator<(const Calc &c)
{
if (l / K == c.l / K) return r < c.r;
else return l < c.l;
}
};
Calc qr[100005];
vector<Query> query[300005];
void add_query(int sgn, int x1, int x2, int y1, int y2, int id)
{
Query q1, q2, q3, q4;
q1 = {sgn, id, y2};
q2 = {-sgn, id, y2};
q3 = {-sgn, id, y1-1};
q4 = {sgn, id, y1-1};
query[x2].push_back(q1); query[x2].push_back(q3);
query[x1-1].push_back(q2); query[x1-1].push_back(q4);
}
struct maxseg
{
int sz = 1 << 17;
vector<int> tree;
void init(int n, int* a)
{
tree.resize(2*sz);
for (int i = 1; i <= n; i++) tree[i+sz] = a[i];
for (int i = sz - 1; i >= 0; i--) tree[i] = max(tree[2*i], tree[2*i+1]);
}
int query(int l, int r)
{
int ans = 0;
for (l += sz, r += sz; l <= r; l >>= 1, r >>= 1) {
if (l & 1) ans = max(ans, tree[l++]);
if (!(r & 1)) ans = max(ans, tree[r--]);
}
return ans;
}
};
struct minseg
{
int sz = 1 << 17;
vector<int> tree;
void init(int n, int* a)
{
tree.resize(2*sz);
for (int i = 1; i <= n; i++) tree[i+sz] = a[i];
for (int i = sz - 1; i >= 0; i--) tree[i] = min(tree[2*i], tree[2*i+1]);
}
int query(int l, int r)
{
int ans = inf;
for (l += sz, r += sz; l <= r; l >>= 1, r >>= 1) {
if (l & 1) ans = min(ans, tree[l++]);
if (!(r & 1)) ans = min(ans, tree[r--]);
}
return ans;
}
};
struct FenWick
{
vector<int> tree;
int n;
FenWick(int N)
{
n = N;
tree.resize(N+1);
}
void upd(int i, int x)
{
for (; i <= n; i += i&-i) tree[i] += x;
}
int query(int i)
{
int ret = 0;
for (; i; ret += tree[i], i -= i&-i);
return ret;
}
};
void dfs(int v, int p)
{
if (p) ett[v].first = ++pv;
ver[v] = ++pv;
for (int i:adj[v]) {
if (i != p) {
dfs(i, v);
}
}
if (p) ett[v].second = ++pv;
}
set<int> curver;
void add(int id, int c)
{
if (curver.empty()) {
curver.insert(c);
return;
}
auto it = curver.lower_bound(c);
if (it == curver.end()) {
int s = *curver.begin(), e = *--curver.end();
add_query(1, 1, s, e, c-1, id);
}
else if (it == curver.begin()) {
int s = *it, e = *--curver.end();
add_query(1, c+1, s, e, pv, id);
}
int bef;
if (it == curver.begin()) bef = 1;
else {
bef = *--it + 1; ++it;
}
int aft;
if (it == curver.end()) aft = pv;
else aft = *it - 1;
add_query(1, bef, c, c, aft, id);
curver.insert(c);
}
void del(int id, int c)
{
curver.erase(c);
if (curver.empty()) return;
auto it = curver.lower_bound(c);
if (it == curver.end()) {
int s = *curver.begin(), e = *--curver.end();
add_query(-1, 1, s, e, c-1, id);
}
else if (it == curver.begin()) {
int s = *it, e = *--curver.end();
add_query(-1, c+1, s, e, pv, id);
}
int bef;
if (it == curver.begin()) bef = 1;
else {
bef = *--it + 1; ++it;
}
int aft;
if (it == curver.end()) aft = pv;
else aft = *it - 1;
add_query(-1, bef, c, c, aft, id);
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> N >> M >> Q;
K = sqrt(N);
for (int i = 1; i < N; i++) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 0);
for (int i = 2; i <= N; i++) dot[ett[i].first].push_back(ett[i].second);
for (int i = 1; i <= M; i++) {
cin >> c[i];
verc[i] = ver[c[i]];
}
maxseg Mseg; Mseg.init(N, verc);
minseg mseg; mseg.init(N, verc);
for (int i = 1; i <= Q; i++) {
cin >> qr[i].l >> qr[i].r;
qr[i].id = i;
}
sort(qr + 1, qr + Q + 1);
int nl = 1, nr = 0;
for (int i = 1; i <= Q; i++) {
while (nr < qr[i].r) add(qr[i].id, verc[++nr]);
while (nl > qr[i].l) add(qr[i].id, verc[--nl]);
while (nr > qr[i].r) del(qr[i].id, verc[nr--]);
while (nl < qr[i].l) del(qr[i].id, verc[nl++]);
}
FenWick fenWick(pv);
for (int i = 1; i <= pv; i++) {
for (int j:dot[i]) {
fenWick.upd(j, 1);
}
for (Query j:query[i]) {
int tmp = fenWick.query(j.y);
if (j.sgn == 1) ans[j.id] += tmp;
else ans[j.id] -= tmp;
}
}
for (int i = 1; i <= Q; i++) ans[i] += ans[i-1];
for (int i = 1; i <= Q; i++) cout << ans[i] + 1 << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
18772 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
18772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
18772 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
18772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
18772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
18772 KB |
Output is correct |
| 2 |
Incorrect |
87 ms |
31612 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
18772 KB |
Output is correct |
| 2 |
Correct |
9 ms |
20108 KB |
Output is correct |
| 3 |
Correct |
66 ms |
88668 KB |
Output is correct |
| 4 |
Execution timed out |
5119 ms |
666724 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
18772 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
18772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
