QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#197182 | #7437. 博丽灵梦 | zhouhuanyi | 20 | 7032ms | 12076kb | C++23 | 2.2kb | 2023-10-02 13:00:51 | 2023-10-02 13:00:52 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 100000
#define M 1000000
using namespace std;
long long read()
{
char c=0;
long long sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int n,m,sz,l1,r1,l2,r2,block[N+1],p[N+1],q[N+1],C[N+1],Cs[N+1],cnt[N+1];
unsigned int W[N+1],Wt[N+1],Ws[N+1],res,ans[M+1];
struct reads
{
int x1,y1,x2,y2,num;
bool operator < (const reads &t)const
{
if (block[x1]!=block[t.x1]) return block[x1]<block[t.x1];
else if (block[y1]!=block[t.y1]) return block[y1]<block[t.y1];
else if (block[x2]!=block[t.x2]) return block[x2]<block[t.x2];
else return y2<t.y2;
}
};
reads st[M+1];
int main()
{
n=read(),sz=max(n/max((int)(pow(m,1.0/4)),1),1);
for (int i=1;i<=n;++i) block[i]=(i-1)/sz+1;
for (int i=1;i<=n;++i) p[i]=read(),q[p[i]]=i;
for (int i=1;i<=n;++i) C[i]=read();
for (int i=1;i<=n;++i) W[i]=read();
for (int i=1;i<=n;++i) Cs[i]=C[q[i]],Wt[i]=W[C[i]],Ws[i]=W[Cs[i]];
m=read();
for (int i=1;i<=m;++i) st[i].x1=read(),st[i].x2=read(),st[i].y1=read(),st[i].y2=read(),st[i].num=i;
sort(st+1,st+m+1),l1=l2=1,r1=r2=0;
for (int i=1;i<=m;++i)
{
while (l1>st[i].x1)
{
--l1;
if (l2<=p[l1]&&p[l1]<=r2) cnt[C[l1]]++,res+=(cnt[C[l1]]==1)?Wt[l1]:0;
}
while (r1<st[i].x2)
{
++r1;
if (l2<=p[r1]&&p[r1]<=r2) cnt[C[r1]]++,res+=(cnt[C[r1]]==1)?Wt[r1]:0;
}
while (l1<st[i].x1)
{
if (l2<=p[l1]&&p[l1]<=r2) cnt[C[l1]]--,res-=(!cnt[C[l1]])?Wt[l1]:0;
++l1;
}
while (r1>st[i].x2)
{
if (l2<=p[r1]&&p[r1]<=r2) cnt[C[r1]]--,res-=(!cnt[C[r1]])?Wt[r1]:0;
--r1;
}
while (l2>st[i].y1)
{
--l2;
if (l1<=q[l2]&&q[l2]<=r1) cnt[Cs[l2]]++,res+=(cnt[Cs[l2]]==1)?Ws[l2]:0;
}
while (r2<st[i].y2)
{
++r2;
if (l1<=q[r2]&&q[r2]<=r1) cnt[Cs[r2]]++,res+=(cnt[Cs[r2]]==1)?Ws[r2]:0;
}
while (l2<st[i].y1)
{
if (l1<=q[l2]&&q[l2]<=r1) cnt[Cs[l2]]--,res-=(!cnt[Cs[l2]])?Ws[l2]:0;
++l2;
}
while (r2>st[i].y2)
{
if (l1<=q[r2]&&q[r2]<=r1) cnt[Cs[r2]]--,res-=(!cnt[Cs[r2]])?Ws[r2]:0;
--r2;
}
ans[st[i].num]=res;
}
for (int i=1;i<=m;++i) printf("%u\n",ans[i]);
return 0;
}
详细
Test #1:
score: 4
Accepted
time: 0ms
memory: 9764kb
input:
10 7 6 3 5 9 1 10 8 4 2 1 9 7 4 1 4 1 1 9 7 9 2 4 9 1 8 5 5 6 7 10 2 7 6 8 2 5 4 10 6 9 8 9 6 9 7 9 4 5 6 7 4 9 8 8 2 9 3 5 3 7 4 8 4 6 1 10 6 7 8 9
output:
6 24 9 9 0 9 20 9 18 0
result:
ok 10 numbers
Test #2:
score: 4
Accepted
time: 100ms
memory: 10040kb
input:
5000 4584 3973 1352 4671 419 4060 2422 1887 1113 4149 3583 511 2168 3996 963 870 1871 1972 2974 3771 2725 2276 4578 194 4600 114 4297 1714 3530 3353 2904 4842 366 744 116 1785 3646 2473 1421 4245 1366 4483 1555 4595 1179 1394 3648 3066 4024 1935 2263 4237 4268 29 2148 4647 4515 2135 4131 4589 3314 2...
output:
327117 136689 1479698 1136737 449729 1711409 450967 763623 858017 807158 284267 1975776 1648557 1531841 417402 1109352 779487 3606 5497 491686 1800425 252458 96255 3426670 106777 1457932 21547 717391 1449681 334971 2332339 1508267 169612 3687559 347639 28409 388782 363513 244140 1945694 116465 67408...
result:
ok 5000 numbers
Test #3:
score: 4
Accepted
time: 2495ms
memory: 12076kb
input:
25000 17933 12647 4126 561 20565 17721 3237 20956 23810 15182 1371 1964 19155 23873 16313 20143 23077 15413 14837 23101 15220 2217 22784 2221 17865 11528 9072 23426 15666 9562 23566 7278 11913 6636 10360 8741 13378 13274 515 17382 15017 11838 24731 10977 643 23193 24811 18852 20273 17879 16016 2687 ...
output:
44331710 96283081 87530730 38741823 58043413 55254246 67615705 37985774 22050584 103215771 59813290 96181328 30218492 87030588 64939548 95314170 26427029 89913865 13923644 53206182 85913027 77294146 12276632 82340332 33993445 88588245 72575496 73838518 52753249 34970184 88425783 51570715 90607205 10...
result:
ok 50000 numbers
Test #4:
score: 0
Time Limit Exceeded
input:
50000 34190 30883 11333 45339 39327 7782 31720 17826 49088 48395 26423 1963 15006 13296 31887 39411 41575 47505 26979 39758 29082 5053 35619 36746 28511 45672 37295 30506 46420 36833 48283 34088 32552 48561 22638 32469 22093 49328 21194 8280 24202 26909 49400 11332 12274 29937 15451 42485 48625 4052...
output:
result:
Test #5:
score: 0
Time Limit Exceeded
input:
75000 30149 54180 3798 34212 67897 28067 50060 44816 38037 27530 70405 68069 16326 14256 66092 36541 72536 72996 63812 65847 23781 72137 39834 29700 11212 11156 41911 9140 57560 21211 39159 53063 71051 45303 39914 9566 32134 69835 24071 7055 58777 70053 69284 73900 53302 28963 74142 46429 7921 57247...
output:
result:
Test #6:
score: 0
Time Limit Exceeded
input:
100000 47534 82358 90198 90311 86971 78138 57685 92820 95572 82397 45779 74859 67319 89881 76297 71344 68227 55217 75262 94126 96422 87581 94223 87931 88679 42475 75545 30649 91491 96694 85088 94656 24494 69871 78199 69331 99352 18668 74574 78408 79693 61591 99297 49169 83870 93128 88383 69981 66151...
output:
result:
Test #7:
score: 4
Accepted
time: 1512ms
memory: 8432kb
input:
20000 11616 14681 9191 15174 9118 13157 14663 13691 19020 4289 1661 17151 11530 10198 10148 7691 1626 8200 5742 16570 17497 342 19688 4812 9998 16500 8667 16256 16815 5543 2734 13845 2182 8140 17207 15824 4253 474 9157 8209 14695 6161 8064 19843 1130 13147 19730 10224 7634 12957 14900 7442 11608 138...
output:
2016662 6773498 16534227 7264977 8255967 20382699 8614253 36830556 6684778 1707073 21596412 32682670 6404798 13544211 3015074 32926912 2438256 13675665 23244560 116740 12652456 3120774 26092 35826021 5516953 580396 46007357 16163011 3231113 8955441 12216687 1402777 21395122 130204 10097522 31481510 ...
result:
ok 19260 numbers
Test #8:
score: 4
Accepted
time: 7032ms
memory: 10996kb
input:
30000 18100 17984 29616 26532 16351 25306 28940 17968 12149 21623 10913 25728 7504 1694 18649 20697 12374 28510 28482 24090 23186 26948 24342 8516 28375 24474 26716 10580 18582 25290 29675 5255 22335 21818 28936 918 11068 8231 14805 25816 29904 26304 12336 12440 28867 27898 20999 18451 17788 10485 2...
output:
57833084 14731524 7903237 111647773 4838310 59648591 10688753 50939852 5221720 113380726 24782301 22498185 61111304 39389586 37258737 9093606 25185482 84788372 6132515 28307612 54940963 56002962 72959218 2090556 131394639 13444906 3911685 36151408 11946266 42502314 9084655 3594198 7500469 6076377 48...
result:
ok 60000 numbers
Test #9:
score: 0
Time Limit Exceeded
input:
40000 6155 33310 18982 32436 23117 11936 23625 36826 24896 18185 2373 31232 5057 20465 18997 36213 39297 32273 32461 29674 18962 13728 30106 33069 4625 35639 28937 32955 36807 31210 12487 33040 26415 13758 38447 20070 16135 32305 34756 22396 24672 32400 28184 22671 5895 5628 7054 27520 28612 17575 2...
output:
result:
Test #10:
score: 0
Time Limit Exceeded
input:
50000 38469 24525 32217 24789 47311 24293 3571 14829 26717 913 21309 8308 37327 8734 17912 43870 48997 10733 2270 26728 7330 16464 40796 11288 47560 48672 46090 18389 25933 46137 41744 48976 38039 41118 38084 40612 47921 45345 45410 48851 31754 38299 27413 23608 24009 31513 40500 49878 8252 41404 10...
output:
result:
Test #11:
score: 0
Time Limit Exceeded
input:
60000 28929 27272 6259 45423 15780 40321 15580 4868 47291 3546 27936 45710 20567 26606 30216 52113 50838 55739 49818 56542 31288 49488 50806 8957 57695 52604 58066 14076 38002 58344 26180 36232 22180 32879 34138 51711 34760 25593 43389 31396 51616 13814 58547 40038 55058 48403 34408 25186 51758 5163...
output:
result:
Test #12:
score: 0
Time Limit Exceeded
input:
70000 52924 17320 66317 8157 30299 14111 65609 39835 21071 62191 51780 53198 44998 54574 66213 14371 58818 68483 39851 47765 42611 69393 63471 60519 9205 11577 69131 61430 13885 29809 66714 44006 62051 58921 12599 53974 40692 64816 36682 3519 24905 52640 10114 68493 49109 41844 48600 66776 38530 433...
output:
result:
Test #13:
score: 0
Time Limit Exceeded
input:
100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
result:
Test #14:
score: 0
Time Limit Exceeded
input:
100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
result:
Test #15:
score: 0
Time Limit Exceeded
input:
100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
result:
Test #16:
score: 0
Time Limit Exceeded
input:
95000 54869 89685 84021 77335 29643 94178 67158 60183 31735 63706 79776 89995 89643 62925 35391 76241 81318 59689 94539 42088 29258 71464 41104 76091 24922 72978 89700 92047 64960 12525 70519 82967 85527 88068 85048 89273 19561 66101 53150 88863 43065 94970 41214 71260 82429 52175 75847 14693 94497 ...
output:
result:
Test #17:
score: 0
Time Limit Exceeded
input:
100000 85963 54232 81192 62832 86584 80503 31766 74547 68821 73102 73096 72267 89495 33829 99520 43962 54837 89342 84555 71099 98465 64321 69793 39525 70934 87510 76927 85543 80068 25394 93361 4064 75959 51666 98914 15652 80946 90768 98387 88616 95082 44075 76628 84428 90891 63623 85280 43215 12888 ...
output:
result:
Test #18:
score: 0
Time Limit Exceeded
input:
100000 90787 49393 38459 68555 92570 80827 83843 39871 57205 59948 85227 96519 94578 78479 78947 89776 58887 21176 89863 99298 44414 29776 25867 88717 53798 75196 76719 87201 71049 86356 44186 47657 77140 74621 90681 81634 99004 97417 67801 73807 30440 47271 98457 50945 68642 92999 98340 99414 14611...
output:
result:
Test #19:
score: 0
Time Limit Exceeded
input:
100000 56193 78732 53570 44033 95995 99805 99585 94328 86681 87057 38285 74770 35856 6475 67612 52118 61883 18643 94607 31187 29338 88506 19752 84313 95851 96938 75747 72293 99364 67597 58337 99189 57651 74675 88241 44625 85781 27224 95532 74927 99055 98502 50279 27215 87270 20715 81841 89907 89718 ...
output:
result:
Test #20:
score: 0
Time Limit Exceeded
input:
100000 54722 84563 96554 77985 99277 67108 96381 71428 89162 91934 89671 74392 31632 30282 14966 88796 75550 96930 3617 82001 88145 28169 71044 85311 22416 30942 30195 99275 88970 30785 61892 84018 48484 19580 65559 90924 92214 43453 76013 9855 77640 76849 60741 31437 99618 3508 5054 87130 26889 946...
output:
result:
Test #21:
score: 0
Time Limit Exceeded
input:
100000 69536 76666 30096 75927 68899 60112 50144 27911 91674 77923 64608 95868 89728 87803 87234 62536 90788 95452 75434 48468 83595 97682 61133 69084 86299 99064 81737 90986 94384 95563 96802 37554 83608 94954 80895 23078 92537 56143 80659 14842 93617 92962 91436 39232 97232 67436 98527 67131 73774...
output:
result:
Test #22:
score: 0
Time Limit Exceeded
input:
100000 25377 81949 73151 50640 84530 48045 12139 82295 59977 92190 83405 82243 94236 93605 83319 98058 89610 91310 38547 86841 81877 90240 70172 35462 69666 93781 81392 54806 87407 99453 99244 58440 95573 88739 5938 84504 56614 23803 77556 47383 87088 73684 82110 83163 35349 92668 73141 20736 70294 ...
output:
result:
Test #23:
score: 0
Time Limit Exceeded
input:
100000 68911 78955 67125 63739 77253 93872 98284 30234 65137 93114 55561 50049 18255 97663 75460 27811 96088 82376 74231 62398 67493 59605 51358 41605 88345 83081 83446 37670 52929 59276 32521 95748 30602 11042 62878 97612 83929 41373 30569 82057 79198 90481 19440 97993 30901 96818 84076 87404 9354 ...
output:
result:
Test #24:
score: 0
Time Limit Exceeded
input:
100000 38458 39973 76990 86656 70315 70763 69153 94522 73043 96732 91705 43575 10537 63472 87305 65815 77792 96549 40795 68033 60805 57972 92038 84405 83637 18269 75531 94024 85636 83976 61301 74283 59778 5838 70252 73510 86230 62884 52089 84610 88915 78999 96146 35458 90912 98152 93863 35686 99939 ...
output:
result:
Test #25:
score: 0
Time Limit Exceeded
input:
100000 17357 75572 76084 97973 70590 40014 38940 43780 66344 53972 29698 53880 32667 26551 87331 3607 91253 63177 86190 42335 94989 38370 32515 59279 35119 38533 93007 8473 46782 85420 98270 27516 83838 66639 57364 91913 46439 83749 30263 97990 18522 97105 87000 80718 98885 29744 95730 93844 98301 2...