QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#461048 | #4409. 袜子 | Nityacke | 0 | 0ms | 0kb | C++20 | 4.3kb | 2024-07-02 15:31:49 | 2024-07-02 15:31:50 |
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 int long long
#define db double
#define pb push_back
using namespace std;
const int N=5e5+5,M=5e4,INF=2e9;
bool Med;
int n,m,ans[N];
struct pt{int x,y,c;}a[M];
struct point{db x,y;int id;};
vector<pt>G[M];
namespace Sub1{
vector<pt>Q1,Q2;
int cnt[M],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<=m&&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;
for(auto v:Q1){
while(idx<=m&&v.x*a[idx].y+v.y>0) ++cnt[a[idx].c],res+=2*cnt[a[idx].c]-1,++idx;
ans[v.c]=res;
}
}
}
vector<point>Vec;
int tot,rt;
struct Node{
db xl=INF,xr,yl=INF,yr;
int id,tag,ans,lc,rc;
inline void init(point a){xl=xr=a.x,yl=yr=a.y,id=a.id,tag=ans=lc=rc=0;}
}t[N<<1];
#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;
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;
vector<int>S,S1;
inline bool cmp(db a,db b){return flag?a<0:a>0;}
inline db calc(db x,db y){return A*x+B*y+C;}
inline db Mn(int k){return min({calc(t[k].xl,t[k].yl),calc(t[k].xl,t[k].yr),calc(t[k].xr,t[k].yl),calc(t[k].xr,t[k].yr)});}
inline db Mx(int k){return max({calc(t[k].xl,t[k].yl),calc(t[k].xl,t[k].yr),calc(t[k].xr,t[k].yl),calc(t[k].xr,t[k].yr)});}
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;}
inline bool change(int k){
db mx=Mx(k),mn=Mn(k);
// cerr<<A<<" "<<B<<" "<<C<<" "<<k<<" "<<mx<<" "<<mn<<"\n";
if((flag&&mx<0)||(!flag&&mn>0)) return add(k,1),S.pb(k),1;
if((flag&&mn>=0)||(flag&&mx<=0)) return 0;
bool fl=t[k].tag;
push(k);
fl|=change(k1)|change(k2);
if(fl) S.pb(k),S1.pb(k);
return fl;
}
inline void calc(){
sort(S.begin(),S.end()),S.erase(unique(S.begin(),S.end()),S.end());
sort(S1.begin(),S1.end()),S1.erase(unique(S1.begin(),S1.end()),S1.end());
for(auto k:S1) push(k);
for(auto k:S) t[k].ans+=t[k].tag*t[k].tag,t[k].tag=0;
S.clear(),S1.clear();
}
namespace T1{
vector<point>vec;
inline void add(db x,db 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(auto v:Vec) cerr<<v.x<<" "<<v.y<<"\n";
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();
}
dfs(1,0,sz-1);
}
}
namespace T2{
vector<point>vec;
inline void add(db x,db 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();
}
dfs(1,0,sz-1);
}
}
bool Mst;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cerr<<(&Med-&Mst)/1024.0/1024.0<<"\n";
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(1.0*C/A,1.0*B/A,i);
else T2::add(1.0*C/A,1.0*B/A,i);
}
T1::solve(),T2::solve(),Sub1::solve();
for(int i=1;i<=m;++i) cout<<ans[i]<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Memory Limit Exceeded
Test #1:
score: 0
Memory Limit Exceeded
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:
result:
Subtask #2:
score: 0
Memory Limit Exceeded
Test #11:
score: 0
Memory 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
Memory Limit Exceeded
Test #19:
score: 0
Memory 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: 0
Memory Limit Exceeded
Test #25:
score: 0
Memory Limit Exceeded
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:
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
0%