QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#291679#4817. Half PlaneRadewoosh#TL 10917ms201060kbC++235.0kb2023-12-27 02:50:262023-12-27 02:50:27

Judging History

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

  • [2023-12-27 02:50:27]
  • 评测
  • 测评结果:TL
  • 用时:10917ms
  • 内存:201060kb
  • [2023-12-27 02:50:26]
  • 提交

answer

//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//~ #pragma GCC target ("avx2")
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define shandom_ruffle random_shuffle

using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int nax=1000*1007;
const ll mod=1000*1000*1000+7;

int n, q;

struct vec
{
	ll w[3];
	vec()
	{
		for (int i=0; i<3; i++)
			w[i]=0;
	}
	void czyt()
	{
		for (int i=0; i<3; i++)
			scanf("%lld", &w[i]);
	}
};

struct mac
{
	ll w[3][3];
	mac()
	{
		for (int i=0; i<3; i++)
			for (int j=0; j<3; j++)
				w[i][j]=0;
	}
	mac(ll v)
	{
		for (int i=0; i<3; i++)
			for (int j=0; j<3; j++)
				w[i][j]=(i==j)*v;
	}
	void czyt()
	{
		for (int i=0; i<3; i++)
			for (int j=0; j<3; j++)
				scanf("%lld", &w[i][j]);
	}
};

vec operator +(const vec &a, const vec &b)
{
	vec ret=vec();
	for (int i=0; i<3; i++)
		ret.w[i]=(a.w[i]+b.w[i])%mod;
	return ret;
}

mac operator *(const mac &a, const mac &b)
{
	mac ret=mac();
	for (int i=0; i<3; i++)
		for (int j=0; j<3; j++)
			for (int l=0; l<3; l++)
				ret.w[i][l]=(ret.w[i][l]+a.w[i][j]*b.w[j][l])%mod;
	return ret;
}

vec operator *(const mac &a, const vec &b)
{
	vec ret=vec();
	for (int i=0; i<3; i++)
		for (int j=0; j<3; j++)
			ret.w[i]=(ret.w[i]+a.w[i][j]*b.w[j])%mod;
	return ret;
}

pll tab[nax];
vec vectab[nax];

bool mniej1(int a, int b)
{
	return tab[a]<tab[b];
}

bool mniej2(int a, int b)
{
	pll aa=tab[a];
	pll bb=tab[b];
	swap(aa.first, aa.second);
	swap(bb.first, bb.second);
	return aa<bb;
}

int m;

pll px[nax];
pll py[nax];
mac narz[nax];
vec pod[nax];
vi dz[nax];

vec daj(int v)
{
	return narz[v]*pod[v];
}

void push(int v)
{
	for (int i : dz[v])
		narz[i]=narz[v]*narz[i];
	narz[v]=mac(1);
}

void upd(int v)
{
	pod[v]=daj(dz[v][0])+daj(dz[v][1]);
}

int nal[nax];

int build(vector<vi> wek, int parz)
{
	if ((int)wek[0].size()==1)
	{
		int kt=wek[0][0];
		m++;
		pod[m]=vectab[kt];
		narz[m]=mac(1);
		px[m]={tab[kt].first, tab[kt].first};
		py[m]={tab[kt].second, tab[kt].second};
		return m;
	}
	int r=wek[0].size();
	for (int i=0; i<r; i++)
		nal[wek[parz][i]]=(2*i<r);
	
	vector<vector<vi>> podz(2, vector<vi>(2));
	
	for (int h=0; h<2; h++)
		for (int i : wek[h])
			podz[nal[i]][h].push_back(i);
	
	m++;
	int tu=m;
	dz[tu].push_back(build(podz[0], parz^1));
	dz[tu].push_back(build(podz[1], parz^1));
	px[tu]={min(px[dz[tu][0]].first, px[dz[tu][1]].first), max(px[dz[tu][0]].second, px[dz[tu][1]].second)};
	py[tu]={min(py[dz[tu][0]].first, py[dz[tu][1]].first), max(py[dz[tu][0]].second, py[dz[tu][1]].second)};
	pod[tu]=daj(dz[tu][0])+daj(dz[tu][1]);
	narz[tu]=mac(1);
	return tu;
}

ll ga, gb, gc;

mac glomac;
vec wyn;

