QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#100379#4236. Triangular Logslgvc#WA 89ms49572kbC++233.5kb2023-04-25 19:04:062023-04-25 19:04:10

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-25 19:04:10]
  • 评测
  • 测评结果:WA
  • 用时:89ms
  • 内存:49572kb
  • [2023-04-25 19:04:06]
  • 提交

answer

//这回只花了114514min就打完了。
//真好。记得多手造几组。
#include <bits/stdc++.h>
//#define int long long
#define pai 3.141592653589793238462643383279502884197169399375105820
#define MOD 1000000007
#define eps 0.00000001
inline int min(int a,int b) {return a<b?a:b;}
inline int max(int a,int b) {return a>b?a:b;}
#define ULL unsigned long long
#define LL long long
#define INF 0x3f3f3f3f
#define INF_LL 0x3f3f3f3f3f3f3f3f
static char buf[1000000],*paa=buf,*pd=buf;
static char buf2[1000000],*pp=buf2;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline void pc(char ch){
	if(pp-buf2==1000000) fwrite(buf2,1,1000000,stdout),pp=buf2;
	*pp++=ch;
}
inline void pcc(){
	fwrite(buf2,1,pp-buf2,stdout);
	pp=buf2;
}
inline int read(void) {
	int w=1;
	register int x(0);register char c(getchar());
	while(c<'0'||c>'9') {if(c=='-') w=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w*x;
}
void write(int x) {
	if(x<0) pc('-'),x=-x;
	static int sta[20];
	int top=0;
	do {
		sta[top++]=x%10,x/=10;
	} while(x);
	while(top) pc(sta[--top]+48);
}
void we(int x) {
	write(x);
	pc('\n');
}
inline bool cmp_xi(int a,int b) {return a<b;}
inline bool cmp_da(int a,int b) {return a>b;}
int N,Q,tt[100009],rt[100009],t[109],as[109],ak[109],qd,kq,ls[4000009],rs[4000009],seg[4000009],kd;
struct n_t{
	int x,y,h;
} a[100009];
struct m_t{
	int x,h;
};
inline bool cmp(n_t m,n_t n) {return m.x<n.x;}
inline bool cmpp(m_t m,m_t n) {return m.x<n.x;}
std::vector<m_t> p[100009];
#define md ((l+r)>>1)
void up(int n,int& nn,int l,int r,int p) {
	nn=++kd;
	seg[nn]=seg[n]+1;
	if(l==r) return;
	if(p<=md) {
		up(ls[n],ls[nn],l,md,p);
		rs[nn]=rs[n];
	} else {
		up(rs[n],rs[nn],md+1,r,p);
		ls[nn]=ls[n];
	}
}
int q(int r1,int r2,int l,int r,int L,int R) {
	if(r<L||R<l) return 0;
	if(L<=l&&r<=R) return seg[r2]-seg[r1];
	return q(ls[r1],ls[r2],l,md,L,R)+q(rs[r1],rs[r2],md+1,r,L,R);
}
void q2(int r1,int r2,int l,int r,int L,int R) {
	if(seg[r1]==seg[r2]||r<L||R<l) return;
	if(l==r) {
		t[++kq]=l;
		return;
	}
	q2(ls[r1],ls[r2],l,md,L,R);q2(rs[r1],rs[r2],md+1,r,L,R);
}
#undef md
signed main(void) {
    //freopen("m.in","r",stdin);
    //freopen("m.out","w",stdout);
	N=read();Q=read();
	for(int i=1;i<=N;i++) {
		a[i].x=read();
		a[i].y=read();
		a[i].h=read();
		tt[i]=a[i].y;
	}
	std::sort(a+1,a+N+1,cmp);
	for(int i=1;i<=N;i++) {
		up(rt[i-1],rt[i],1,1000000000,a[i].y); 
	}
	std::sort(tt+1,tt+N+1);
	int k=std::unique(tt+1,tt+N+1)-tt;
	for(int i=1;i<=N;i++) {
		int v=std::lower_bound(tt+1,tt+k+1,a[i].y)-tt-1;
		p[v].push_back((m_t){a[i].x,a[i].h});
	}
	for(int i=1;i<=k;i++) std::sort(p[i].begin(),p[i].end(),cmpp);
	while(Q--) {
		int xl=read(),yl=read(),xr=read(),yr=read();
		int l=0,r=N,md;
		while(l<r) {
			md=(l+r+1)>>1;
			if(a[md].x<xl) l=md;else r=md-1;
		}
		int l2=1,r2=N;
		while(l2<r2) {
			md=(l2+r2+1)>>1;
			if(a[md].x<=xr) l2=md;else r2=md-1;
		}
		if(q(rt[l],rt[l2],1,1000000000,yl,yr)>100) {
			we(0);
			continue;
		}  
		kq=0;
		q2(rt[l],rt[l2],1,1000000000,yl,yr);
		qd=0;
		for(int i=1;i<=kq;i++) {
			int v=std::lower_bound(tt+1,tt+k+1,t[i])-tt-1;
			int l=0,r=p[v].size()-1;
			while(l<r) {
				md=(l+r)>>1;
				if(p[v][md].x>=xl) r=md;else l=md+1;
			}
			while(l<p[v].size()&&p[v][l].x<=xr) {
				ak[++qd]=p[v][l].h;
				l++;
			}
		}
		std::sort(ak+1,ak+qd+1);
		bool zz=0;
		for(int i=1;i+2<=qd;i++) {
			if(ak[i]+ak[i+1]>ak[i+2]) zz=1;
		}
		we(zz);
	}
	pcc();
    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 7920kb

input:

9 5
1 3 3
2 3 1
3 3 4
1 2 1
2 2 5
3 2 9
1 1 2
2 1 6
3 1 5
1 1 1 2
1 1 2 2
1 1 1 3
1 2 3 2
1 1 3 3

output:

0
1
0
0
1

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 8252kb

input:

481 1
8 6788 8975
24 6552 2668
26 7948 4730
40 531 9805
110 1914 1916
164 7073 3371
165 6293 7756
170 9946 2003
179 9654 1700
215 6447 2229
221 3149 3030
242 1999 6843
242 5764 3163
249 3716 8634
250 6801 9317
260 2741 4273
282 5436 4836
284 3951 6483
288 4812 76
375 9004 5492
380 5627 5929
391 6385...

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 0ms
memory: 8868kb

input:

378 1
62730 50925 80731
92666 77280 61521
29236 67032 7889
35986 96802 8763
13313 49918 83582
51842 66775 47834
2286 12925 41106
39790 6698 15243
65145 56379 68496
35570 809 525
39834 16723 48002
77230 16273 16032
52615 7621 77300
92267 82517 39917
13170 89084 77751
45638 23868 49631
7758 71381 5191...

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 86ms
memory: 48060kb

input:

100000 100000
299999993 206450345 26023928
334281171 300000008 18107965
318653732 299999990 82338399
299999997 393028366 37212808
299999992 208114125 82126189
300000002 303613195 34463905
270033576 299999993 49200970
300000003 249755524 5829381
300000003 367329175 12867359
300000009 337452692 131045...

output:

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
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
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
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
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
...

result:

ok 100000 lines

Test #5:

score: -100
Wrong Answer
time: 89ms
memory: 49572kb

input:

100000 100000
299999990 299999990 40343876
299999990 299999991 75128878
299999990 299999992 54630219
299999990 299999993 2733654
299999990 299999994 46236519
299999990 299999995 98430004
299999990 299999996 48355189
299999990 299999997 85287882
299999990 299999998 83938086
299999990 299999999 739070...

output:

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
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
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
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
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
...

result:

wrong answer 1st lines differ - expected: '1', found: '0'