QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#744190#879. Exhaustive ExperimentciuimAC ✓139ms25736kbC++142.9kb2024-11-13 21:06:252024-11-13 21:06:34

Judging History

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

  • [2024-11-13 21:06:34]
  • 评测
  • 测评结果:AC
  • 用时:139ms
  • 内存:25736kb
  • [2024-11-13 21:06:25]
  • 提交

answer

bool M1;
#define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<" MB\n"
#define look_time cerr<<(clock()-Time)*1.0/CLOCKS_PER_SEC<<'\n'
#include <cstdio>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <cstring>
#include <array>
#include <algorithm>
#include <queue>
#include <vector>
#include <bitset>
#include <ctime>
#include <cstdlib>
#include <random>
#include <set>
#include <ctime>
#include <map>
#include <stack>
#include <unordered_map>
#include <assert.h>
#include <unordered_set>
#define i128 __int128
#define ll long long
#define uint unsigned
#define ull unsigned long long
#define ld long double
#define fo(a,b,c) for(ll a=b;a<=c;++a)
#define re(a,b,c) for(ll a=b;a>=c;--a)
#define pii pair<ll,ll>
#define pdd pair<db,db>
#define fi first
#define pb push_back
#define se second
#define ite set<ll> ::iterator
#define vite vector<ll> ::iterator
using namespace std;
const ll mod=998244353;
inline ll gi()
{
	ll x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = (x<<1) + (x<<3) + (ch^48);
		ch = getchar();
	}
	return x * f;
}
ll _=1;
const ll inf=2e17+5,iinf=1e9+5;
const ll N=200005;
ll cnt=0;
struct IO
{
	ll x,y;
	char c;
}px[N];
bool cmp(IO za,IO zb)
{
	if(za.y==zb.y)
	{
		return za.x>zb.x;
	}
	return za.y<zb.y;
}
bool tmp(IO za,IO zb)
{
	if(za.x!=zb.x) return za.x<zb.x;
	else return za.y>zb.y;
}
multiset<pii> ss;
IO pp[N];
void sol()
{
	ll n=gi();
	fo(i,1,n)
	{
		px[i].x=gi();
		px[i].y=gi();
		char c;
		cin>>c;
		px[i].c=c;
	}
	ll mn=inf;
	fo(i,1,n)
	{
		mn=min(mn,px[i].y);
	}
	fo(i,1,n)
	{
		ll x=px[i].x;
		ll tl=2*x-(px[i].y-mn),tr=2*x+(px[i].y-mn);
		px[i].x=tl;
		px[i].y=tr;
	}
	sort(px+1,px+1+n,cmp);
//	fo(i,1,n)
//	{
//		cout<<"WK "<<px[i].x<<" "<<px[i].y<<" "<<px[i].c<<'\n';
//	}
	multiset<ll> s;
	fo(i,1,n)
	{
		if(px[i].c=='N') s.insert(px[i].x);
		else if(px[i].c=='P')
		{
			if(s.lower_bound(px[i].x)!=s.end())
			{
				cout<<"impossible";
				return;
			}
		}
	}
	ll zmx=-inf;
	fo(i,1,n)
	{
		if(px[i].c=='-')
		{
			if(zmx<px[i].x&&ss.lower_bound({px[i].x,-1})!=ss.end()) ss.insert({px[i].x,i});
		}
		else if(px[i].c=='P')
		{
			ss.insert({px[i].x,i});
		}
		else
		{
			zmx=max(zmx,px[i].x);
		}
	}
	ll cnt=0;
	while(!ss.empty())
	{
		cnt++;
		pii zp=*ss.begin();
		ss.erase(ss.begin());
//		cout<<"WK "<<zp.se<<'\n';
		pp[cnt]=px[zp.se];
	}
	sort(pp+1,pp+1+cnt,tmp);
	ll num=0,mx=-inf,nw=-inf;
	mx=-inf;
	fo(i,1,cnt)
	{
//		cout<<"T "<<pp[i].x<<" "<<pp[i].y<<" "<<pp[i].c<<'\n';
		mx=max(mx,pp[i].y);
		if(pp[i].y>nw)
		{
			if(pp[i].c=='P')
			{
				nw=mx;
				num++;
				mx=-inf;
			}
		}
	}
	cout<<num;
}
bool M2;
int main()
{
	int Time=clock();
	look_memory;
//	_=gi();
	while(_--)
	{
		sol();
		printf("\n");
	}
	look_time;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5928kb

input:

4
1 -1 P
2 2 P
-1 3 N
-2 -1 -

output:

1

result:

ok "1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 5964kb

input:

2
0 0 N
1 2 P

output:

impossible

result:

ok "impossible"

Test #3:

score: 0
Accepted
time: 0ms
memory: 6048kb

input:

1
-30472937 -21950328 P

output:

1

result:

ok "1"

Test #4:

score: 0
Accepted
time: 1ms
memory: 6068kb

input:

1
75022528 -38109895 N

output:

0

result:

ok "0"

Test #5:

score: 0
Accepted
time: 0ms
memory: 5856kb

input:

1
-39558286 72055628 -

output:

0

result:

ok "0"

Test #6:

score: 0
Accepted
time: 1ms
memory: 5956kb

input:

3
1 0 P
2 0 P
0 0 P

output:

3

result:

ok "3"

Test #7:

score: 0
Accepted
time: 1ms
memory: 6020kb

input:

3
2 0 P
0 0 P
1 2 -

output:

1

result:

ok "1"

Test #8:

score: 0
Accepted
time: 1ms
memory: 6068kb

input:

15
2 0 P
1 0 P
2 6 -
3 -4 P
2 -3 P
0 3 N
7 -1 P
8 -2 P
7 0 -
3 1 N
0 2 -
2 1 P
-2 -2 P
1 -2 -
6 -3 P

output:

3

result:

ok "3"

Test #9:

score: 0
Accepted
time: 1ms
memory: 6076kb

input:

10
0 0 P
14 7 P
18 9 P
16 8 P
6 3 P
2 1 P
12 6 P
10 5 P
8 4 P
4 2 P

output:

10

result:

ok "10"

Test #10:

score: 0
Accepted
time: 1ms
memory: 6012kb

input:

10
7 14 P
0 0 P
8 16 P
3 6 P
9 18 P
4 8 P
2 4 P
1 2 P
5 10 P
6 12 P

output:

1

result:

ok "1"

Test #11:

score: 0
Accepted
time: 0ms
memory: 6048kb

input:

20
0 0 P
6 0 P
5 1 N
1 0 P
8 1 N
3 1 N
2 1 N
0 1 N
7 0 P
1 1 N
4 0 P
6 1 N
8 0 P
2 0 P
3 0 P
9 0 P
5 0 P
7 1 N
9 1 N
4 1 N

output:

10

result:

ok "10"

Test #12:

score: 0
Accepted
time: 1ms
memory: 6176kb

input:

20
4 1 P
8 0 N
4 0 N
3 1 P
9 0 N
3 0 N
5 0 N
0 0 N
2 1 P
9 1 P
5 1 P
0 1 P
6 1 P
1 0 N
2 0 N
1 1 P
6 0 N
8 1 P
7 0 N
7 1 P

output:

impossible

result:

ok "impossible"

Test #13:

score: 0
Accepted
time: 1ms
memory: 5924kb

input:

20
6 0 P
7 0 P
0 0 P
0 2 -
1 0 P
4 0 P
9 0 P
2 0 P
5 2 -
1 2 -
3 0 P
7 2 -
6 2 -
2 2 -
9 2 -
8 2 -
3 2 -
5 0 P
8 0 P
4 2 -

output:

4

result:

ok "4"

Test #14:

score: 0
Accepted
time: 0ms
memory: 5964kb

input:

20
-90394002 -98465629 N
55927325 88386657 -
59749238 49291180 -
95338756 52978092 N
-16627530 -67380746 N
-89625569 -3537413 -
60325466 87638514 P
50259513 43013499 -
-44373165 -20393833 P
-7910787 73165555 P
26135275 40128270 N
27298084 -40124679 -
-51104205 -20724280 P
41354267 -99201527 P
-81439...

output:

impossible

result:

ok "impossible"

Test #15:

score: 0
Accepted
time: 0ms
memory: 5960kb

input:

20
-21904192 -91041047 -
20663014 29046161 -
-65276283 -86800104 -
23660597 -76711343 P
-65566770 -73247584 -
-55268030 46405465 P
75379696 -17756864 P
-75925632 28560138 -
-17333950 -18569224 -
-60172950 -85880845 P
71987735 -5827653 -
31775344 18613538 -
-81110939 -7397078 -
-1065959 -58054771 P
-...

output:

5

result:

ok "5"

Test #16:

score: 0
Accepted
time: 1ms
memory: 5960kb

input:

20
-19221377 -99014313 N
-75590500 -10437461 -
42863056 -30468815 -
-86018485 -91837989 N
658922 11708028 N
-10892188 -39235779 N
-58373411 23768486 -
-59506542 -59869911 -
-56905562 67002361 -
-48804407 -92200165 N
-47948809 816486 -
-17198398 8919975 -
29935528 9839297 -
-89051384 -70629376 N
-300...

output:

0

result:

ok "0"

Test #17:

score: 0
Accepted
time: 0ms
memory: 6176kb

input:

20
53361278 60315709 -
-36804474 68454300 P
74575185 7191752 -
53518084 -31112136 -
25300728 47306879 P
79096341 -61948345 P
24004208 -52177483 -
-30958983 -4322655 P
55172503 -23354358 -
75274555 29587402 P
-66349605 -2530802 P
-34590957 42456416 P
-30901923 30295158 -
46771132 -13872648 P
40826247...

output:

5

result:

ok "5"

Test #18:

score: 0
Accepted
time: 0ms
memory: 5992kb

input:

20
15149712 88056744 N
94026616 10829548 -
-101 -102 N
52282849 55097803 -
75723597 8179397 N
93715162 24859963 N
57908671 75366349 -
21354670 2104133 N
7457993 31061381 -
1514714 27359087 N
8981158 74432596 -
68889077 20807829 N
7252197 46798325 N
40251457 71258448 N
19568607 71455063 -
69634911 69...

output:

impossible

result:

ok "impossible"

Test #19:

score: 0
Accepted
time: 0ms
memory: 5916kb

input:

20
30000000 0 P
25000000 0 P
83826218 10247401 -
20000000 0 P
35000000 0 P
5000000 0 P
45000000 0 P
95629846 16440329 -
94540952 19310845 -
48794061 4190826 -
21566278 1578241 -
18363878 23819895 -
34144264 5018447 -
10000000 0 P
31319054 16044026 -
13852189 16543544 -
0 0 P
80365590 3501056 -
40000...

output:

6

result:

ok "6"

Test #20:

score: 0
Accepted
time: 0ms
memory: 6036kb

input:

20
45000000 0 P
30000000 0 P
15000000 0 P
48627265 11021121 -
84552129 14338512 N
45658763 14396058 -
20000000 0 P
0 0 P
25890176 3588342 N
10000000 0 P
66011041 13765775 N
38592522 2697312 N
40000000 0 P
20693678 20785134 -
35000000 0 P
80436233 14503874 N
5000000 0 P
2736411 13358226 -
25000000 0 ...

output:

8

result:

ok "8"

Test #21:

score: 0
Accepted
time: 1ms
memory: 5960kb

input:

20
430 88392846 P
61 90836890 -
411 35435431 P
740 -69485320 P
45 33896902 -
450 -44694050 -
772 52349400 -
39 -90051154 P
577 13530559 P
793 -6146243 P
227 77785022 P
58 4895119 -
457 40847401 -
868 65318757 P
757 23200802 -
654 -52439664 P
886 21692195 P
920 13974242 P
83 43532035 P
504 31428919 -

output:

1

result:

ok "1"

Test #22:

score: 0
Accepted
time: 1ms
memory: 6016kb

input:

20
-82661636 737 P
4068998 539 P
96500510 28 -
-61694861 458 P
-81771214 478 P
-47897681 682 -
35250357 739 -
-34059938 796 -
-99476665 618 P
-71321252 782 -
-23042721 462 P
-62455904 859 P
55539244 535 P
7265333 633 -
81807004 823 -
22792252 240 P
-48458023 576 P
37546040 831 P
-20859296 172 -
6774...

output:

11

result:

ok "11"

Test #23:

score: 0
Accepted
time: 81ms
memory: 24252kb

input:

200000
64637 0 P
99848 0 P
4840 1 N
4775 0 P
35545 1 N
69168 1 N
4755 0 P
68755 1 N
19253 0 P
14315 1 N
53683 0 P
41554 0 P
79752 1 N
46055 0 P
78170 1 N
57017 0 P
48069 0 P
32558 1 N
11208 1 N
9572 1 N
98686 1 N
18368 1 N
46419 1 N
34300 0 P
64265 0 P
59636 1 N
46656 0 P
23763 1 N
28049 0 P
3381 0 ...

output:

100000

result:

ok "100000"

Test #24:

score: 0
Accepted
time: 30ms
memory: 8856kb

input:

200000
44817 1 P
56264 1 P
98055 1 P
11770 1 P
74556 0 N
91279 0 N
68455 0 N
67772 1 P
84349 1 P
48263 1 P
69835 0 N
43650 0 N
94120 1 P
75518 1 P
91052 0 N
135 0 N
82130 1 P
98598 1 P
2693 0 N
68109 1 P
31704 0 N
16137 1 P
56905 0 N
35686 0 N
65005 1 P
14189 1 P
1152 0 N
41000 1 P
74537 1 P
65960 0...

output:

impossible

result:

ok "impossible"

Test #25:

score: 0
Accepted
time: 85ms
memory: 25736kb

input:

200000
98388 2 -
92932 2 -
88289 2 -
51223 2 -
16359 0 P
36429 2 -
6179 0 P
93858 2 -
62603 0 P
45012 0 P
77927 2 -
12082 2 -
19480 2 -
13001 2 -
3032 2 -
727 0 P
85753 2 -
50527 0 P
54041 2 -
80117 2 -
28614 2 -
27226 0 P
86511 0 P
39339 0 P
63253 0 P
18144 2 -
4351 0 P
70008 2 -
33184 2 -
29287 0 ...

output:

33334

result:

ok "33334"

Test #26:

score: 0
Accepted
time: 39ms
memory: 10552kb

input:

200000
26408107 938095 P
48283070 67622971 N
34124389 -89206245 N
-95003527 -5108823 P
-69353691 -43927010 P
37472266 15060526 P
-76408163 67377261 N
-93391566 -86741273 P
-31688140 -61605899 P
78256216 -68074104 -
-39737262 5165375 N
-26478007 17225603 P
-12134620 -38922000 -
65203074 33124417 N
94...

output:

impossible

result:

ok "impossible"

Test #27:

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

input:

200000
-21825942 -69338709 P
21125972 69431856 P
14811655 79218329 P
81563093 58473396 -
26805138 -56241479 P
82834360 64891730 P
32541913 -91187141 -
17547264 -99454318 -
-10506009 7530812 -
-22337691 -21720746 -
-33412089 42342018 -
96367457 -26640346 -
-28677092 98305727 P
-88748970 82240749 P
-8...

output:

371

result:

ok "371"

Test #28:

score: 0
Accepted
time: 63ms
memory: 15132kb

input:

200000
2949725 69387231 N
-60832153 4788081 -
-29551383 11404938 N
-16645218 63807982 N
29908820 20410546 -
19676139 94707123 N
-74097994 -39917078 -
-31242656 -94969781 N
-14933034 36638841 N
-89396574 92283740 N
-85107891 -35375599 -
89246205 -59214500 N
79589674 -91729992 N
-58440925 77066327 N
-...

output:

0

result:

ok "0"

Test #29:

score: 0
Accepted
time: 139ms
memory: 25684kb

input:

200000
-55306223 9870600 P
-25901253 55547440 -
41143987 -23935368 -
-47745882 -37646392 P
51510652 3196152 P
-63752184 -92444075 -
-10529756 -24499860 P
44417679 93854393 -
-90335076 6273209 -
93690480 -95685096 -
-21052892 33546507 P
-34916835 -34369468 -
-1381728 -40009550 P
-55359737 -54504772 P...

output:

352

result:

ok "352"

Test #30:

score: 0
Accepted
time: 32ms
memory: 8508kb

input:

200000
26615803 8225879 N
81728441 3451527 N
53211045 48820579 N
18931322 94692358 N
12957789 68331279 -
90764254 71498777 N
91994969 44160103 -
42790955 29095320 N
21333513 16703863 N
30654875 79427979 N
96446597 88518809 -
41343973 31111078 N
19430200 74600310 -
58591201 87650086 -
21819083 941683...

output:

impossible

result:

ok "impossible"

Test #31:

score: 0
Accepted
time: 68ms
memory: 22384kb

input:

200000
30889000 0 P
27388984 167 -
47745000 0 P
86539757 743 -
48701002 345 -
10897000 0 P
78050623 1828 -
91640189 1385 -
32613500 0 P
48855353 1113 -
35313500 0 P
20873500 0 P
16558486 1312 -
36364257 1692 -
25298590 2250 -
14709530 1163 -
27694500 0 P
15254977 727 -
26030759 1866 -
20017570 1478 ...

output:

53642

result:

ok "53642"

Test #32:

score: 0
Accepted
time: 60ms
memory: 23004kb

input:

200000
33561454 223 -
36476500 0 P
70963229 134 -
17353500 0 P
72016162 273 -
89213725 2446 -
18879445 1810 N
37343000 0 P
41472000 0 P
33414500 0 P
26251500 0 P
10707236 735 N
43240928 397 -
28439777 1795 N
22457500 0 P
97230239 2213 N
40485000 0 P
51158443 118 -
84884174 640 -
45485000 0 P
36259 1...

output:

78108

result:

ok "78108"

Test #33:

score: 0
Accepted
time: 75ms
memory: 25664kb

input:

200000
703 75782528 P
711 66597383 P
630 -37161138 -
747 -50454609 P
918 68564847 P
335 -88660426 -
460 -512112 -
649 26620087 P
129 -8361395 -
169 27803523 -
941 -91899445 -
677 16770315 P
546 -29335090 -
757 -78039284 P
629 -45424289 -
994 6412015 -
328 19136216 P
674 65988251 P
698 51179275 P
623...

output:

2

result:

ok "2"

Test #34:

score: 0
Accepted
time: 68ms
memory: 20084kb

input:

200000
26575215 387 P
-34052981 966 P
38187532 232 P
99129056 578 P
-20516888 594 -
78928596 432 -
-66505173 113 P
72878480 759 -
-99710587 973 -
-36899156 365 -
52061910 206 -
-15588293 30 -
-32721882 185 -
55885599 968 P
-7708620 69 -
-88292674 508 -
90900171 889 P
-35843655 221 -
-97810276 225 P
...

output:

92034

result:

ok "92034"

Test #35:

score: 0
Accepted
time: 82ms
memory: 21524kb

input:

134473
-46967008 15868908 P
-67588974 -88369190 P
-25938929 -36915660 P
-92338728 -18884590 P
67780836 19480175 P
-89133733 -20130351 P
-30380490 -88635040 P
63654157 -45478697 P
-97419444 21962981 P
-88088882 31656306 P
50993127 -49312361 P
55035183 66993098 P
18236959 -18851993 P
52888712 26116231...

output:

451

result:

ok "451"

Test #36:

score: 0
Accepted
time: 29ms
memory: 13532kb

input:

63895
4607517 -39060977 -
46605143 70136866 -
-37100275 -44219003 P
-86495052 -46431199 P
85425972 -95108057 P
35906699 18137132 -
-65087743 8780618 -
-64743752 -42195238 -
-28987566 20731542 -
54810852 -73615224 -
-14271172 -24107110 -
72052508 85978863 P
71509562 61823445 P
-4695632 -90317748 P
61...

output:

193

result:

ok "193"

Test #37:

score: 0
Accepted
time: 6ms
memory: 10092kb

input:

26053
54890016 -40999773 P
96948811 -48298062 P
-16482427 -90910503 P
90334219 75279597 P
61854010 -22371021 P
41463335 -12527114 P
91317839 31264607 P
-74348757 -52769650 P
-68666889 69018343 P
11430208 76916846 P
-25451499 -29353541 P
58536675 -52719097 P
-19166593 46904592 P
-65580145 -90360355 P...

output:

202

result:

ok "202"

Test #38:

score: 0
Accepted
time: 0ms
memory: 6544kb

input:

6928
-85429009 7617702 -
-36169284 -61548629 P
-70073931 63729872 -
-67978863 67433854 P
-94281620 -95989210 -
94865561 85106952 -
-69912740 -9869711 P
85942589 -6597015 -
-50072691 54708780 -
10171305 50704302 P
-19281187 -28579929 -
5927243 27881817 -
70677909 -83116065 -
-36288497 -6547383 P
-446...

output:

65

result:

ok "65"

Test #39:

score: 0
Accepted
time: 10ms
memory: 7748kb

input:

18552
24067577 -17099781 P
19538026 -77132075 -
-73799699 -63335103 P
-17067899 -10686014 -
-12454316 26326863 -
-43417532 -75040696 P
6844188 29712748 -
-42072435 -66506151 -
49755519 78169459 -
-53294184 -7472076 P
-95815286 72882454 P
41126065 -87714016 P
48190062 -99456072 P
-32993808 -93860575 ...

output:

122

result:

ok "122"

Test #40:

score: 0
Accepted
time: 41ms
memory: 16984kb

input:

89853
27661149 19904698 P
-98694679 -29791252 -
-23099871 -81060586 P
-24735185 49384021 -
76884279 -36741920 P
-22316403 -59151114 -
22071884 -42283709 -
79367278 23895428 P
-1679625 -68719395 P
-72132934 73194731 P
47742710 46984871 -
46226579 84253160 -
-66659881 45672980 -
-83204271 -23586794 P
...

output:

227

result:

ok "227"

Test #41:

score: 0
Accepted
time: 39ms
memory: 10144kb

input:

180751
22937140 35171617 N
91634056 8238124 P
-98639700 41409618 P
68328492 -85020144 P
-90538049 -47313935 N
-12240196 75381961 P
-95372446 61596637 N
67904074 32788201 N
-28077807 96357889 P
67158740 19836510 N
85848526 -6045090 N
-13170801 57693916 N
-41346786 -66498432 P
84792888 42750463 N
2044...

output:

impossible

result:

ok "impossible"

Test #42:

score: 0
Accepted
time: 17ms
memory: 8636kb

input:

31757
-17734133 -12332652 -
14877531 63845738 -
27954539 33325061 P
-53257111 -73862551 P
28035568 12428900 -
98632405 -25168396 -
85740744 -98515510 -
-2569013 97994183 -
19580164 10488535 P
86838234 -82694610 -
95191800 39709795 -
5841224 4879630 P
4632897 28802089 P
95570187 -48881288 -
75550969 ...

output:

155

result:

ok "155"

Test #43:

score: 0
Accepted
time: 18ms
memory: 9424kb

input:

60442
49383765 -58050546 -
-53545758 76571869 -
-30836576 -83891785 -
-44367231 65591117 -
-43902932 -88477513 N
-28996302 -76660031 N
-29408196 76042567 -
48761603 -32133019 -
28933678 85969029 N
-32234573 44367545 -
83028306 -67874859 -
23571253 -39493997 -
-17871644 -96402290 -
84952125 -55573227...

output:

0

result:

ok "0"

Test #44:

score: 0
Accepted
time: 34ms
memory: 10572kb

input:

114001
15879325 3920034 -
52531251 -11382843 -
58770320 58690512 -
-68795256 35043822 -
68772951 86561355 N
15154131 78754712 N
-5925052 -83903652 -
-88199674 -90404195 -
-52510280 37331093 N
5272235 43933597 -
95148681 -66203820 N
94145375 87192359 -
-40356471 -4511142 N
48693302 -33667266 -
233807...

output:

0

result:

ok "0"