void szuk(int v)
{
	ll mini=min(ga*px[v].first, ga*px[v].second)+min(gb*py[v].first, gb*py[v].second);
	ll maxi=max(ga*px[v].first, ga*px[v].second)+max(gb*py[v].first, gb*py[v].second);
	if (mini>=gc)
	{
		return;
	}
	if (maxi<gc)
	{
		wyn=wyn+daj(v);
		narz[v]=glomac*narz[v];
		return;
	}
	assert(!dz[v].empty());
	push(v);
	for (int i : dz[v])
		szuk(i);
	upd(v);
}

int main()
{
	scanf("%d", &n);
	for (int i=1; i<=n; i++)
	{
		ll x, y;
		vec w;
		scanf("%lld%lld", &x, &y);
		tab[i]={x, y};
		vectab[i].czyt();
	}
	vi k1, k2;
	for (int i=1; i<=n; i++)
		k1.push_back(i);
	k2=k1;
	sort(k1.begin(), k1.end(), mniej1);
	sort(k2.begin(), k2.end(), mniej2);
	int korz=build({k1, k2}, 0);
	scanf("%d", &q);
	while(q--)
	{
		scanf("%lld%lld%lld", &ga, &gb, &gc);
		glomac.czyt();
		wyn=vec();
		
		szuk(korz);
		
		for (int i=0; i<3; i++)
			printf("%lld ", wyn.w[i]);
		printf("\n");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 18ms
memory: 149432kb

input:

5
1 1 2 3 4
12 12 4 6 1
1 12 5 1 2
12 1 1 5 5
6 6 2 0 3
3
1 1 4 1 1 2 3 4 5 2 3 4
1 1 400 1 3 4 2 1 2 3 4 5
-1 -1 -10 3 2 1 4 6 5 4 3 2

output:

2 3 4 
25 50 40 
92 58 139 

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 8ms
memory: 146648kb

input:

8
-509 1134 869419079 764178960 818736647
-2836 296 965929020 482991943 829626659
1594 -1045 289612318 572608619 474362463
-2946 -165 85255903 285022572 770151631
-74 -131 732523347 283776652 211209006
-627 -604 539714672 763810142 817996815
-1187 -1219 734874008 764773559 261445054
-18 226 31476550...

output:

242481509 621755738 615459217 
984440526 242571329 417013116 
122667367 215125161 518083968 
594780462 21825000 214574293 

result:

ok 4 lines

Test #3:

score: 0
Accepted
time: 192ms
memory: 153280kb

input:

30000
676 -1234 836467424 502287177 140023561
-2003 -54 939673593 585085650 422504901
14185 -49892 469301115 424738168 942143157
-6019 4933 573698653 956514739 385606216
-1097 -1767 918532462 279450765 873950517
-2732 5210 428418604 607751438 2805137
-2791 1240 250817926 463999452 951276698
-3460 -5...

output:

538200103 176562537 786040129 
282120049 585253989 126746038 
442585365 946639191 152848161 
309217862 352168103 288017696 
798331649 483116583 428411187 
396357116 876189623 301235280 
832917758 314259493 851554086 
129794051 40695662 730810045 
922712284 511389451 59925242 
580263289 336968685 459...

result:

ok 1000 lines

Test #4:

score: 0
Accepted
time: 185ms
memory: 157728kb

input:

30000
-861 514 579191255 606538526 388715812
-2743 143 33760465 13211059 128903675
105 -1848 31959805 331710130 184775255
19 -1110 445507093 115980536 539879344
-1041 41 507163898 642632299 488129195
1471 81 294281682 547102977 542058890
804 -843 987425295 849386341 831783549
-1793 -2178 444562260 3...

output:

545178258 677491591 34959177 
426445915 979131304 126183119 
215187507 759685069 499663658 
200968299 790214661 15389717 
839830981 763311704 525155406 
857030222 464548447 842171760 
658456271 313959441 663157301 
771261247 935340775 339842291 
94545060 716008509 891433021 
347612571 574108893 9409...

result:

ok 1000 lines

Test #5:

score: 0
Accepted
time: 183ms
memory: 153632kb

input:

30000
10549 19178 551387003 459346332 265437020
-4440 -801 346488842 634142290 954669423
-1758 964 418335341 620928953 575285343
-4434 4081 109829333 799485017 24011325
-4527 -24166 664063304 756571635 986936785
-2020 -826 968644308 698506784 869326786
-2700 -7894 94755543 255350611 433336916
-6626 ...

output:

93567974 334118538 550727969 
788441432 886909715 475552713 
526828502 419035304 422234431 
226030179 753442982 68364174 
453395418 329482885 434105443 
15411089 926245366 274889354 
829805395 617738666 67824539 
591388868 172923133 108968027 
491445793 193764448 630342293 
185049502 34074677 601638...

result:

ok 1000 lines

Test #6:

score: 0
Accepted
time: 147ms
memory: 157704kb

input:

30000
729570 -682315 124492027 232374133 480672372
-89810 -111355 986358898 821368981 395456251
167275 -156587 366703017 453206326 674212301
362570 -471220 637350218 819423356 510777066
-256566 369328 923342730 723162512 203219131
-85619 132807 403845003 932528656 550721085
58246 68727 988188769 670...

output:

177234170 706893826 321822432 
51918258 607410764 301981413 
520332556 577378859 923040905 
748810147 59692955 792648057 
715348611 655896889 617831176 
601836304 718124476 848465506 
797797405 409159165 810850490 
467212419 781133102 681159662 
508324225 694481060 155771698 
74229267 592178614 4395...

result:

ok 1000 lines

Test #7:

score: 0
Accepted
time: 137ms
memory: 157732kb

input:

30000
215276 568757 143058747 670589199 352546244
675349 276797 890016278 179562506 916859284
485993 366119 538889148 285689789 926460934
-184492 100853 168179724 850340050 328350589
542050 68798 786636421 318440051 561731640
226406 81944 652753350 969237706 547819021
-143180 485953 369758464 939858...

output:

365510556 899423656 472212247 
119697678 211030227 547616991 
943724197 8064634 987392937 
751180665 973505281 385971334 
146010557 420227720 902462073 
950046809 985538196 710838208 
550105062 384450812 364915306 
671184632 124125952 829362702 
960089545 335852503 982532966 
451317766 825994835 318...

result:

ok 1000 lines

Test #8:

score: 0
Accepted
time: 169ms
memory: 157744kb

input:

30000
11963 26612 563932814 736535581 744632517
-2996 -641 649230390 398487502 776589770
1657 10623 794968118 747797397 59585526
-1289 4706 836020237 90456178 741776740
10179 -7004 847704879 346040819 168119367
21602 16579 515124205 829841195 234479530
-9495 4238 514818687 716733774 820045998
11361 ...

output:

847073709 381148374 516974732 
325834948 765765564 453516874 
352025353 10436598 371323304 
519640707 574307750 444125010 
964483737 141341740 498601658 
122304331 399174936 431259077 
742526585 700279913 545695293 
236747120 378183966 111872419 
373973546 315782774 219011044 
653194034 928721309 67...

result:

ok 1000 lines

Test #9:

score: 0
Accepted
time: 158ms
memory: 157804kb

input:

30000
2313 20 151184035 531728233 996237244
515 -436 420930337 404861517 994681405
2926 -1322 689432222 234158944 272476457
52 530 390434030 44056866 776993283
-120 125 513404791 337625507 139274204
-1510 -588 855754494 303354450 351544403
291 419 471802575 810180275 84881798
-926 203 191026997 8895...

output:

935216674 480722085 384576623 
621069889 322955919 600300871 
538133841 334312373 608592766 
399447778 295652105 484049427 
606144001 591324118 339546480 
453328653 101855275 823859765 
818910344 986178644 528468199 
516357332 825796558 402562947 
380183389 14261509 250494299 
809568025 37546310 730...

result:

ok 1000 lines

Test #10:

score: 0
Accepted
time: 989ms
memory: 158020kb

input:

30000
-3 0 18053028 724837864 201780269
4 -1 369642866 720614816 646577044
-2 3 992365366 938793416 407081706
1 -4 738991115 509688102 673930606
-5 -3 948082291 588327493 257752862
158959 -317919 21154757 755166158 63273074
-231604 463212 308429264 964756648 833312195
-274206 137101 54048637 8096471...

output:

862026374 343842668 392567836 
26146542 777447884 265002500 
519892143 987619881 426932515 
307747538 901692231 98873625 
299878208 896834820 396084450 
518123452 367206424 423709655 
492309974 426180612 43588029 
93883631 234933962 816430356 
941272925 469347297 418005544 
712877801 820259786 20711...

result:

ok 1000 lines

Test #11:

score: 0
Accepted
time: 220ms
memory: 153632kb

input:

30000
-628784 -314394 968049914 611010155 822556658
-3 0 838684476 988751102 498207269
6 -1 158444020 203447175 827072499
-2 2 841964319 627180884 755281158
0 1 413763717 628446147 347356885
-284050 284052 94365801 261989175 608758104
-581295 -290648 374291550 717086259 564713688
73891 -55417 174966...

output:

957939759 686088484 588606155 
357666270 89551368 871461447 
304416932 448365469 240287435 
189543262 819930261 29529388 
991099953 449913997 43461210 
477390988 422207149 985823068 
562575922 578008854 565415569 
204689372 295956274 353515327 
903410183 296376364 476833877 
243697219 390369978 5738...

result:

ok 1000 lines

Test #12:

score: 0
Accepted
time: 849ms
memory: 158016kb

input:

30000
-999828 -999830 173576982 203686018 994555951
-998603 -998590 115320595 714379127 71972197
-998454 -998461 582494909 402300032 56908643
-999936 -999947 309327006 413646683 29938844
-998533 -998540 405243148 585079102 398415243
-999121 -999124 461176875 806714912 415591127
-999368 -999360 81873...

output:

706781663 971336842 722570837 
901431625 707596220 681677130 
732352331 871961411 695587377 
408559767 167863511 861911926 
896487900 934792684 147141981 
493733093 18703611 340196993 
985805162 566839384 988513262 
491465851 966179587 213337874 
679343318 939892014 685452506 
271297173 725622566 52...

result:

ok 1000 lines

Test #13:

score: 0
Accepted
time: 808ms
memory: 157808kb

input:

30000
-998172 -998163 303367951 336827340 741891676
-998613 -998627 978906198 787402624 411749183
-999756 -999760 209847555 827753782 828064940
-998721 -998722 57298138 24146456 133315754
-999055 -999049 485766055 400319901 927614503
-999515 -999512 819375843 657191016 397525265
-998927 -998917 5628...

output:

344833859 511256074 589227250 
160649192 831110888 812776997 
364036365 231766374 134127815 
561228840 82616806 21344553 
492460416 411409491 673466870 
81178955 7782751 53224357 
668188185 936366293 846510789 
447219778 260304026 996347527 
195850491 714970045 82351025 
519868498 352974360 74737778...

result:

ok 1000 lines

Test #14:

score: 0
Accepted
time: 9171ms
memory: 200592kb

input:

300000
6021 230 81186458 630223908 123502523
2206 -531 689274343 832968795 677935
-341 -5215 716916582 683843861 647948947
2201 -1132 238585560 881522585 759965041
-177 -1074 8264009 559321916 639075365
6108 6279 962302528 744228952 68956569
-4693 -2455 441948155 503678773 745829679
-420 -13854 4728...

output:

82983903 179991622 106488484 
681002891 958372672 310322005 
363534694 53035454 56365650 
7875167 569276234 649871689 
308858221 563321281 619554189 
592339933 652542820 630728333 
751354771 257358842 153279350 
641615783 461178965 609603439 
461431233 661609045 84919622 
531356919 122787693 6855663...

result:

ok 15000 lines

Test #15:

score: 0
Accepted
time: 10917ms
memory: 199368kb

input:

300000
-1541 2074 483711051 775771378 933380329
-1202 937 14941100 95502583 406917332
-397 933 119936225 788956255 184399251
-2102 3773 467131826 239645751 2290676
2072 -263 932141083 104521580 379780700
1158 -1549 370331747 922535291 448464108
-229 -2937 703381418 812044117 231275901
6736 6078 1912...

output:

151554358 46645906 509711997 
957929736 124465982 921338614 
780537979 152135527 222940084 
898910633 706590019 155412491 
666177849 668780531 141518722 
120573053 841195759 693067816 
673859081 914870171 539596578 
797525561 762342396 893229210 
666026033 522635102 678158674 
324491661 430885376 14...

result:

ok 15000 lines

Test #16:

score: 0
Accepted
time: 9573ms
memory: 197072kb

input:

300000
-1429 3885 869722740 460347054 807234428
3210 -4073 740106320 769063122 1794249
-5330 999 825552652 687199472 471974260
3992 -13122 563236 12365054 26764156
5815 12317 619466573 742538443 90994367
3260 -11043 547395011 86980825 479243959
-4918 -5000 463639498 694648153 191692996
-8213 704 355...

output:

70369296 802723337 485242181 
778408067 101136699 578430827 
59236084 859831660 652901410 
487792116 558581293 540295156 
397927035 696155263 604985519 
532561270 256798053 163000549 
660547771 964952980 130194673 
795610991 542049320 508344297 
837462486 8411881 118887485 
624170576 492134445 60500...

result:

ok 15000 lines

Test #17:

score: 0
Accepted
time: 8487ms
memory: 200800kb

input:

300000
-48956 176288 294568837 681990844 108484875
465540 30060 594194061 432722326 975809276
322853 86233 624880701 636519647 123533058
39572 123790 52446149 837375344 874805784
242075 16355 814153380 808465176 310264045
724220 141800 250042243 452069985 785962576
-15397 -302885 721918671 849665682...

output:

217164511 890555989 468580431 
873672440 10416005 335152754 
168260096 296116507 515183079 
643587763 110241008 532159647 
292054849 298856232 32579311 
817235669 740795802 947667483 
811580830 305170089 60911106 
943907963 645552165 485781477 
775206500 940421299 273866375 
614646408 207555416 1979...

result:

ok 15000 lines

Test #18:

score: 0
Accepted
time: 7046ms
memory: 196240kb

input:

300000
548861 388115 822669343 873492273 64551335
142114 483309 73323733 377207989 401490383
409937 433860 468438030 733460962 86587324
-95314 -724737 220585189 596749522 236182178
-232292 101582 962016830 94900027 376733896
-471250 -383514 546101196 384906647 735431088
-613815 -28324 935120004 2278...

output:

840102999 395990206 325451803 
635747567 312896695 686169301 
32392523 67192111 801889682 
905088946 148676049 290362045 
845729578 970554643 850798992 
755069476 398969651 75952502 
393532004 199951181 778505295 
554172772 657233299 368574943 
475330407 790333939 809810988 
488164236 296809553 2458...

result:

ok 15000 lines

Test #19:

score: 0
Accepted
time: 9732ms
memory: 201060kb

input:

300000
5682 9377 949323658 553347341 444480700
-558 12821 479233963 838560675 503993160
-90072 99174 64550749 372042921 157455703
33629 -18539 910752028 675178989 6183338
4094 -9068 571409045 855828101 666318228
7362 -3223 994148664 59458754 429764351
18143 15935 497100086 130510740 101003327
19627 ...

output:

134876512 996773578 290017641 
12972555 545073419 36920150 
163613612 148286639 953392953 
549979315 813956825 439846140 
461903687 393685137 111966526 
384221517 205800294 614191703 
398427965 265931649 896187620 
398769200 244677051 117091887 
858689143 583789209 164596528 
320325883 648990746 692...

result:

ok 15000 lines

Test #20:

score: 0
Accepted
time: 8516ms
memory: 200432kb

input:

300000
547 690 346545624 337977798 795059761
45 -551 949642049 482808092 690979844
3219 -718 283653294 808205832 301230355
-642 434 137063134 719417339 556377894
1348 -877 935715166 762762998 429929218
-580 1119 98934045 111915923 121943244
-160 1552 415902936 660527333 715593097
562 267 940796772 8...

output:

676314820 153422372 531726977 
957088456 516181215 376785017 
411232593 251615075 698932972 
872121538 638474993 392125420 
184376465 170196693 682538955 
162640120 365396981 315291403 
899719122 784781991 193165169 
900756271 249147967 727724517 
558035587 964383737 923478314 
673082882 410404532 2...

result:

ok 15000 lines

Test #21:

score: -100
Time Limit Exceeded

input:

300000
-160874 -321740 650679894 682085901 118564431
1 3 829284607 674413386 589242129
-1 -5 128251902 861925529 227295077
2 0 483335001 136506986 627827042
373064 -186531 980063766 887583003 124536602
-556935 278464 203163296 576564387 284484406
0 -8 370263598 946662142 724897316
-322063 -161035 16...

output:

270929648 657292934 1072391 
355748333 538055525 893060481 
923071675 138126180 897616241 
368606556 247572560 663225792 
935528969 985474533 765493326 
906004891 660594616 73269130 
270889963 986581893 508328370 
548082638 466247003 942212565 
541968798 644553201 603406730 
130543301 125334160 6988...

result: