QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#618991#7752. The Only Way to the DestinationlixpML 0ms0kbC++142.1kb2024-10-07 12:30:112024-10-07 12:30:15

Judging History

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

  • [2024-10-07 12:30:15]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-10-07 12:30:11]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
inline int Min(int x,int y) { return x<y?x:y; }
inline int Max(int x,int y) { return x>y?x:y; }
int ans,nm;
struct node {
	int ps,x,y,t;
	bool operator < (const node &x) const {
		return ps<x.ps;
	}
}p[N];
int n,m,k,B[N],cnt,ss;
int fnd(int l,int r,int x) {
	while(l<=r) {
		int mid=(l+r>>1);
		if(B[mid]<x) l=mid+1;
		else if(B[mid]==x) return mid;
		else r=mid-1;
	}
}

struct SGT {
	int tg[N<<5],tot,rt,lc[N<<5],rc[N<<5];
	void add(int p,int l,int r) {
		tg[p]=r-l+1;
	}
	void change(int &p,int l,int r,int x,int y) {
		if(!p) p=++tot;
		if(x<=l && r<=y) { add(p,l,r); return;}
		int mid=l+r>>1;
		if(x<=mid) change(lc[p],l,mid,x,y);
		if(y>mid) change(rc[p],mid+1,r,x,y);
		tg[p]=tg[p<<1]+tg[p<<1|1];
	}
	int ask(int p,int l,int r,int x,int y) {
		if(!p) return 0;
		int ans=0,mid=(l+r)>>1;
		if(x<=l && r<=y) return tg[p];
		if(tg[p]==r-l+1) {
			if(!lc[p]) lc[p]=++tot,tg[tot]=mid-l+1;
			if(!rc[p]) rc[p]=++tot,tg[tot]=r-mid;
		}
		if(x<=mid) ans+=ask(lc[p],l,mid,x,y);
		if(y>mid) ans+=ask(rc[p],mid+1,r,x,y);
		return ans;
	}
}T;

signed main() {
	scanf("%lld%lld%lld",&n,&m,&k); ans=n*(m-1)+m*(n-1);nm=n*m;
	if(n==1 || m==1) {
		cout<<"YES\n";
		return 0;
	}
	for(int i=1;i<=k;i++) {
		scanf("%lld%lld%lld",&p[i].x,&p[i].y,&p[i].ps);
		ans-=3*(p[i].y-p[i].x+1)+1;
		if(p[i].x==1) ans++;
		if(p[i].y==n) ans++;
		if(p[i].ps==1 || p[i].ps==m) ans+=p[i].y-p[i].x+1;
		nm-=p[i].y-p[i].x+1;
//		B[++ss]=p[i].ps-1;B[++ss]=p[i].ps;B[++ss]=p[i].ps+1;
	}
/*	sort(B+1,B+ss+1);
	for(int i=1;i<=ss;i++)
		if(B[i]!=B[i-1]) B[++cnt]=B[i];
	for(int i=1;i<=k;i++) {
		p[i].ps=fnd(1,cnt,p[i].ps);
	}*/
	sort(p+1,p+k+1);
	for(int i=1,nxt=1,pre=0;i<=k;pre=i,i=nxt+1) {
		T.rt=0;nxt=i;
		while(p[i].ps==p[nxt+1].ps) nxt++;
		if(p[pre].ps!=p[i].ps-1) continue;
		for(int j=pre;j<i;j++)
			T.change(T.rt,1,n,p[j].x,p[j].y);
		for(int j=i;j<=nxt;j++)
			ans+=T.ask(T.rt,1,n,p[j].x,p[j].y);
	}
	if(ans==nm-1) cout<<"YES\n";
	else cout<<"NO\n";
	return 0;
}

/*
4 4 3
2 4 2
3 4 3
2 4 4
*/

详细

Test #1:

score: 0
Memory Limit Exceeded

input:

5 3 2
2 5 1
1 4 3

output:


result: