QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#735198 | #9613. 计算几何 | modwwe | 0 | 0ms | 0kb | C++23 | 2.9kb | 2024-11-11 18:09:44 | 2024-11-11 18:09:45 |
answer
//Judges with GCC >= 12 only needs Ofast
#pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
#pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#include<bits/stdc++.h>
#define int long long
//#include "sqsort.h"
#define down cout<<'\n';
#define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
void phongbeo();
const int mod2= 998244353;
const int mod=1e9+7;
struct ib
{
int a;
int b;
};
struct icd
{
int a,b;
};
struct ic
{
int a,b,c;
};
struct id
{
int a,b,c,d;
};
int n,m,s2,s4,s3,sf,k,r,dem=0,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,l;
int i,s10,s12;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
//fin(task),fou(task);
#endif
NHP
//modwwe
phongbeo(),down
//checktime
}
ib a[1000001];
int bit[3000002],bit2[3000002],bit3[3000002],bit4[3000002];
void add2(int x,int y)
{
for(x;x>=1000001;x-=x&-x)
bit2[x]+=y,bit[x]++;
}
void add3(int x,int y)
{
for(x;x;x-=x&-x)
bit3[x]+=y,bit4[x]++;
}
int get1(int x,int y)
{
int ss=0,ss2=0,ss4=y;
for(x;x<=s2;x+=x&-x)
{
ss2+=bit[x];
ss+=bit2[x];
}
return ss4*ss2-ss;
}
int get2(int x,int y)
{
int ss=0,ss2=0,ss4=y;
for(x;x<=s2;x+=x&-x)
{
ss2+=bit4[x];
ss+=bit3[x];
}
return ss4*ss2-ss;
}
bool cmp(ib a,ib b)
{
return a.a<b.a;
}
void phongbeo()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i].a,a[i].a+=1000001;
for(int i=1;i<=n;i++)
cin>>a[i].b,s2=max(s2,a[i].a+a[i].b);
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
{ s4=a[i].a-a[i].b;
s5=a[i].a+a[i].b;
s3+=get1(s5,a[i].a);
s3+=get2(s4,a[i].a);
add2(s5,a[i].a);
add3(s4,a[i].a);
}
for(int i=1;i<=n;i++)
{
a[i].a-=1000001;
swap(a[i].a,a[i].b);
a[i].a+=1000001;
}
sort(a+1,a+1+n,cmp);
memset(bit,0,sizeof bit);
memset(bit2,0,sizeof bit);
memset(bit3,0,sizeof bit);
memset(bit4,0,sizeof bit);
for(int i=1;i<=n;i++)
{ s4=a[i].a-a[i].b;
s5=a[i].a+a[i].b;
s3+=get1(s5+1,a[i].a);
s3+=get2(s4+1,a[i].a);
add2(s5,a[i].a);
add3(s4,a[i].a);
}
cout<<s3*2;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 0
Runtime Error
input:
2000 2000 983850330 731103020 513263912 234227610 788795134 228585831 -983909940 -814082030 -582261039 729875680 617950974 -259602422 -355311469 355769341 -394119311 -493842356 899026446 -402238603 -300533665 433674923 946553927 26786776 46270288 43713228 -838909861 427788951 863776211 691106038 -93...
output:
result:
Test #2:
score: 0
Runtime Error
input:
2000 2000 407439483 0 -924180082 0 534637753 0 -836707453 0 -385278990 0 90204634 0 454360393 0 -895242427 0 -112231538 0 -323497705 0 368203671 0 -124641980 0 183953551 0 596609116 0 666423112 0 706701157 0 988299741 0 -248457324 0 -507127215 0 610030981 0 356918300 0 110156240 0 317203493 0 754544...
output:
result:
Test #3:
score: 0
Runtime Error
input:
20000 20000 -721847248 671834627 -750033826 -893098471 358123311 740735694 -15749050 352553172 331628828 285387115 -870680297 30680547 747479743 495644671 -24785538 458380663 -49052185 540025540 192115219 694762799 -582891748 -643029079 -356894103 726491498 213744952 457769371 -357728988 745592631 -...
output:
result:
Test #4:
score: 0
Runtime Error
input:
20000 20000 -856287 613193 884980 313749 -51917 -595036 -515889 732611 768011 201825 685038 -690361 -825296 610210 693313 378198 153998 -220528 -881367 -427847 -762386 726194 -882783 -396975 -585188 -646369 852468 -769564 845740 446417 -272832 806448 -23829 -843528 -290649 -509815 183302 929309 -810...
output:
result:
Test #5:
score: 0
Time Limit Exceeded
input:
20000 20000 272933 -400117 36074 -350576 -180416 245927 -152816 -532917 -815869 -121672 900928 561561 696604 -34106 281988 -30073 37999 -748187 -260504 367199 -254538 984542 -929979 -597816 735632 -731486 -88688 -820300 -180173 516379 319782 -306180 461815 88179 -863913 497662 -972928 920984 670858 ...
output:
result:
Test #6:
score: 0
Runtime Error
input:
20000 20000 961714 0 -256591 0 858025 0 302536 0 989232 0 921482 0 132252 0 -687494 0 976712 0 584368 0 -379471 0 -368374 0 -421478 0 -269707 0 -840836 0 683604 0 -233785 0 -509259 0 691924 0 -326966 0 699666 0 -602646 0 -394566 0 -762188 0 -721221 0 110375 0 123249 0 -679471 0 476495 0 -247891 0 -6...
output:
result:
Test #7:
score: 0
Time Limit Exceeded
input:
20000 20000 931651 0 -193344 0 -459921 0 -208681 0 265915 0 221047 0 -976889 0 836902 0 -128302 0 775194 0 523077 0 -398264 0 296667 0 -324286 0 477274 0 226741 0 -70369 0 627346 0 -81394 0 525865 0 454142 0 708462 0 -629738 0 -171617 0 -745312 0 -647420 0 -249238 0 -911374 0 255729 0 565402 0 -3974...
output:
result:
Test #8:
score: 0
Runtime Error
input:
20000 20000 286328653 0 -436132873 0 -950502327 0 62507734 0 410183824 0 -244422860 0 -89619254 0 -36224025 0 987264815 0 -366170043 0 789288990 0 595133547 0 129243363 0 480765515 0 -367270251 0 85317458 0 -717834130 0 990039646 0 601945059 0 979377776 0 487802144 0 -543661591 0 -649863532 0 530289...
output:
result:
Test #9:
score: 0
Runtime Error
input:
200000 200000 -412960500 577830338 99802584 -136950865 -950307156 -859369040 793568959 -565815756 411737945 -479377622 569675957 -601905445 -417176412 -729638186 200119881 -430545998 -86043427 969867029 64175162 -427861527 83451953 -756750354 -748032722 43908052 418515829 494502750 346664686 9215021...
output:
result:
Test #10:
score: 0
Runtime Error
input:
200000 200000 215020 -29462 152216 -199822 -604632 -191567 10263 -830451 -89159 -121408 -881329 -921244 -809798 -903639 29060 -438373 -393896 -438778 79484 803288 646060 323407 -150152 23631 -509647 -88435 -772163 923612 -832132 -270978 650123 -731403 997559 -457855 797171 863407 366847 -915734 -700...
output:
result:
Test #11:
score: 0
Time Limit Exceeded
input:
200000 200000 -814016 -440530 -988229 -214220 -825745 -268031 808279 -507843 -365671 559807 -823503 84191 685041 -755331 -379355 -288337 -730097 156308 -49982 -920817 135131 710420 786978 14054 -877243 607279 -61488 -541803 839910 -778520 498514 -990675 408344 758599 -596998 201097 -711216 615872 60...
output:
result:
Test #12:
score: 0
Time Limit Exceeded
input:
200000 200000 492262 0 767261 0 -49558 0 763447 0 -766015 0 305219 0 216950 0 309815 0 -563799 0 -576993 0 807708 0 -28765 0 805496 0 -792510 0 452313 0 636912 0 251743 0 367464 0 460580 0 731290 0 -899643 0 35424 0 900164 0 -627830 0 -200278 0 -364485 0 85580 0 348513 0 -445170 0 782325 0 867546 0 ...
output:
result:
Test #13:
score: 0
Time Limit Exceeded
input:
200000 200000 547911 0 477311 0 650541 0 -105453 0 626756 0 -374148 0 -185598 0 -740854 0 845506 0 692548 0 -87545 0 -338111 0 -672163 0 348336 0 790086 0 588112 0 874537 0 -165894 0 602594 0 -951962 0 121709 0 597190 0 -231436 0 954727 0 874009 0 923477 0 176425 0 -953583 0 107836 0 -354119 0 80494...
output:
result:
Test #14:
score: 0
Runtime Error
input:
200000 200000 -317746997 0 -151278487 0 231239102 0 -333682162 0 817071806 0 778079717 0 -29317929 0 -796844681 0 -969298078 0 -290624098 0 -687507332 0 967855359 0 -200682268 0 446953365 0 829160344 0 431722814 0 -321478842 0 500793767 0 -958916933 0 -993173724 0 -583938136 0 -621654506 0 540155031...
output:
result:
Test #15:
score: 0
Runtime Error
input:
2000 1000000 600102029 78163345 623529642 -781629210 -194743627 856505922 132730843 -866898111 496967234 357290802 424803615 -817449125 326888043 973054140 682875209 743038131 659124372 893679753 -415512262 835204413 -753019068 -821982592 650486625 656222368 765610921 -158965479 -131326155 454415998...
output:
result:
Test #16:
score: 0
Runtime Error
input:
2000 1000000 172304227 0 104292738 0 -257051223 0 -21999534 0 -574879748 0 -574439539 0 -947027598 0 765205348 0 195088335 0 406074782 0 75136395 0 227990070 0 900067610 0 675451839 0 804606264 0 556516588 0 -511265459 0 510580926 0 863647316 0 807267358 0 -778168632 0 127848817 0 255183075 0 -60073...
output:
result:
Test #17:
score: 0
Runtime Error
input:
1000000 10 156999516 -24390575 -347759760 638897014 -102812461 325031686 668597244 262829264 678216489 165516603 621656879 -412885032 233438419 931865318 709921083 -313209071 389603839 76036576 -769757796 359645480 -100357260 928717563 709905946 839359128 233518030 -695740543 524417586 -804059937 -4...
output:
result:
Test #18:
score: 0
Time Limit Exceeded
input:
1000000 10 281115 207197 -791397 227390 -769663 849805 -689936 477469 -251524 174662 189816 721806 -579178 -339234 993809 -705268 -690664 35222 -298116 -663820 -321165 -327572 -609151 166540 799070 -156124 -305786 89239 53446 -399972 845917 137485 316083 266638 -720291 -915315 -706115 135108 -161326...
output:
result:
Test #19:
score: 0
Runtime Error
input:
1000000 10 370517413 0 607064501 0 198217472 0 143369676 0 627031881 0 -242777381 0 -122948696 0 334651705 0 754835147 0 -975826131 0 -3570204 0 136544599 0 519231560 0 -21309928 0 -647797468 0 728822996 0 -239842256 0 854368498 0 -555223024 0 -177243458 0 -606866771 0 867321201 0 983555681 0 753390...
output:
result:
Test #20:
score: 0
Runtime Error
input:
1000000 1000000 -565158168 192228664 -60734026 -876227887 169956757 458933534 415705153 359751682 706646043 -267237804 -785235125 -286053701 -810363619 -883277015 -917766646 796218920 568429513 157525175 652148934 -563141041 101229780 387951397 138582181 234580165 989042915 303473055 848403115 67207...
output:
result:
Test #21:
score: 0
Time Limit Exceeded
input:
1000000 1000000 937028 -142721 470057 -596447 805603 -653737 422827 -146839 -134461 -284129 -740611 -822073 129788 -760939 189012 76048 -649576 825583 376935 955180 -675052 -614100 217445 -951905 463589 -489265 309830 -722532 510085 591599 -961137 67299 -817170 188112 338633 -558591 -571501 -205785 ...
output:
result:
Test #22:
score: 0
Runtime Error
input:
1000000 1000000 556639 -726845 488045 -320786 907001 -483744 941440 533716 -722534 856343 -338618 616639 491388 733720 -416677 107094 108121 465292 -123127 350855 657412 326868 -943626 -335813 -502533 257525 56288 -494808 -248448 -317412 463444 -822305 686331 178764 -255923 18808 -520494 -446761 624...
output:
result:
Test #23:
score: 0
Runtime Error
input:
1000000 1000000 -542377 0 80556 0 -734137 0 -588964 0 255112 0 598605 0 -363464 0 -703421 0 157594 0 -98285 0 799038 0 897889 0 -518690 0 -303647 0 -503359 0 166055 0 -173378 0 568761 0 -839895 0 -125384 0 -113615 0 -926581 0 -597497 0 865459 0 271137 0 779200 0 -589752 0 695449 0 -633220 0 477974 0...
output:
result:
Test #24:
score: 0
Runtime Error
input:
1000000 1000000 475716 0 733854 0 -670602 0 -495883 0 879413 0 -549166 0 395637 0 -922358 0 -95497 0 261093 0 -855001 0 -232761 0 839785 0 415412 0 456189 0 487755 0 951642 0 68750 0 -207887 0 108335 0 73919 0 -829879 0 -521857 0 -235996 0 -474559 0 50128 0 599195 0 -72168 0 454461 0 384522 0 -27507...
output:
result:
Test #25:
score: 0
Runtime Error
input:
1000000 1000000 -647194312 0 923266193 0 311967052 0 26202656 0 145325407 0 -363221031 0 322109698 0 400374410 0 -666477923 0 -803868087 0 -739610118 0 941620833 0 335162000 0 -343764277 0 -854360295 0 354763517 0 -559596318 0 -857042621 0 638986823 0 -794261929 0 137855671 0 317157550 0 942335473 0...