QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#343698#3059. Buffalo BarricadesPetroTarnavskyi#WA 2ms5676kbC++203.8kb2024-03-02 21:41:422024-03-02 21:41:43

Judging History

你现在查看的是最新测评结果

  • [2024-03-02 21:41:43]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5676kb
  • [2024-03-02 21:41:42]
  • 提交

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;
}




Details

Tip: Click on the bar to expand more detailed information

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'