2 solutions
-
0
Guest MOD
-
0
#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