QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#544203 | #4409. 袜子 | Nityacke | 15 | 2077ms | 320300kb | C++20 | 5.9kb | 2024-09-02 12:04:55 | 2024-09-02 12:04:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define int long long
#define db frac
const int maxn=5e5+5;
struct frac{
int x,y;
frac(int a=0,int b=1){
x=a,y=b;
if(b<0)x=-x,y=-y;
}
};
inline frac operator +(frac A,frac B){return frac(A.x*B.y+A.y*B.x,A.y*B.y);}
inline frac operator -(frac A,frac B){return frac(A.x*B.y-A.y*B.x,A.y*B.y);}
inline frac operator *(frac A,frac B){return frac(A.x*B.x,A.y*B.y);}
inline frac operator *(frac A,int B){return frac(A.x*B,A.y);}
inline frac operator +(frac A,int B){return frac(A.x+A.y*B,A.y);}
inline bool operator <(frac A,frac B){return A.x*B.y<A.y*B.x;}
inline bool operator >(frac A,frac B){return A.x*B.y>A.y*B.x;}
inline frac operator *=(frac &A,int B){return A=A*B;}
struct line{
db a,b,c;
inline db operator ()(db x,db y){return a*x+b*y+c;}
};
namespace Fastio {
#define USE_FASTIO 1
#define IN_LEN 450000
#define OUT_LEN 450000
char ch, c; int len;
short f, top, s;
inline char Getchar() {
static char buf[IN_LEN], *l = buf, *r = buf;
if (l == r) r = (l = buf) + fread(buf, 1, IN_LEN, stdin);
return (l == r) ? EOF : *l++;
}
char obuf[OUT_LEN], *ooh = obuf;
inline void Putchar(char c) {
if (ooh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh = obuf;
*ooh++ = c;
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }
#undef IN_LEN
#undef OUT_LEN
struct Reader {
template <typename T> Reader& operator >> (T &x) {
x = 0, f = 1, c = Getchar();
while (!isdigit(c)) { if (c == '-') f *= -1; c = Getchar(); }
while ( isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = Getchar();
x *= f;
return *this;
}
Reader() {}
} cin;
const char endl = '\n';
struct Writer {
typedef long long mxdouble;
template <typename T> Writer& operator << (T x) {
if (x == 0) { Putchar('0'); return *this; }
if (x < 0) Putchar('-'), x = -x;
static short sta[40];
top = 0;
while (x > 0) sta[++top] = x % 10, x /= 10;
while (top > 0) Putchar(sta[top] + '0'), top--;
return *this;
}
Writer& operator << (const char *str) {
int cur = 0;
while (str[cur]) Putchar(str[cur++]);
return *this;
}
inline Writer& operator << (char c) {Putchar(c); return *this;}
Writer() {}
~ Writer () {flush();}
} cout;
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
}
struct node{
db mn[2],mx[2];
int ls,rs,tag,ans,id;
}xds[maxn<<2];
int ans[maxn];
inline void pushup(int k){for(int i=0;i<2;i++)xds[k].mn[i]=min(xds[xds[k].ls].mn[i],xds[xds[k].rs].mn[i]),xds[k].mx[i]=max(xds[xds[k].ls].mx[i],xds[xds[k].rs].mx[i]);}
inline void ADD(int k,int v){xds[k].tag+=v;}
inline void pushdown(int k){ADD(xds[k].ls,xds[k].tag),ADD(xds[k].rs,xds[k].tag),xds[k].tag=0;}
#define mid ((l+r)>>1)
void dfs(int k,int l,int r){
if(l==r)return ans[xds[k].id]+=xds[k].ans,void();
xds[xds[k].ls].ans+=xds[k].ans;xds[xds[k].rs].ans+=xds[k].ans;
dfs(xds[k].ls,l,mid);dfs(xds[k].rs,mid+1,r);
}
inline int pd(int k,line Q){
int res=0;
res+=(Q(xds[k].mn[0],xds[k].mn[1])>0);
res+=(Q(xds[k].mn[0],xds[k].mx[1])>0);
res+=(Q(xds[k].mx[0],xds[k].mn[1])>0);
res+=(Q(xds[k].mx[0],xds[k].mx[1])>0);
return res;
}
bool vis[maxn<<2];
void modify(int k,line Q){
int z=pd(k,Q);
vis[k]=1;
if(z==0)return ;
if(z==4){
// cerr<<"ADD "<<k<<" "<<1<<endl;
return ADD(k,1);
}
pushdown(k);
modify(xds[k].ls,Q);modify(xds[k].rs,Q);
}
struct pt{int id;db x,y;}cp[maxn];
bool cmpx(pt a,pt b){return a.x<b.x;}
bool cmpy(pt a,pt b){return a.y<b.y;}
int cnt=0;
void build(int &k,int l,int r,int d){
k=++cnt;
xds[k].tag=xds[k].ans=0;
if(l==r){
xds[k].mn[0]=xds[k].mx[0]=cp[l].x,xds[k].mn[1]=xds[k].mx[1]=cp[l].y;
xds[k].ls=xds[k].rs=0,xds[k].id=cp[l].id;
return ;
}
nth_element(cp+l,cp+mid,cp+r,d?cmpx:cmpy);
build(xds[k].ls,l,mid,d^1);build(xds[k].rs,mid+1,r,d^1);
pushup(k);
// cerr<<k<<" -> "<<xds[k].ls<<","<<xds[k].rs<<endl;
}
void dfs2(int k){
if(!vis[xds[k].ls]&&!vis[xds[k].rs]){
// cerr<<k<<" ans updated by "<<xds[k].tag*xds[k].tag<<endl;
return xds[k].ans+=xds[k].tag*xds[k].tag,xds[k].tag=0,vis[k]=0,void();
}
pushdown(k);
dfs2(xds[k].ls);dfs2(xds[k].rs);vis[k]=0;
}
int n,m;
vector<line> e[maxn];
struct lxl_dick_sucker{
pair<db,int> p[maxn],L[maxn];
int tot,cntc[maxn],cur;
lxl_dick_sucker(){cur=tot=0;}
void solve(){
if(!tot)return ;
sort(p+1,p+n+1);sort(L+1,L+tot+1);
int now=0;
for(int i=1;i<=tot;i++){
while(now+1<=n&&p[now+1].first<L[i].first){
++now;int &t=cntc[p[now].second];t++;
cur+=t*t-(t-1)*(t-1);
}
ans[L[i].second]=cur;
}
}
}T[2];
struct lxl_ass_kicker{
pt p[maxn];
int tot,tp,rt;
lxl_ass_kicker(){tot=0;}
void solve(){
if(!tot)return ;
cnt=0;
for(int i=1;i<=tot;i++)cp[i]=p[i];
build(rt,1,tot,0);
for(int i=1;i<=n;i++){
// cerr<<"___________________________"<<endl;
for(auto [A,B,C]:e[i]){
A*=tp,B*=tp,C*=tp;
// cerr<<"Line : "<<A<<" "<<B<<" "<<C<<endl;
modify(rt,{A,B,C});
}
dfs2(rt);
}
dfs(rt,1,tot);
}
}P[2];
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int x,y,c;cin>>x>>y>>c;
e[c].push_back({y,1,x});
T[0].p[i]={y,c};
T[1].p[i]={-y,c};
}
P[0].tp=-1;P[1].tp=1;
for(int i=1;i<=m;i++){
int A,B,C;cin>>A>>B>>C;
if(A==0){
if(B>0)T[0].L[++T[0].tot]={frac(-C,B),i};
else T[1].L[++T[1].tot]={frac(C,B),i};
}else{
if(A>0)P[0].p[++P[0].tot]={i,frac(B,A),1.0*frac(C,A)};
else P[1].p[++P[1].tot]={i,frac(B,A),1.0*frac(C,A)};
}
}
T[0].solve(),T[1].solve();
P[0].solve();P[1].solve();
for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 40ms
memory: 313828kb
input:
1000 1000 8756 4483 237 -7891 -2818 114 8667 -7202 36 8150 -2 248 -4483 -9934 375 -9669 -1815 802 4008 9788 22 -2193 -4988 307 -9813 -4926 22 6344 8542 93 -9906 -9906 38 -3791 -2822 814 -7118 8408 51 -779 9589 3 -3211 1342 73 2346 -6502 112 31 -5037 6 3714 -4554 118 8788 6735 533 3860 -4232 5 3257 6...
output:
1103 1034 853 1319 1060 1090 870 972 1029 843 1115 1012 1205 0 869 879 1060 1026 1048 1035 963 1386 1181 989 1060 1082 944 1034 1017 0 1554 1102 0 1128 1187 1214 1205 1063 1060 940 0 1060 1060 962 860 958 890 1020 849 970 1060 1025 906 1455 1480 878 1051 1060 917 1122 956 1323 1083 0 967 1034 1011 8...
result:
wrong answer 1st numbers differ - expected: '1047', found: '1103'
Subtask #2:
score: 0
Time Limit Exceeded
Test #11:
score: 0
Time Limit Exceeded
input:
50000 500000 384309433 -953786733 1 -381089810 891795502 1 -701194776 440247159 1 -403243027 539105336 1 275206790 -652250203 1 -554746251 903743804 1 -457035253 912757156 1 -342310772 -17612092 1 -440332191 682239316 1 730332275 816145283 1 -701691234 -908289789 1 -632861504 -277378843 1 -567495050...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Time Limit Exceeded
Test #19:
score: 0
Time Limit Exceeded
input:
50000 500000 2598 -1000000 6 1388 -1000000 3 5492 1000000 8 -1000000 -3573 23 -1000000 -7880 15 -4285 1000000 7 1000000 5211 5 -1000000 5915 79 7147 -1000000 29 -9495 -1000000 25 9028 1000000 1 1000000 -4880 20 -8498 1000000 53 1000000 -4256 22 3107 -1000000 29 2061 -1000000 45 8876 -1000000 76 -279...
output:
result:
Subtask #5:
score: 15
Accepted
Test #25:
score: 15
Accepted
time: 1393ms
memory: 320052kb
input:
50000 500000 407 -5105 53 6211 98 81 7444 6196 1 -4294 -9353 26 4316 -3143 1 7144 2361 17 6364 -2245 14 -8684 -6564 3 6269 -687 2 -3139 5693 12 -9991 6547 20 2179 2178 47 -6588 7830 21 -6216 -200 3 9207 8834 24 9388 -5953 31 7752 4125 39 7875 -5517 22 -4701 2244 12 8088 3158 4 -4446 3467 1 -1002 154...
output:
10325005 11474809 0 0 11518032 0 0 49015742 49015742 49015742 0 11392831 0 49015742 0 13876057 0 13339251 10553686 49015742 49015742 49015742 14634637 0 0 49015742 49015742 0 11099497 49015742 11282162 0 0 49015742 0 49015742 0 49015742 49015742 49015742 0 49015742 13190125 13266876 0 0 10953869 116...
result:
ok 500000 numbers
Test #26:
score: 15
Accepted
time: 2077ms
memory: 320300kb
input:
50000 500000 -798827 -248238 55 -202385 195966 51 -935972 695372 12 -207494 597523 36 828639 839545 1 604085 -878258 28 854907 987889 33 -488652 555674 10 -308758 201373 2 786438 -72867 11 -533482 -614535 58 -853349 714523 60 729730 441018 27 193712 759574 30 -439466 -262414 1 -995124 383459 76 5638...
output:
12116545 1627120 12028488 8327000 11890527 12038075 12100532 30829152 23884384 48253618 0 0 48253618 12079058 4707441 34295749 1085217 12123770 48253618 20695368 11904819 3608287 12253559 0 12074236 12265677 12236373 48253618 12250929 0 11885547 11885547 7336386 12109428 48253618 0 0 36922388 511026...
result:
ok 500000 numbers
Test #27:
score: 15
Accepted
time: 1888ms
memory: 320084kb
input:
50000 500000 916228474 736861331 8 41223569 567024226 2 33633521 -640602439 11 43060388 157896754 9 522582493 -456464181 2 184581697 729182371 8 -915463955 774500464 2 595541741 4861507 3 375567184 -686285601 3 -59758078 -72014188 11 -535452680 -972290610 4 -425062848 998970443 3 776900364 383068694...
output:
73688076 34624304 35713642 74151261 74568055 73687317 80280672 73694989 74197031 74197031 190116467 73477393 74568055 23847839 86652478 126942497 108464771 74197031 125422244 56618750 74568055 73657436 9934358 85804146 74568055 221183265 178732347 73330257 73172655 74197031 73622903 74619669 7449609...
result:
ok 500000 numbers
Test #28:
score: 15
Accepted
time: 1796ms
memory: 319856kb
input:
50000 500000 -218467527 996547968 2 667898126 353067063 1 -703792310 -88011029 3 796101380 -150592337 1 233483304 202627437 1 227009907 -277641383 1 398753734 123601516 1 -932943038 -991506612 1 -586877275 884068330 1 -14924328 992992981 15 -558045242 470672933 7 -305045173 -532112183 7 183202586 80...
output:
34171044 145124721 133863158 322891322 149231859 144059207 201503200 147989909 145302374 145382184 145302231 144074835 144074694 186273717 391942339 147909184 145382184 147909184 45485862 30564622 147909184 13602211 29269333 136955300 161713859 145417496 411765627 144050978 147901245 147744158 30332...
result:
ok 500000 numbers
Test #29:
score: 15
Accepted
time: 1443ms
memory: 319780kb
input:
50000 500000 -209258179 -13673102 2 -536850965 -914833237 1 -859835086 -387099479 7 650316207 -949976551 2 490090099 432733293 1 295590818 336348152 1 -924146823 -481896977 1 -688990212 -402275949 1 905552333 225834084 1 100755207 -115968339 5 409919132 761133402 1 -486717813 -425455505 1 -448210451...
output:
342217921 351225756 335443425 351262509 109504291 342519167 344283077 344283077 335848738 803468818 538859665 335443425 344283077 344548834 351534475 335399668 765872733 216202376 344283077 335363755 351409541 51890336 201074052 335443425 351534475 335363755 351452899 124534601 342217921 351828683 3...
result:
ok 500000 numbers
Test #30:
score: 15
Accepted
time: 1751ms
memory: 320280kb
input:
50000 500000 -683034611 -711257501 27 60004722 -761142590 25 661166166 -468685357 7 849005124 -979617930 65 -844130034 690778896 26 420045533 -127259351 21 770352203 284425974 4 767529443 -311119877 25 -773073204 -708678356 61 -616770488 -127741421 27 -439194801 -804840917 7 -102517861 -591985498 15...
output:
5176455 36752777 12349440 9037077 11988285 12249163 12230497 6719556 12344687 12249163 11988285 12055113 31826512 12074401 15191922 32592923 12074401 12358058 10249606 12249163 11988285 12009512 12074401 12067085 11988285 12074401 12345034 12349440 12074401 11998182 12074401 23409470 1079840 2820121...
result:
ok 500000 numbers
Subtask #6:
score: 0
Skipped
Dependency #1:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
0%