2 solutions

  • 0
    @ 2024-2-5 20:22:42
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 2e5 + 10;
    int n,m,Q,dx[N],dy[N];
    char ch[N];
    ll A[N],B[N];
    ll makep(int xi,int yi){
    	return 2ll * (xi + N) * N + yi + N;
    }
    int getid(ll x){
    	int res = lower_bound(B + 1, B + 1 + m, x) - B;
    	return res;
    }
    int mp[N];
    struct question{
    	int pos,id,sgn;
    	ll point;
    }q[N * 5];
    int ans[N];
    question makeq(int posi,ll pointi,int idi,int sgni){
    	question tmp;
    	tmp.pos = posi;
    	tmp.point = pointi;
    	tmp.id = idi;
    	tmp.sgn = sgni;
    	return tmp;
    }
    bool cmpq(question a,question b){
    	return a.pos < b.pos;
    }
    int main(){
    	scanf("%d",&n);
    	scanf("%s",ch + 1);
    	for(int i = 1; i <= n; i += 1){
    		dx[i] = dx[i - 1];
    		dy[i] = dy[i - 1];
    		if(ch[i] == 'U') dy[i] += 1;
    		else if(ch[i] == 'D') dy[i] -= 1;
    		else if(ch[i] == 'L') dx[i] -= 1;
    		else dx[i] += 1;
    		A[i] = B[i] = makep(dx[i], dy[i]);
    	}
    	A[0] = B[n + 1] = makep(0, 0);
    	sort(B + 1, B + 2 + n);
    	m = unique(B + 1, B + 2 + n) - B - 1;
    	for(int i = 0; i <= n; i += 1)
    		A[i] = getid(A[i]);
    	int cnt = 0;
    	scanf("%d",&Q);
    	for(int i = 1; i <= Q; i += 1){
    		int xi,yi,li,ri;
    		scanf("%d%d%d%d",&li,&ri,&xi,&yi);
    		q[++cnt] = makeq(li - 1,makep(xi,yi),i,1);
    		if(ri > li){
    			int tx = dx[li - 1] + dx[ri] - xi;
    			int ty = dy[li - 1] + dy[ri] - yi;
    			q[++cnt] = makeq(ri - 1, makep(tx, ty), i, 1);
    			q[++cnt] = makeq(li - 1, makep(tx, ty), i, -1);
    		}
    		q[++cnt] = makeq(n, makep(xi,yi), i, 1);
    		q[++cnt] = makeq(ri - 1, makep(xi,yi), i, -1);
    	}
    	sort(q + 1,q + 1 + cnt,cmpq);
    	for(int i = 0,j = 1; i <= n,j <= cnt; i += 1){
    		mp[A[i]] += 1;
    		while(q[j].pos == i && j <= cnt){
    			int res = getid(q[j].point);
    			if(B[res] == q[j].point)
    				ans[q[j].id] += q[j].sgn * mp[res];
    			j += 1;
    		}
    	}
    	for(int i = 1; i <= Q;i += 1)
    		if(ans[i]) printf("YES\n");
    		else printf("NO\n");
    	return 0;
    }
    

    Information

    ID
    306
    Time
    1000ms
    Memory
    512MiB
    Difficulty
    7
    Tags
    (None)
    # Submissions
    40
    Accepted
    9
    Uploaded By