QOJ.ac

QOJ

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

Judging History

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

  • [2024-11-08 13:39:32]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:TL
  • 用时:1084ms
  • 内存:48804kb
  • [2024-11-08 13:39:28]
  • hack成功,自动添加数据
  • (/hack/1149)
  • [2024-10-01 16:00:39]
  • 评测
  • 测评结果:100
  • 用时:1065ms
  • 内存:48892kb
  • [2024-10-01 16:00:39]
  • 提交

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

詳細信息

Test #1:

score: 100
Accepted
time: 6ms
memory: 27848kb

input:

2
3 2 4
1 1
0 2
0 0
1 100 100
1000 1000

output:

34
1020100

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 530ms
memory: 31076kb

input:

6116
19 403875 4598
244446 658406
439472 600614
831502 516732
471917 520839
453020 604310
42306 699481
376843 270708
67164 501987
534254 381735
584472 43380
425780 946800
208487 272200
737998 300759
454500 397309
837634 156713
293648 671302
597485 524248
698078 141688
389057 265668
10 268299 760142
...

output:

379354128879726
104873326525021424
105606787645824723
708210768663783512
132912961393461646
202868704323232157
142763396656757487
31220157133721509
183522976883097753
60792387857469878
54087773825760948
13028977926188800
397834145111696233
64443345446763396
102402202407373004
24578007805918476
22181...

result:

ok 6116 lines

Test #3:

score: 0
Accepted
time: 839ms
memory: 34740kb

input:

6116
19 712953 722736
5686 60810
377083 350609
535028 763626
550340 834947
993495 995201
989872 934913
314598 292101
362688 320197
805489 860814
194143 73963
832924 870115
498063 456534
603643 839328
249060 131022
740139 845556
865334 928800
504864 499431
472982 433077
852053 894291
2 830795 685574
...

output:

369887957086041723
431841334366294875
308477305320984605
613664386014754638
357826753561485272
338658347975033029
426142209172666186
759666649386109551
378494587050071809
306219137754076618
607898503543409988
743634628947627450
223491301887405615
360966639876096830
398616574824535225
504497791642527...

result:

ok 6116 lines

Test #4:

score: 0
Accepted
time: 1084ms
memory: 33284kb

input:

6116
7 1000000 1000000
412334 537125
550637 537125
846976 462055
130053 462055
263751 537125
274893 462055
48620 537125
13 1000000 1000000
564915 923124
203670 765136
621916 339636
331226 448765
396601 765136
255282 50583
429851 339636
654810 339636
138494 448765
186497 448765
282100 50583
233299 50...

output:

1000001153532805335
1000000582954982857
1000001615181949269
1000001997185373760
1000001544547212292
1000001400049627238
1000000981793279458
1000000923184555598
1000001037042229556
1000001839767792582
1000001053880830252
1000000549232039823
1000000783602725738
1000001955176278477
1000000400154228860
...

result:

ok 6116 lines

Test #5:

score: 0
Accepted
time: 150ms
memory: 36632kb

input:

1
1000000 342269 953012
473985 235501
917204 100230
756706 510618
768364 407348
931604 127659
853933 179476
909155 968310
769785 680886
622841 228543
239160 97618
294588 675503
571602 81210
676816 615217
367042 405009
284074 735031
900597 770465
994923 433364
468269 645505
595488 277488
52201 87303
...

output:

211091849789153155

result:

ok single line: '211091849789153155'

Test #6:

score: 0
Accepted
time: 163ms
memory: 42984kb

input:

1
865193 617749 536531
577306 577305
334144 333316
218524 217512
409600 408899
924088 923692
510522 510309
722200 721676
872779 872541
292233 291306
501418 501237
893308 892862
972243 972077
37933 37174
848551 848469
977272 977132
443974 443592
639095 638462
333157 332325
961099 960942
828150 828081...

output:

158737140297421602

result:

ok single line: '158737140297421602'

Test #7:

score: 0
Accepted
time: 164ms
memory: 44736kb

input:

1
864322 865792 550280
959602 959616
758897 759684
150506 150749
418888 419528
804075 804410
65213 65455
212385 213207
486540 486928
484647 485135
811196 811450
893947 894330
863384 863748
475776 476396
500216 500597
396442 396999
582180 582559
730649 731072
481286 481826
230484 231253
775303 775991...

output:

283982082132780416

result:

ok single line: '283982082132780416'

Test #8:

score: 0
Accepted
time: 261ms
memory: 48428kb

input:

1
1000000 1000000 1000000
623164 107113
623164 948418
667542 261951
667542 516385
667542 586519
667542 330574
667542 496932
667542 11259
623164 188794
623164 598328
667542 860430
623164 909263
667542 134671
667542 241963
667542 130855
667542 639700
623164 237591
623164 835427
623164 492063
667542 40...

output:

1000001290708086130

result:

ok single line: '1000001290708086130'

Test #9:

score: 0
Accepted
time: 232ms
memory: 48804kb

input:

1
1000000 1000000 1000000
148005 130246
22954 694549
701374 844290
273280 844290
819874 615667
258850 844290
740006 615667
755675 844290
437784 694549
927035 615667
240736 694549
969223 694549
928325 662804
52986 130246
395176 694549
717785 694549
859887 615667
648063 130246
910409 130246
863155 662...

output:

999999947571940219

result:

ok single line: '999999947571940219'

Extra Test:

score: -3
Extra Test Failed : Time Limit Exceeded on 2

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: