QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#721761#5414. Stop, Yesterday Please No MoreMitsubachiAC ✓98ms13696kbC++142.5kb2024-11-07 16:46:512024-11-07 16:46:52

Judging History

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

  • [2024-11-07 16:46:52]
  • 评测
  • 测评结果:AC
  • 用时:98ms
  • 内存:13696kb
  • [2024-11-07 16:46:51]
  • 提交

answer

//g++-13 1.cpp -std=c++17 -O2 -I .
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
 
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vst = vector<string>;
using vvst = vector<vst>;
 
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define pq_big(T) priority_queue<T,vector<T>,less<T>>
#define pq_small(T) priority_queue<T,vector<T>,greater<T>>
#define all(a) a.begin(),a.end()
#define rep(i,start,end) for(ll i=start;i<(ll)(end);i++)
#define per(i,start,end) for(ll i=start;i>=(ll)(end);i--)
#define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end())

random_device seed;
mt19937_64 randint(seed());

ll grr(ll mi, ll ma) { // [mi, ma)
    return mi + randint() % (ma - mi);
}

string dir = "UDLR";

vi dx = {-1,1,0,0};
vi dy = {0,0,-1,1};

void solve(){
  int n,m,k;cin>>n>>m>>k;
  string s;cin>>s;
  vvi im((n+1),vi(m+1,0));

  int dxl=0,dxr=0,dyl=0,dyr=0;
  {
    int x=0,y=0;
    rep(i,0,s.size()){
      rep(j,0,4){
        if(s[i]==dir[j]){
          x+=dx[j];y+=dy[j];
        }
      }
      dxl=min(dxl,x);
      dxr=max(dxr,x);
      dyl=min(dyl,y);
      dyr=max(dyr,y);
    }
  }

  int sxl=-dxl,sxr=n-1-dxr,syl=-dyl,syr=m-1-dyr;
  int area=(sxr-sxl+1)*(syr-syl+1);
  if(sxl>sxr||syl>syr){
    if(k==0){
      cout<<n*m<<"\n";
    }
    else{
      cout<<0<<"\n";
    }
    return;
  }

  map<pair<int,int>,int> mp;

  auto sub=[&](int x,int y){
    im[sxl+x][syl+y]++;
    im[sxl+x][syr+y+1]--;
    im[sxr+x+1][syl+y]--;
    im[sxr+x+1][syr+y+1]++;
    mp[{x,y}]=1;
  };

  sub(0,0);

  {
    int x=0,y=0;
    rep(i,0,s.size()){
      rep(j,0,4){
        if(s[i]==dir[j]){
          x+=dx[j];y+=dy[j];
        }
      }
      if(mp[{x,y}]==0){
        sub(x,y);
      }
    }
  }

  rep(i,0,n+1){
    rep(j,1,m+1){
      im[i][j]+=im[i][j-1];
    }
  }
  
  rep(i,1,n+1){
    rep(j,0,m+1){
      im[i][j]+=im[i-1][j];
    }
  }

  int ans=0;
  rep(i,0,n){
    rep(j,0,m){
      if(im[i][j]+k==area)ans++;
    }
  }
  cout<<ans<<endl;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t;cin>>t;
  while(t--){
    solve();
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 7ms
memory: 3684kb

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: 0ms
memory: 7004kb

input:

1
1000 1000 979065
DDUULULUDULLULLDLUULURRLDURLRDLRRUURUUUDLRLUUDUUDUDLLDDDULU

output:

958416

result:

ok 1 number(s): "958416"

Test #4:

score: 0
Accepted
time: 0ms
memory: 7512kb

input:

1
1000 1000 943471
LRLDLURLDLRDRDUULULRDDLLRURDUURLLDDLDLDDLLLUUURLDRUDRLLUUUUUDLUUDLURURRDLRLRRRLULRRULURLRRDLDRLUDRRLDDLUDRRLLUDLLLRDULRRRRLDUUDRDLULUUUUDRRDULUDLLUUDLDURDRRLRRLDRLDDRURURLUULRRLDLLRLRDRRUULDLDLULLDLLRULLRUULURDURRLUUDUULLULDLRUDDLRLRLLUDDDLLLUDRRLDDULRRURRDURDDRDLLULRLULURLRDLLURD...

output:

889224

result:

ok 1 number(s): "889224"

Test #5:

score: 0
Accepted
time: 98ms
memory: 13696kb

input:

1
1000 1000 315808
LLRURURRDDDULLDDUDRDLRLLLDDDLUDRDURLDULRLRULUUDLUULUUDULLLLDDURLDUULUUDLLDLLDRUDUULRLLRLRUURLRLULLDDLLDUDLLRUUDRLDLUULDLLDRRRURDULLDRRRDURURDRLDURURUDLURLDURRLRRUDUDURDRLRRRDLRRURLURUDRRLDLRULLDLUURDURLURLLRDLRDRUURURDRUDUUUDLRRLUDLUUDUDDRRDUULUUDDRLLULDUUDRURRDRLULRLULDURLURUDLLD...

output:

426

result:

ok 1 number(s): "426"

Test #6:

score: 0
Accepted
time: 0ms
memory: 7024kb

input:

1
1000 1000 986018
LLULDRRRDDURRUDRUURRRDDLUUDUULRULRDULLD

output:

972180

result:

ok 1 number(s): "972180"

Test #7:

score: 0
Accepted
time: 0ms
memory: 6984kb

input:

1
1000 1000 945431
DDRRURUUDLDULLDLDDLRULDLLDDRRLUDRLUURRLDRDLURUURRRRLRURLURULLLDRDDDRRRLDLDRLRDDUURRURDDDLRUURLUURLRDUDDDLLDUURLDLUDLLRRDUUDRLUULLUULDLURRUDLUURLRLRURDUDRRRDRLRUDLLLLURLULRLRLRRDDUDLRLDUUUULUDLLURRLURRDLRURRRULDDLLLRLRDLUDLLDDRULDUULRDDUUDDUDLURDULLDUDDLULRULDRLDDULDULLUDLULUDRURRR...

output:

893000

result:

ok 1 number(s): "893000"

Test #8:

score: 0
Accepted
time: 90ms
memory: 10712kb

input:

1
1000 1000 460035
RDDUURDULDDLDDLDDLDRRULLRLUURLURRRDRUDDDRDLDLDULUDLRLLRRLRRURRRDLRLUDRDURULDRRDDDDDDLRLDULUULDUDRLLUUUURUUDRURLRRULDRDRUUUUULULRURDDRLRULLLRDRRULUDDUDDLLLRDRUULUUDDRLURDLDURRDLRRLDRRUDLUULRDLURULLDLRLLDDURDUDLDULDLLRULRDLRLUULLUDRUDDDLRRDULULLRUURLUURRLLLLRLDRURLLRLDRRDDDRLUUUUDUL...

output:

417

result:

ok 1 number(s): "417"

Test #9:

score: 0
Accepted
time: 0ms
memory: 7028kb

input:

1
1000 1000 992010
LLLLLDLDRRLUDRR

output:

1999

result:

ok 1 number(s): "1999"

Test #10:

score: 0
Accepted
time: 3ms
memory: 7068kb

input:

1
1000 1000 919600
LLDLRUDRLURRUDRDRRDLRUDLRRRUUULDLDURDDDRUURRRLLURULDRLRLULLULDRULULRLRRRURLDDDRUUULUDLLLLRRLLRDDRDULUDLRLRLDRLUDUDURRULUULLDULUULDLLDRDULUDLDULDDUULDDRRURDRDULRRLDRRDUURURRLUUUDRRLDRRDDLULRDDLDLLRLRLLLRULUUUURRRLDLRUDRRLRURDRLDULLLUDRULLDLDRRUUDLRRLLRLDDLUDLRLRRURUUDUULUDURDURRLUU...

output:

944

result:

ok 1 number(s): "944"

Test #11:

score: 0
Accepted
time: 74ms
memory: 8352kb

input:

1
1000 1000 804351
DLRLDLLLLUDRDURRLDDRRLRUULURURDDDRDLRUDDULRRLLULURDRUUDRURRLURRRDRURRDRLULRDLRRDRRDDUDLUDLDULRUURRLRUUDRLDDRDDUUDULUULUUUDLRURULLRDUUDDDRRLDRUDDUUDRURLRDRUDLRLDDRRLLRLRDUDDULLULRLLDDUDDDUULDULLRRULULDUUULUDRRDRLUDLRRDDUDLRRDDLDLDRUULRRRRRLRLULLRDDRDDDULDRRURUDDLURLRLURLRDRULUDULUU...

output:

640000

result:

ok 1 number(s): "640000"