QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#343698 | #3059. Buffalo Barricades | PetroTarnavskyi# | WA | 2ms | 5676kb | C++20 | 3.8kb | 2024-03-02 21:41:42 | 2024-03-02 21:41:43 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
typedef tree<LL, null_type, less<LL>, rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
struct SegTree{
vector<set<int>> t;
int n;
void init(int _n)
{
n = 1;
while(n < _n)
n *= 2;
t.resize(2 * n - 1);
}
void upd(int v, int tl, int tr, int pos, int what, int y)
{
if(what == -1)
t[v].erase(y);
else
t[v].insert(y);
if(tl + 1 == tr)
return;
int tm = (tl + tr) / 2;
if(pos < tm)
upd(2 * v + 1, tl, tm, pos, what, y);
else
upd(2 * v + 2, tm, tr, pos, what, y);
}
int query(int v, int tl, int tr, int l, int r, int y)
{
if(r <= tl || tr <= l)
return 0;
if(l <= tl && tr <= r)
{
auto it = t[v].upper_bound(y);
if(it == t[v].begin())
return 0;
return *prev(it);
}
int tm = (tl + tr) / 2;
return max(query(2 * v + 1, tl, tm, l, r, y),
query(2 * v + 2, tm, tr, l, r, y));
}
void upd(int pos, int what, int y)
{
upd(0, 0, n, pos, what, y);
}
int query(int r, int y)
{
return query(0, 0, n, 0, r, y);
}
};
const int INF = 1e9;
struct SegTreeMX{
vector<PII> t;
int n;
void init(int _n)
{
n = 1;
while(n < _n)
n *= 2;
t.assign(2 * n - 1, MP(-INF, -1));
}
void upd(int v, int tl, int tr, int pos, PII val)
{
if(tl + 1 == tr)
{
t[v] = val;
return;
}
int tm = (tl + tr) / 2;
if(pos < tm)
upd(2 * v + 1, tl, tm, pos, val);
else
upd(2 * v + 2, tm, tr, pos, val);
t[v] = max(t[2 * v + 1], t[2 * v + 2]);
}
PII query(int v, int tl, int tr, int l, int r)
{
if(r <= tl || tr <= l)
return MP(-INF, -1);
if(l <= tl && tr <= r)
{
return t[v];
}
int tm = (tl + tr) / 2;
return max(query(2 * v + 1, tl, tm, l, r),
query(2 * v + 2, tm, tr, l, r));
}
void upd(int pos, PII val)
{
upd(0, 0, n, pos, val);
}
PII query(int v)
{
return query(0, 0, n, 0, v);
}
};
const int N = 1 << 19;
VI g[N];
SegTreeMX MX;
int cnt[N];
void dfs(int v, int d = 0)
{
MX.upd(v, MP(d, v));
for(int go : g[v])
{
dfs(go, d + 1);
}
MX.upd(v, MP(-INF, -1));
int to = MX.query(v).S;
if(to != -1)
cnt[to] += cnt[v];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
vector<tuple<int, int, int>> events;
int n;
cin >> n;
FOR(i, 0, n)
{
int x, y;
cin >> x >> y;
events.PB({x, -1, y});
}
int m;
cin >> m;
SegTree T;
T.init(m);
FOR(i, 0, m)
{
int x, y;
cin >> x >> y;
events.PB({x, i, y});
T.upd(i, 1, y);
}
sort(ALL(events));
multiset<int> byky;
multiset<PII> chely;
VI p(m, -1);
FOR(i, 0, n + m)
{
auto [x, t, y] = events[i];
if(t == -1)
{
byky.insert(y);
continue;
}
T.upd(t, -1, y);
int mny = T.query(t, y);
cnt[t] = 0;
while(true)
{
auto it = byky.upper_bound(y);
if(it == byky.begin() || *prev(it) <= mny)
break;
cnt[t]++;
byky.erase(prev(it));
}
while(true)
{
auto it = chely.upper_bound(MP(y, -1));
if(it == chely.begin() || prev(it)->F <= mny)
break;
p[prev(it)->S] = t;
chely.erase(prev(it));
}
chely.insert(MP(y, t));
}
MX.init(m);
FOR(i, 0, m)
{
if(p[i] != -1)
g[p[i]].PB(i);
}
FOR(i, 0, m)
if(p[i] == -1)
dfs(i);
FOR(i, 0, m)
{
cout << cnt[i] << "\n";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 5676kb
input:
7 1 1 4 2 6 2 5 3 2 5 4 7 7 5 4 4 4 8 2 9 6 6 5
output:
2 1 3 2
result:
ok 4 lines
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 5612kb
input:
10 64 37 51 67 97 74 45 85 1 23 87 85 67 58 67 25 36 19 34 11 10 88 5 3 27 95 88 63 56 28 61 93 89 82 51 96 24 49 26 22 52
output:
0 1 8 2 0 0 2 0 0 0
result:
wrong answer 9th lines differ - expected: '2', found: '0'