QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#393538#7436. Optimal Ordered Problem Solverlcs0802060 2930ms249184kbC++146.8kb2024-04-18 19:14:072024-04-18 19:14:08

Judging History

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

  • [2024-04-18 19:14:08]
  • 评测
  • 测评结果：0
  • 用时：2930ms
  • 内存：249184kb
查看
  • [2024-04-18 19:14:07]
  • 提交

answer

#include<bits/stdc++.h>
#define N 1000005
#define ls x<<1
#define rs x<<1|1
using namespace std;
int n,m;

struct node{
	int x,y;
}a[N];
bool cmp1(node x,node y){return x.x==y.x?x.y<y.y:x.x<y.x;}

struct Qr{
	int o,x,y,X,Y;
	int ans1;
}q[N];
struct Qr2{int x,y,id;};

struct tree1{
	int tr[N];
	int lb(int x){return (x&-x);}
	void upd(int x,int y){
		for(int i=x;i<=n;i+=lb(i)){
			tr[i]+=y;
		}
	}
	int qr(int x){
		int res=0;
		for(int i=x;i;i-=lb(i))res+=tr[i];
		return res;
	}
}tr1;//二维数点 
vector<Qr2>qr[N];

struct SG1{
	int minn[N<<2];
	void pup(int x){minn[x]=min(minn[ls],minn[rs]);}
	void upd(int x,int l,int r,int t,int v){
		if(l>t||r<t)return;
		if(l==r){minn[x]=v;return;}
		int mid=l+r>>1;
		upd(ls,l,mid,t,v);upd(rs,mid+1,r,t,v);pup(x);
	}
	int query1(int x,int l,int r,int tl,int tr){
		if(l>tr||r<tl)return n+1;
		if(l>=tl&&r<=tr)return minn[x];
		int mid=l+r>>1;
		return min(query1(ls,l,mid,tl,tr),query1(rs,mid+1,r,tl,tr));
	}
	int query2(int x,int l,int r,int tl,int tr,int v){
		if(l>tr||r<tl)return 0;
		if(l>=tl&&r<=tr){
			if(minn[x]!=v)return 0;
			if(l==r)return l;
			int mid=l+r>>1,X=query2(ls,l,mid,tl,tr,v);
			if(!X)return query2(rs,mid+1,r,tl,tr,v);
			return X;
		}
		int mid=l+r>>1,X=query2(ls,l,mid,tl,tr,v);
		if(!X)return query2(rs,mid+1,r,tl,tr,v);
		return X;
	}
}tree;
vector<int>tx[N];
int totx[N];//散点修改 

struct SG2{
	int val[N<<2];
	void pup(int x){val[x]=val[ls]+val[rs];}
	void upd(int x,int l,int r,int t,int v){
		if(l>t||r<t)return;
		if(l==r){val[x]+=v;return;}
		int mid=l+r>>1;
		upd(ls,l,mid,t,v);upd(rs,mid+1,r,t,v);pup(x);
	}
	int query(int x,int l,int r,int tl,int tr){
		if(l>tr||r<tl)return 0;
		if(l>=tl&&r<=tr)return val[x];
		int mid=l+r>>1;
		return query(ls,l,mid,tl,tr)+query(rs,mid+1,r,tl,tr);
	}
}tr_x,tr_y;//散点计数 

struct SG3{
	int val[N<<2],tag[N<<2];
	void pd(int x){
		if(!tag[x])return;
		tag[ls]=tag[rs]=tag[x];
		val[ls]=val[rs]=0;tag[x]=0;
	}
	void pup(int x){val[x]=val[ls]+val[rs];}
	void upd(int x,int l,int r,int t,int v){
		if(l>t||r<t)return;
		if(l==r){val[x]+=v;return;}
		pd(x);int mid=l+r>>1;
		upd(ls,l,mid,t,v);upd(rs,mid+1,r,t,v);pup(x);
	}
	void upd2(int x,int l,int r,int tl,int tr){
		if(l>tr||r<tl)return;
		if(l>=tl&&r<=tr){tag[x]=1;val[x]=0;return;}
		pd(x);int mid=l+r>>1;
		upd2(ls,l,mid,tl,tr);upd2(rs,mid+1,r,tl,tr);pup(x);
	}
	int query(int x,int l,int r,int tl,int tr){
		if(l>tr||r<tl)return 0;
		if(l>=tl&&r<=tr)return val[x];
		pd(x);int mid=l+r>>1;
		return query(ls,l,mid,tl,tr)+query(rs,mid+1,r,tl,tr);
	}
}tr2_x,tr2_y;//轮廓线上点 

