QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#1149#603340#9433. TrailsyeVegeTablekaritoSuccess!2024-11-08 13:39:052024-11-08 13:39:05

详细

Extra Test:

Time Limit Exceeded

input:

1000000
1 1000000 1000000
814907 135507
1 1000000 1000000
905995 835196
1 1000000 1000000
127015 969086
1 1000000 1000000
913581 221083
1 1000000 1000000
632501 308236
1 1000000 1000000
97562 547343
1 1000000 1000000
278560 188424
1 1000000 1000000
547004 993104
1 1000000 1000000
957722 996685
1 100...

output:

1000001839989397151
1000001984508599980
1000001973013541710
1000001932687771777
1000001745778421764
1000001591506122234
1000001414497610560
1000001996877139584
1000001999860848430
1000001998881289240
1000001769198236704
1000001999456041370
1000001962066121548
1000001896215405060
1000001859743535840
...

result:


ID题目提交者结果用时内存语言文件大小提交时间测评时间
#603340#9433. Trailskarito#TL 1084ms48804kbC++172.9kb2024-10-01 16:00:392024-11-08 13:39:32

answer

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

class xds {
private:
	struct node {
		node* lc, * rc;
		int mx;
		~node()
		{
			delete lc;
			delete rc;
		}
	};
	node* _build(int l, int r)
	{
		if (r == l + 1)
			return new node{ nullptr,nullptr,0 };
		int mid = (l + r) / 2;
		return new node{ _build(l,mid),_build(mid,r),0 };
	}
	void chg(node* rt,int l, int r, int p, int x)
	{
		if (r <= x || l > x)
			return;
		if (r == l + 1)
		{
			rt->mx = x;
			return;
		}
		int mid = (l + r) / 2;
		chg(rt->lc, l, mid, p, x), chg(rt->rc, mid, r, p, x);
		rt->mx = max(rt->lc->mx, rt->rc->mx);
	}
	int query(node* rt, int l, int r, int left, int right)
	{
		if (l >= right || r <= left)
			return 0;
		if (l <= left && r >= right)
			return rt->mx;
		int mid = (l + r) / 2;
		return max(query(rt->lc, l, mid, left, right), query(rt->rc, mid, r, left, right));
	}
	node* root;
	int left, right;
public:
	void build(int l, int r)
	{
		left = l, right = r;
		root = _build(l, r);
	}
	void chg(int p, int x)
	{
		chg(root, left, right, p, x);
	}
	int query(int l, int r)
	{
		return query(root, left, right, l, r);
	}
	~xds()
	{
		delete root;
	}
};

int lowbit(int x)
{
	return x & -x;
}

const int N = 1e6 + 10;

int tr[N];


void update(int x, int c,int siz)
{
	x++;
	for (int i = x; i <= siz; i += lowbit(i))
		tr[i] = max(tr[i], c);
}

int query(int x)
{
	int ans = 0;
	x++;
	if (x <= 0) return 0;
	for(int i=x;i;i-=lowbit(i))
		ans=max(ans,tr[i]);
	return ans;
}

void clear(int siz)
{
	for(int i=1;i<=siz;i++) tr[i]=0;
}

void work();

int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--)
		work();
	return 0;
}

vector<int> pos[1000010];

bool cmp(const pair<int, int>& x, const pair<int, int>& y)
{
	if (x.first == y.first)
		return x.second > y.second;
	return x.first < y.first;
}

void work()
{
	long long n, p, q;
	cin >> n >> p >> q;
	vector<pair<int, int>> nod;
	for (int i = 0; i < n; i++)
	{
		pair<int, int>x;
		cin >> x.first >> x.second;
		if (x.first < 0 || x.first >= p || x.second < 0 || x.second >= q)
			continue;
		nod.push_back(x);
	}
	sort(nod.begin(), nod.end(),cmp);
	//xds tr;
	clear(q + 5);
	vector<int> ct;
	int mxt = 0;
	//vector<pair<int, int>> tmp;
	for (auto i:nod)
	{
		int t = query(i.second-1) + 1;
		ct.push_back(t);
		update(i.second, t, q + 5);
		mxt = max(mxt, t);
	}
	for (int i = 0; i <= mxt; i++)
		pos[i].clear();
	for (int i = 0; i < nod.size(); i++)
		pos[ct[i]].push_back(i);
	long long sm = 0;
	for (int i = 0; i <= mxt; i++)
	{
		long long bef = q;
		for (auto j : pos[i])
		{
			if (nod[j].second >= bef)
				continue;
			sm += (p - nod[j].first) * (bef - nod[j].second);
			bef = nod[j].second;
		}
	}
	cout << (p + q) * (p + 1) * (q + 1) / 2 - sm << '\n';
}