QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#461964 | #4409. 袜子 | Nityacke | 15 | 1140ms | 228676kb | C++20 | 6.4kb | 2024-07-03 11:18:33 | 2024-07-03 11:18:33 |
Judging History
answer
// Problem: P8261 [CTS2022] 袜子
// URL: https://www.luogu.com.cn/problem/P8261
// Memory Limit: 512 MB
// Time Limit: 8000 ms
// Author: Nityacke
// Time: 2024-07-02 14:39:41
#include<bits/stdc++.h>
#define ll long long
#define db double
#define pb push_back
using namespace std;
const int N=5e5+5,M=5e5+5,INF=2e9;
bool Med;
int n,m;
ll ans[N];
struct pt{int x,y,c;}a[M];
vector<pt>G[50005];
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
}
namespace Sub1{
vector<pt>Q1,Q2;
int cnt[M];
ll res;
inline void add(int x,int y,int c){
if(x>0) Q1.pb({x,y,c});
else Q2.pb({x,y,c});
}
inline void solve(){
sort(a+1,a+n+1,[&](pt a,pt b){return a.y<b.y;});
sort(Q1.begin(),Q1.end(),[&](pt a,pt b){return (-1.0*a.y/a.x)<(-1.0*b.y/b.x);});
sort(Q2.begin(),Q2.end(),[&](pt a,pt b){return (-1.0*a.y/a.x)>(-1.0*b.y/b.x);});
int idx=1;
for(auto v:Q1){
while(idx<=n&&1ll*v.x*a[idx].y+v.y<0) ++cnt[a[idx].c],res+=2*cnt[a[idx].c]-1,++idx;
ans[v.c]=res;
}
for(int i=0;i<M;++i) cnt[i]=0;
sort(a+1,a+n+1,[&](pt a,pt b){return a.y>b.y;});
idx=1,res=0;
for(auto v:Q2){
while(idx<=n&&1ll*v.x*a[idx].y+v.y<0) ++cnt[a[idx].c],res+=2*cnt[a[idx].c]-1,++idx;
ans[v.c]=res;
}
}
}
struct frac{
ll a,b;
inline frac(ll _a=1,ll _b=1){
if(_b<0) _a=-_a,_b=-_b;
a=_a,b=_b;
}
inline friend frac max(frac A,frac B){return A.a*B.b<B.a*A.b?B:A;}
inline friend frac min(frac A,frac B){return A.a*B.b<B.a*A.b?A:B;}
inline friend bool operator<(frac A,frac B){
return A.a*B.b<B.a*A.b;
}
inline friend frac operator*(frac A,int b){
return frac(A.a*b,A.b);
}
inline friend frac operator+(frac A,frac B){
return frac(A.a*B.b+A.b*B.a,A.b*B.b);
}
inline friend frac operator+(frac A,int b){
return frac(A.a+A.b*b,A.b);
}
};
struct point{frac x,y;int id;};
vector<point>Vec;
int tot,rt;
struct Node{
frac xl,xr,yl,yr;
int id,tag,lc,rc;
ll ans;
inline void init(point a){xl=xr=a.x,yl=yr=a.y,id=a.id,tag=ans=lc=rc=0;}
}t[N<<2];
#define k1 t[k].lc
#define k2 t[k].rc
#define mid ((l+r)>>1)
inline bool cmpx(point A,point B){return A.x<B.x;}
inline bool cmpy(point A,point B){return A.y<B.y;}
inline void up(int k){
t[k].xl=min(t[k1].xl,t[k2].xl),t[k].xr=max(t[k1].xr,t[k2].xr),
t[k].yl=min(t[k1].yl,t[k2].yl),t[k].yr=max(t[k1].yr,t[k2].yr);
}
inline int build(int l,int r,int d=0){
int k=++tot;
t[k].ans=t[k].tag=t[k].id=0;
if(l==r) return t[k].init(Vec[l]),k;
nth_element(Vec.begin()+l,Vec.begin()+mid,Vec.begin()+r+1,d?cmpx:cmpy);
k1=build(l,mid,d^1),k2=build(mid+1,r,d^1);
return up(k),k;
}
int A,B,C;
bool flag;
inline frac Mn(int k){
frac now(C,1);
if(A<=0) now=now+t[k].xr*A;
else now=now+t[k].xl*A;
if(B<=0) now=now+t[k].yr*B;
else now=now+t[k].yl*B;
return now;
}
inline frac Mx(int k){
frac now(C,1);
if(A>=0) now=now+t[k].xr*A;
else now=now+t[k].xl*A;
if(B>=0) now=now+t[k].yr*B;
else now=now+t[k].yl*B;
return now;
}
inline void dfs(int k,int l,int r){
if(l==r) return ans[t[k].id]=t[k].ans,void();
t[k1].ans+=t[k].ans,t[k2].ans+=t[k].ans;
dfs(k1,l,mid),dfs(k2,mid+1,r);
}
inline void add(int k,int v){t[k].tag+=v;}
inline void push(int k){if(t[k].tag) add(k1,t[k].tag),add(k2,t[k].tag),t[k].tag=0;}
int vis[N<<2];
inline void change(int k){
frac mx=Mx(k),mn=Mn(k);
vis[k]=1;
if((flag&&mx.a<0)||(!flag&&mn.a>0)) return add(k,1);
if((flag&&mn.a>=0)||(!flag&&mx.a<=0)) return;
push(k),change(k1),change(k2);
}
inline void calc(int k){
if(!vis[k1]&&!vis[k2]) return t[k].ans+=1ll*t[k].tag*t[k].tag,vis[k]=t[k].tag=0,void();
push(k),calc(k1),calc(k2),vis[k]=0;
}
namespace T1{
vector<point>vec;
inline void add(frac x,frac y,int id){vec.pb({x,y,id});}
inline void solve(){
int sz=(int)vec.size();
if(!sz) return;
flag=1,tot=0,Vec=vec,rt=build(0,sz-1);
for(int i=1;i<=n;++i)
if(G[i].size()){
for(auto v:G[i]) A=1,B=v.y,C=v.x,change(1);
calc(rt);
}
dfs(rt,0,sz-1);
}
}
namespace T2{
vector<point>vec;
inline void add(frac x,frac y,int id){vec.pb({x,y,id});}
inline void solve(){
int sz=(int)vec.size();
if(!sz) return;
flag=0,tot=0,Vec=vec,rt=build(0,sz-1);
for(int i=1;i<=n;++i)
if(G[i].size()){
for(auto v:G[i]) A=1,B=v.y,C=v.x,change(1);
calc(rt);
}
dfs(rt,0,sz-1);
}
}
bool Mst;
signed main(){
cin>>n>>m;
for(int i=1;i<=n;++i) cin>>a[i].x>>a[i].y>>a[i].c,G[a[i].c].pb({a[i].x,a[i].y,i});
for(int A,B,C,i=1;i<=m;++i){
cin>>A>>B>>C;
if(!A) Sub1::add(B,C,i);
else if(A>0) T1::add(frac(C,A),frac(B,A),i);
else T2::add(frac(C,A),frac(B,A),i);
}
T1::solve(),T2::solve(),Sub1::solve();
for(int i=1;i<=m;++i) cout<<ans[i]<<"\n";
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 8ms
memory: 180024kb
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:
2551 391 665 1903 152 2984 185 387 2224 645 2698 422 2093 0 280 108 136 346 2225 2810 1707 2640 2669 627 152 1949 399 126 285 0 2342 2224 0 2694 2098 2704 2627 2763 136 320 0 152 2418 323 251 364 155 291 295 445 136 2138 302 2477 2443 336 295 2418 285 1985 306 1863 2767 0 319 2861 264 270 192 138 25...
result:
wrong answer 1st numbers differ - expected: '1047', found: '2551'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 372ms
memory: 223248kb
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:
289697300 457907165 333189965 1482943905 221873569 199752714 1824759056 47792273 1754040025 1716372820 35249818 1786257890 2099228356 113557905 46856525 118078056 131752948 1779081653 110529893 376422210 30076020 113430069 1363453600 289867525 1732657232 36846925 258967348 38367845 1791767168 377270...
result:
wrong answer 1st numbers differ - expected: '618496745', found: '289697300'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 653ms
memory: 218536kb
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:
6192048 43034742 34599735 31000686 4564512 48739336 9334184 32598648 8466574 191269 42878514 46705318 54231 28981694 45604760 8384441 8507204 46576568 6210904 3726882 54231 10637888 53745 10864191 6192048 42879703 48739336 40096765 2219677 42946464 2500231 40772500 46576568 8507204 496853 48724 6869...
result:
wrong answer 1st numbers differ - expected: '12162691', found: '6192048'
Subtask #5:
score: 15
Accepted
Test #25:
score: 15
Accepted
time: 902ms
memory: 219860kb
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: 0
Accepted
time: 1140ms
memory: 220548kb
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: 0
Accepted
time: 952ms
memory: 219172kb
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: 0
Accepted
time: 1049ms
memory: 228676kb
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: 0
Accepted
time: 1046ms
memory: 221240kb
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: 0
Accepted
time: 1017ms
memory: 220268kb
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%