QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#782496#5414. Stop, Yesterday Please No Morexcxc82AC ✓113ms17780kbC++143.1kb2024-11-25 20:15:302024-11-25 20:15:30

Judging History

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

  • [2024-11-25 20:15:30]
  • 评测
  • 测评结果：AC
  • 用时：113ms
  • 内存：17780kb
查看
  • [2024-11-25 20:15:30]
  • 提交

answer

#include<bits/stdc++.h>
#define raed read
using namespace std;
const int MAXN = 1010,INF = 0x3f3f3f3f,mod = 1e9+7;
const double eps = 0.0001;
inline int read(){
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;return ~(X-1);
}
int n,m,k,T,a[MAXN][MAXN];
int sum[MAXN][MAXN];
void Modify(int x1,int y1,int x2,int y2,int v){
	sum[x1][y1]+=v;
	sum[x2+1][y1]-=v;
	sum[x1][y2+1]-=v;
	sum[x2+1][y2+1]+=v;
}
unsigned long long M(unsigned long long a,unsigned long long b,unsigned long long c,unsigned long long d){
	unsigned long long now = 0;
	now = now*13331+a;
	now = now*13331+b;
	now = now*13331+c;
	now = now*13331+d;
	return now;
}
string s;
signed main(){
	T = read();
	while(T--){
		cin>>n>>m>>k;
		for(int i=0;i<=n;i++){
			for(int j=0;j<=m;j++){
				a[i][j] = 1;
				sum[i][j] = 0;
			}
		} 
		cin>>s;
		int MAXx = 0,MAXy = 0,MINx = 0,MINy = 0,nowx = 0,nowy = 0;
		int Stx = 0,Sty = 0,Edx = 0,Edy = 0;
		for(int i=0;i<s.length();i++){
			if(s[i]=='L') nowy--;
			if(s[i]=='R') nowy++;
			if(s[i]=='U') nowx--;
			if(s[i]=='D') nowx++;
			MAXx = max(MAXx,nowx);
			MINx = min(MINx,nowx);
			MAXy = max(MAXy,nowy);
			MINy = min(MINy,nowy);
		}
		int cnt = n*m;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(i+MAXx>n||i+MINx<1||j+MAXy>m||j+MINy<1) a[i][j] = 0,cnt--;
			}
		}
		if(cnt<k){
			cout<<0<<endl;
			continue;
		}
		k = cnt-k;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(a[i][j]){
					if(!Stx) Stx = i,Sty = j;
					Edx = i,Edy = j;
				}
			}
		}
		if(Stx){
			map<unsigned long long,int> mp;
			mp[M(Stx,Sty,Edx,Edy)] = 1;
			Modify(Stx,Sty,Edx,Edy,1);
			for(int i=0;i<s.length();i++){
				if(s[i]=='L'){
					Sty--;
					Edy--;
					if(mp[M(Stx,Sty,Edx,Edy)]) continue;
					mp[M(Stx,Sty,Edx,Edy)] = 1;
					Modify(Stx,Sty,Edx,Edy,1);
				}
				if(s[i]=='R'){
					Sty++;
					Edy++;
					if(mp[M(Stx,Sty,Edx,Edy)]) continue;
					mp[M(Stx,Sty,Edx,Edy)] = 1;
					Modify(Stx,Sty,Edx,Edy,1);
				}
				if(s[i]=='U'){
					Stx--;
					Edx--;
					if(mp[M(Stx,Sty,Edx,Edy)]) continue;
					mp[M(Stx,Sty,Edx,Edy)] = 1;
					Modify(Stx,Sty,Edx,Edy,1);
				}
				if(s[i]=='D'){
					Stx++;
					Edx++;
					if(mp[M(Stx,Sty,Edx,Edy)]) continue;
					mp[M(Stx,Sty,Edx,Edy)] = 1;
					Modify(Stx,Sty,Edx,Edy,1);
				}
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+sum[i][j];
			}
		}
		int ans = 0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(sum[i][j]==k) ans++;
			}
		}
		/*for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cout<<sum[i][j]<<" ";
			}
			cout<<endl;
		}*/
		cout<<ans<<endl;
	}
}
/*
1060
19 12 0
UDLDDUUUUDDDLLRDUDUURULUUUDRDUDRDRLRLRLULULLLDLDDRLUUUURUUUDDRLLRUUUDULURUULLRDRLRDDURDUUURRRLURLRUULRRUDURDLUUURDLURDDLUUURDDRLLURRDLRUDLRDRLLRRDRDDLDRURRRLUDULLLRUUDLRRURRDLLRRRDLLRDDDLRLRURURDDDL
11 1 0
UR
3 18 33
UDRLR
17 11 132
RLDRDLDRUU

1
3 18 33
UDRLR
*/
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5636kb

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: 0
Accepted
time: 6ms
memory: 6080kb

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:

ok 1060 numbers

Test #3:

score: 0
Accepted
time: 5ms
memory: 11764kb

input:

1
1000 1000 979065
DDUULULUDULLULLDLUULURRLDURLRDLRRUURUUUDLRLUUDUUDUDLLDDDULU

output:

958416

result:

ok 1 number(s): "958416"

Test #4:

score: 0
Accepted
time: 5ms
memory: 11792kb

input:

