QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#748104 | #879. Exhaustive Experiment | starback24 | AC ✓ | 130ms | 11968kb | C++14 | 2.3kb | 2024-11-14 19:20:48 | 2024-11-14 19:20:50 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define endl '\n'
#define fir first
#define sec second
#define file(__a) freopen(__a".in","r",stdin),freopen(__a".out","w",stdout);
#define look_time cerr<<(clock()-Time)/1000.0<<"s"<<endl
#define look_memory cerr<<(&b2-&b1)/1024.0/1024.0<<"MB"<<endl
using namespace std;
bool b1;
time_t Time = clock();
int T = 1;
template<typename T>
inline void read(T &s) {
T f = 1, c = 0;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') {
f = -1;
}
ch = getchar();
}
while (isdigit(ch)) {
c = (c << 1) + (c << 3) + (ch ^ 48);
ch = getchar();
}
s = f * c;
}
template<typename T, typename ...Args>
inline void read(T &s, Args &...args) {
read(s), read(args...);
}
namespace white_carton {
int n, x, y;
struct node {
int x, y;
char ch;
int id;
} a[1001000];
bool cmp(node a, node b) {
return a.x < b.x;
}
void Solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x >> y;
cin >> a[i].ch;
x = x * 2;
a[i].x = x + y + 3e8 + 1;
a[i].y = y - x + 3e8 + 1;
a[i].id = i;
}
sort(a + 1, a + 1 + n, cmp);
int minn = INF;
for (int i = 1; i <= n; i++) {
int l = i, r = i;
while (a[r].x == a[r + 1].x) {
r++;
}
for (int j = l; j <= r; j++) {
if (a[j].ch == 'N') {
minn = min(minn, a[j].y);
}
}
for (int j = l; j <= r; j++) {
if (a[j].ch == 'P' && a[j].y >= minn) {
cout << "impossible" << endl;
return;
}
if (a[j].ch == '-' && a[j].y >= minn) {
a[j].ch = 'N';
}
}
i = r;
}
int MAXN = -INF, MAXN_ = -INF;
int ans = 0;
for (int i = n; i >= 1; i--) {
int l = i, r = i;
while (l > 1 && a[l].x == a[l - 1].x) {
l--;
}
for (int i = l; i <= r; i++) {
if (a[i].ch == 'N') {
continue;
}
MAXN_ = max(MAXN_, a[i].y);
}
// cout << MAXN_ << endl;
for (int i = l; i <= r; i++) {
if (a[i].ch == 'N') {
continue;
}
if (a[i].y > MAXN && a[i].ch == 'P') {
ans++;
MAXN = MAXN_;
}
}
i = l;
}
cout << ans << endl;
}
}
bool b2;
signed main() {
// file("dis");
// cin>>T;
while (T--)white_carton::Solve();
look_time;
look_memory;
}
//日拱一卒,功不唐捐
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3932kb
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: 3924kb
input:
2 0 0 N 1 2 P
output:
impossible
result:
ok "impossible"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
1 -30472937 -21950328 P
output:
1
result:
ok "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
1 75022528 -38109895 N
output:
0
result:
ok "0"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
1 -39558286 72055628 -
output:
0
result:
ok "0"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3972kb
input:
3 1 0 P 2 0 P 0 0 P
output:
3
result:
ok "3"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
3 2 0 P 0 0 P 1 2 -
output:
1
result:
ok "1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3892kb
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: 0ms
memory: 3920kb
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: 0ms
memory: 3880kb
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: 3936kb
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: 0ms
memory: 3952kb
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: 0ms
memory: 3872kb
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: 3936kb
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: 3824kb
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: 0ms
memory: 3876kb
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: 3932kb
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: 3928kb
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: 3880kb
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: 3872kb
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: 0ms
memory: 3932kb
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: 0ms
memory: 3924kb
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: 80ms
memory: 10424kb
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: 80ms
memory: 10984kb
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: 81ms
memory: 10452kb
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: 120ms
memory: 11804kb
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: 114ms
memory: 10764kb
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: 130ms
memory: 11764kb
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: 130ms
memory: 11580kb
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: 122ms
memory: 11968kb
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: 101ms
memory: 10768kb
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: 97ms
memory: 10924kb
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: 106ms
memory: 11336kb
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: 107ms
memory: 11836kb
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: 87ms
memory: 8904kb
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: 42ms
memory: 7904kb
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: 17ms
memory: 6576kb
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: 2ms
memory: 4104kb
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: 12ms
memory: 4500kb
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: 58ms
memory: 8708kb
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: 117ms
memory: 10752kb
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: 21ms
memory: 6420kb
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: 35ms
memory: 6136kb
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: 70ms
memory: 9056kb
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"