QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#461048#4409. 袜子Nityacke0 0ms0kbC++204.3kb2024-07-02 15:31:492024-07-02 15:31:50

Judging History

你现在查看的是最新测评结果

  • [2024-07-02 15:31:50]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-07-02 15:31:49]
  • 提交

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";
}

詳細信息

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%