1
1000 1000 943471
LRLDLURLDLRDRDUULULRDDLLRURDUURLLDDLDLDDLLLUUURLDRUDRLLUUUUUDLUUDLURURRDLRLRRRLULRRULURLRRDLDRLUDRRLDDLUDRRLLUDLLLRDULRRRRLDUUDRDLULUUUUDRRDULUDLLUUDLDURDRRLRRLDRLDDRURURLUULRRLDLLRLRDRRUULDLDLULLDLLRULLRUULURDURRLUUDUULLULDLRUDDLRLRLLUDDDLLLUDRRLDDULRRURRDURDDRDLLULRLULURLRDLLURD...

output:

889224

result:

ok 1 number(s): "889224"

Test #5:

score: 0
Accepted
time: 113ms
memory: 17780kb

input:

1
1000 1000 315808
LLRURURRDDDULLDDUDRDLRLLLDDDLUDRDURLDULRLRULUUDLUULUUDULLLLDDURLDUULUUDLLDLLDRUDUULRLLRLRUURLRLULLDDLLDUDLLRUUDRLDLUULDLLDRRRURDULLDRRRDURURDRLDURURUDLURLDURRLRRUDUDURDRLRRRDLRRURLURUDRRLDLRULLDLUURDURLURLLRDLRDRUURURDRUDUUUDLRRLUDLUUDUDDRRDUULUUDDRLLULDUUDRURRDRLULRLULDURLURUDLLD...

output:

426

result:

ok 1 number(s): "426"

Test #6:

score: 0
Accepted
time: 2ms
memory: 11528kb

input:

1
1000 1000 986018
LLULDRRRDDURRUDRUURRRDDLUUDUULRULRDULLD

output:

972180

result:

ok 1 number(s): "972180"

Test #7:

score: 0
Accepted
time: 2ms
memory: 11784kb

input:

1
1000 1000 945431
DDRRURUUDLDULLDLDDLRULDLLDDRRLUDRLUURRLDRDLURUURRRRLRURLURULLLDRDDDRRRLDLDRLRDDUURRURDDDLRUURLUURLRDUDDDLLDUURLDLUDLLRRDUUDRLUULLUULDLURRUDLUURLRLRURDUDRRRDRLRUDLLLLURLULRLRLRRDDUDLRLDUUUULUDLLURRLURRDLRURRRULDDLLLRLRDLUDLLDDRULDUULRDDUUDDUDLURDULLDUDDLULRULDRLDDULDULLUDLULUDRURRR...

output:

893000

result:

ok 1 number(s): "893000"

Test #8:

score: 0
Accepted
time: 89ms
memory: 14664kb

input:

1
1000 1000 460035
RDDUURDULDDLDDLDDLDRRULLRLUURLURRRDRUDDDRDLDLDULUDLRLLRRLRRURRRDLRLUDRDURULDRRDDDDDDLRLDULUULDUDRLLUUUURUUDRURLRRULDRDRUUUUULULRURDDRLRULLLRDRRULUDDUDDLLLRDRUULUUDDRLURDLDURRDLRRLDRRUDLUULRDLURULLDLRLLDDURDUDLDULDLLRULRDLRLUULLUDRUDDDLRRDULULLRUURLUURRLLLLRLDRURLLRLDRRDDDRLUUUUDUL...

output:

417

result:

ok 1 number(s): "417"

Test #9:

score: 0
Accepted
time: 5ms
memory: 11732kb

input:

1
1000 1000 992010
LLLLLDLDRRLUDRR

output:

1999

result:

ok 1 number(s): "1999"

Test #10:

score: 0
Accepted
time: 5ms
memory: 11552kb

input:

1
1000 1000 919600
LLDLRUDRLURRUDRDRRDLRUDLRRRUUULDLDURDDDRUURRRLLURULDRLRLULLULDRULULRLRRRURLDDDRUUULUDLLLLRRLLRDDRDULUDLRLRLDRLUDUDURRULUULLDULUULDLLDRDULUDLDULDDUULDDRRURDRDULRRLDRRDUURURRLUUUDRRLDRRDDLULRDDLDLLRLRLLLRULUUUURRRLDLRUDRRLRURDRLDULLLUDRULLDLDRRUUDLRRLLRLDDLUDLRLRRURUUDUULUDURDURRLUU...

output:

944

result:

ok 1 number(s): "944"

Test #11:

score: 0
Accepted
time: 84ms
memory: 13296kb

input:

1
1000 1000 804351
DLRLDLLLLUDRDURRLDDRRLRUULURURDDDRDLRUDDULRRLLULURDRUUDRURRLURRRDRURRDRLULRDLRRDRRDDUDLUDLDULRUURRLRUUDRLDDRDDUUDULUULUUUDLRURULLRDUUDDDRRLDRUDDUUDRURLRDRUDLRLDDRRLLRLRDUDDULLULRLLDDUDDDUULDULLRRULULDUUULUDRRDRLUDLRRDDUDLRRDDLDLDRUULRRRRRLRLULLRDDRDDDULDRRURUDDLURLRLURLRDRULUDULUU...

output:

640000

result:

ok 1 number(s): "640000"
English 繁體中文 简体中文

Server Time: 2024-12-02 18:03:52 | OpenSource Project