struct SG4{
	int minn[N<<2],tag[N<<2];
	void pd(int x){
		minn[ls]=max(minn[ls],tag[x]);
		minn[rs]=max(minn[rs],tag[x]);
		tag[ls]=max(tag[ls],tag[x]);
		tag[rs]=max(tag[x],tag[rs]);
		tag[x]=0;
	}
	void pup(int x){minn[x]=min(minn[ls],minn[rs]);}
	void upd(int x,int l,int r,int tl,int tr,int v){
		if(l>tr||r<tl)return;
		if(l>=tl&&r<=tr){
			minn[x]=max(minn[x],v);tag[x]=max(tag[x],v);return;
		}
		pd(x);int mid=l+r>>1;
		upd(ls,l,mid,tl,tr,v);upd(rs,mid+1,r,tl,tr,v);pup(x);
	}
	int query1(int x,int l,int r,int t){
		if(l>t||r<t)return 0;
		if(l==r)return minn[x];
		pd(x);int mid=l+r>>1;
		return query1(ls,l,mid,t)+query1(rs,mid+1,r,t);
	}
	int query2(int x,int l,int r,int t){
		if(minn[x]>t)return n+1;
		if(l==r)return l;
		pd(x);int mid=l+r>>1,X=query2(ls,l,mid,t);
		if(X==n+1)return query2(rs,mid+1,r,t);
		return X;
	}
}sx,sy;//轮廓线 

struct SG5{
	int val[N<<2];
	void pd(int x){
		if(!val[x])return;
		val[ls]=val[rs]=val[x];val[x]=0;
	}
	void upd(int x,int l,int r,int tl,int tr,int v){
		if(l>tr||r<tl)return;
		if(l>=tl&&r<=tr){
			val[x]=v;return;
		}pd(x);int mid=l+r>>1;
		upd(ls,l,mid,tl,tr,v);upd(rs,mid+1,r,tl,tr,v);
	}
	int query(int x,int l,int r,int t){
		if(l>t||r<t)return 0;
		if(l==r)return val[x];
		pd(x);int mid=l+r>>1;
		return query(ls,l,mid,t)+query(rs,mid+1,r,t);
	}
}dx;//凸点 

void updx(Qr x){
	int Y1=sx.query1(1,1,n,x.x),X1=sy.query1(1,1,n,x.y);
	if(X1>x.x&&Y1>x.y)return;
	if(X1==x.x&&Y1==x.y)return;
	while(1){
		int X=tree.query1(1,1,n,1,x.x);
		if(X>x.y)break;
		int Y=tree.query2(1,1,n,1,x.x,X),YYY=tx[Y][totx[Y]];
		tr_x.upd(1,1,n,Y,-1);tr_y.upd(1,1,n,YYY,-1);
		tr2_x.upd(1,1,n,Y,1);tr2_y.upd(1,1,n,x.y,1);
		++totx[Y];
		if(totx[Y]==tx[Y].size())tree.upd(1,1,n,Y,n+1);
		else tree.upd(1,1,n,Y,tx[Y][totx[Y]]);
	}
	int YY=sy.query2(1,1,n,x.x),XX=sx.query2(1,1,n,x.y);
	int X=tr2_y.query(1,1,n,YY-1,x.y),TY=sy.query1(1,1,n,YY-1)-1,Y=tr2_x.query(1,1,n,x.x+1,TY)+dx.query(1,1,n,TY+1);
	tr2_y.upd2(1,1,n,YY-1,x.y);
	tr2_y.upd(1,1,n,x.y,X-Y);
	tr2_y.upd(1,1,n,YY-1,Y);
	sx.upd(1,1,n,XX,x.x,x.y);
	sy.upd(1,1,n,YY,x.y,x.x);
	if(X1==x.x||Y1==x.y)return;
	dx.upd(1,1,n,XX,x.x,1);
	dx.upd(1,1,n,x.x,x.x,tr2_x.query(1,1,n,x.x,x.x));
}
void updy(Qr x){
	int Y1=sx.query1(1,1,n,x.x),X1=sy.query1(1,1,n,x.y);
	if(X1>x.x&&Y1>x.y)return;
	if(X1==x.x&&Y1==x.y)return;
	while(1){
		int X=tree.query1(1,1,n,1,x.x);
		if(X>x.y)break;
		int Y=tree.query2(1,1,n,1,x.x,X),YYY=tx[Y][totx[Y]];
		tr_x.upd(1,1,n,Y,-1);tr_y.upd(1,1,n,YYY,-1);
		tr2_x.upd(1,1,n,x.x,1);tr2_y.upd(1,1,n,YYY,1);
		++totx[Y];
		if(totx[Y]==tx[Y].size())tree.upd(1,1,n,Y,n+1);
		else tree.upd(1,1,n,Y,tx[Y][totx[Y]]);
	}
	int YY=sy.query2(1,1,n,x.x),XX=sx.query2(1,1,n,x.y);
	int X=tr2_x.query(1,1,n,XX-1,x.x),TY=sx.query1(1,1,n,XX-1)-1,Y=tr2_y.query(1,1,n,x.y+1,TY)+dx.query(1,1,n,XX-1);
	tr2_x.upd2(1,1,n,XX-1,x.x);
	tr2_x.upd(1,1,n,x.x,X-Y);
	tr2_x.upd(1,1,n,XX-1,Y);
	sx.upd(1,1,n,XX,x.x,x.y);
	sy.upd(1,1,n,YY,x.y,x.x);
	if(X1==x.x||Y1==x.y)return;
	dx.upd(1,1,n,XX,x.x,1);
	dx.upd(1,1,n,x.x,x.x,tr2_y.query(1,1,n,x.y,x.y));
}
int qry(Qr x){
	int XX=sy.query1(1,1,n,x.Y),YY=sx.query1(1,1,n,x.X);
	if((XX>=x.X||YY>=x.Y)&&(XX!=x.X||YY!=x.Y))return n;
	int ANS=0;
	ANS=tr_x.query(1,1,n,1,x.X)+tr_y.query(1,1,n,1,x.Y);
	ANS+=tr2_x.query(1,1,n,1,x.X)+tr2_y.query(1,1,n,1,x.Y);
	ANS+=x.ans1;
	return ANS;
}

signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%d%d",&a[i].x,&a[i].y),tr_x.upd(1,1,n,a[i].x,1),tr_y.upd(1,1,n,a[i].y,1);
	sort(a+1,a+n+1,cmp1);
	for(int i=1;i<=n;++i)tx[a[i].x].push_back(a[i].y);
	for(int i=1;i<=n;++i){
		if(totx[i]==tx[i].size())tree.upd(1,1,n,i,n+1);
		else tree.upd(1,1,n,i,tx[i][0]);
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d%d%d%d",&q[i].o,&q[i].x,&q[i].y,&q[i].X,&q[i].Y);
		qr[q[i].X].push_back((Qr2){q[i].Y,n,i});
		qr[n+1].push_back((Qr2){q[i].Y,n,i});
	}
	for(int i=1,j=1;i<=n+1;++i){
		int res=-1;if(i==n+1)res=1;
		while(j<=n&&a[j].x<=i){tr1.upd(a[j].y,1),++j;}
		for(int k=0;k<qr[i].size();++k){
			q[qr[i][k].id].ans1+=res*(tr1.qr(qr[i][k].y)-tr1.qr(qr[i][k].x));
		}
	}
	for(int i=1;i<=m;++i){
		if(q[i].o==1)updx(q[i]);
		else updy(q[i]);
		printf("%d\n",qry(q[i])-n);
	}
	return 0;
}
源文件, 语言: C++14

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 7ms
memory: 61524kb

input:

995 996
950 481
376 18
141 776
711 966
130 727
468 529
47 39
857 563
832 821
776 472
154 914
825 279
332 415
470 361
968 440
45 560
299 755
703 785
744 387
547 382
3 549
344 573
778 424
784 765
280 115
251 434
695 98
463 506
379 38
610 486
305 623
703 244
856 365
117 360
772 847
331 723
663 991
900 ...

output:

423
473
758
313
694
232
333
784
821
154
247
244
504
54
200
370
872
782
734
174
660
467
76
754
77
3
144
974
526
415
439
694
507
577
258
120
243
3
2
319
313
498
218
828
433
623
981
700
120
55
70
499
375
283
387
128
317
139
220
410
22
547
3
385
430
168
32
0
178
625
677
561
488
672
577
64
144
537
235
54...

result:

wrong answer 830th numbers differ - expected: '427', found: '0'

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 2930ms
memory: 249184kb

input:

999996 999996
921339 140126
955508 363759
958698 342406
280137 955674
907511 75721
189876 946586
152058 168837
541857 557702
84498 865987
185574 809224
704828 701026
815379 548000
989515 518951
335439 336866
745570 790616
766723 212893
926629 859003
51261 40866
592510 556235
324926 700261
320946 798...

output:

0
0
953730
0
0
512663
0
0
0
0
407467
0
0
0
0
420
0
0
0
0
0
0
513245
0
0
0
0
0
0
0
0
0
0
0
11756
0
0
7822
0
0
0
0
22726
0
0
0
8233
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
13818
349438
0
0
0
0
0
0
6803
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8602
0
0
0
0
0
0
0
15717
0
0
0
0
0
0
0
0
0
0...

result:

wrong answer 955989th numbers differ - expected: '7', found: '0'

Subtask #3:

score: 0
Time Limit Exceeded

Test #17:

score: 0
Time Limit Exceeded

input:

999995 999997
261379 334440
985281 986034
549380 718157
670003 253925
533027 437989
326806 983213
965935 756259
229069 686789
331338 684961
957559 390618
937820 959719
338153 779814
582581 965418
634156 421264
308778 938878
913059 390904
481477 431492
739774 793015
901442 934600
256704 991485
366691...

output:

160635
633543
123519
313576
450015
383636
574186
2373
203701
326075
117994
567275
652824
199778
380317
380374
105875
373857
788346
703176
609801
648161
367059
497975
57979
478851
745054
75935
543062
251837
769828
436489
480966
235835
509625
757188
763486
396842
262680
2240
267171
165787
558963
16523...

result:

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

伺服器時間: 2024-12-01 00:28:47 | 開源專案