QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#618991 | #7752. The Only Way to the Destination | lixp | ML | 0ms | 0kb | C++14 | 2.1kb | 2024-10-07 12:30:11 | 2024-10-07 12:30:15 |
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Memory Limit Exceeded
input:
5 3 2 2 5 1 1 4 3