QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#503980#5414. Stop, Yesterday Please No MorevwxyzTL 15ms10636kbPython32.6kb2024-08-04 03:37:062024-08-04 03:37:07

Judging History

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

  • [2024-08-04 03:37:07]
  • 评测
  • 测评结果:TL
  • 用时:15ms
  • 内存:10636kb
  • [2024-08-04 03:37:06]
  • 提交

answer

class Cumsum2:
    def __init__(self,lst,mod=0):
        self.H=len(lst)
        self.W=len(lst[0]) if lst else 0
        self.cumsum2=[[0]*(self.W+1) for i in range(self.H+1)]
        for i in range(1,self.H+1):
            for j in range(1,self.W+1):
                self.cumsum2[i][j]=lst[i-1][j-1]
        self.mod=mod
        for i in range(self.H+1):
            for j in range(1,self.W+1):
                self.cumsum2[i][j]+=self.cumsum2[i][j-1]
                if self.mod:
                    self.cumsum2[i][j]%=self.mod
        for i in range(1,self.H+1):
            for j in range(self.W+1):
                self.cumsum2[i][j]+=self.cumsum2[i-1][j]
                if self.mod:
                    self.cumsum2[i][j]%=self.mod

    def __getitem__(self,tpl):
        ab,cd=tpl
        def make_slice(ij,N):
            if type(ij)==int:
                i,j=ij,ij+1
            else:
                i,j=ij.start,ij.stop
                if i==None:
                    i=0
                elif i<-N or N<i:
                    raise IndexError("list index out of range")
                elif -N<=i<0:
                    i+=N
                if j==None:
                    j=N
                elif j<-N or N<j:
                    raise IndexError("list index out of range")
                elif -N<=j<0:
                    j+=N
            return i,j
        a,b=make_slice(ab,self.H)
        c,d=make_slice(cd,self.W)
        retu=self.cumsum2[b][d]+self.cumsum2[a][c]-self.cumsum2[a][d]-self.cumsum2[b][c]
        if self.mod:
            retu%=self.mod
        return retu

    def __str__(self):
        return str(self.cumsum2)

T=int(input())
for t in range(T):
    N,M,K=map(int,input().split())
    S=input()
    le=len(S)
    x0,x1=0,N
    y0,y1=0,M
    x,y=0,0
    X,Y=[x],[y]
    for s in S:
        if s=="U":
            x-=1
        elif s=="D":
            x+=1
        elif s=="R":
            y-=1
        else:
            y+=1
        x0=max(x0,x)
        x1=min(x1,N+x)
        y0=max(y0,y)
        y1=min(y1,M+y)
        X.append(x)
        Y.append(y)
    x1=max(x1,x0)
    y1=max(y1,y0)
    minX=min(X)
    minY=min(Y)
    for i in range(le+1):
        X[i]-=minX
        Y[i]-=minY
    leX=max(X)+1
    leY=max(Y)+1
    C=[[0]*leY for x in range(leX)]
    for x,y in zip(X,Y):
        C[x][y]=1
    C=Cumsum2(C)
    ans=0
    for x in range(N):
        for y in range(M):
            dx,dy=x-X[0],y-Y[0]
            if (x1-x0)*(y1-y0)==K+C[min(leX,max(0,x0-dx)):min(leX,x1-dx),min(leY,max(0,y0-dy)):min(leY,y1-dy)]:
                ans+=1
    print(ans)

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 15ms
memory: 10636kb

input:

3
4 5 3
ULDDRR
4 5 0
UUUUUUU
4 5 10
UUUUUUU

output:

2
20
0

result:

ok 3 number(s): "2 20 0"

Test #2:

score: -100
Time Limit Exceeded

input:

1060
19 12 0
UDLDDUUUUDDDLLRDUDUURULUUUDRDUDRDRLRLRLULULLLDLDDRLUUUURUUUDDRLLRUUUDULURUULLRDRLRDDURDUUURRRLURLRUULRRUDURDLUUURDLURDDLUUURDDRLLURRDLRUDLRDRLLRRDRDDLDRURRRLUDULLLRUUDLRRURRDLLRRRDLLRDDDLRLRURURDDDL
11 1 0
UR
3 18 33
UDRLR
17 11 132
RLDRDLDRUU
6 10 13
UULUDDLRDLUUDLDD
1 15 0
D
6 20 50
D...

output:

228
11
20
99
18
15
34
240
15
0
0
13
14
18
26
16
1
19
108
8
2
2
3
7
0
30
16
21
0
8
10
9
15
5
320
11
7
3
0
0
12
0
11
0
0
14
0
22
36
51
23
7
6
4
2
48
28
8
63
22
49
13
10
4
108
10
18
44
0
15
9
0
4
30
14
99
105
10
14
17
0
66
10
11
28
52
34
56
33
14
56
90
14
0
121
3
48
30
36
13
0
30
7
8
3
11
16
45
20
34
0...

result: