QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#625924#5414. Stop, Yesterday Please No Moregates_orzRE 0ms3556kbC++202.6kb2024-10-09 21:45:032024-10-09 21:45:04

Judging History

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

  • [2024-10-09 21:45:04]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3556kb
  • [2024-10-09 21:45:03]
  • 提交

answer

#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;

typedef long long LL;
//#define int LL
#define inl inline
const int N = 3e5 + 10;
const int M = N * 2;
//const int mod=998244353;
const int mod = 1000000007;
const double eps = 1e-8;
//const int mod=1e9+7;
typedef pair<int, int> PII;
//const int INF=0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, m;

void become_faster() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

void solve() {
    int k;
    cin>>n>>m>>k;
    vector<vector<int>>pre(2*n+2,vector<int>(2*m+2,0));
    string s;
    cin>>s;
    int x=0,y=0;
    int x1=1,y1=1;
    int x2=n,y2=m;
    for(auto c:s) {
        if(c=='U')x--;
        if(c=='D')x++;
        if(c=='L')y--;
        if(c=='R')y++;
        if(x<0)x1=max(x1,1-x);
        if(x>0)x2=min(x2,n-x);
        if(y<0)y1=max(y1,1-y);
        if(y>0)y2=min(y2,m-y);
    }
    if(x1>=1&&x1<=n&&y1>=1&&y1<=m&&x2>=1&&x2<=n&&y2>=1&&y2<=m);
    else {
        if(k!=0)cout<<0<<"\n";
        else cout<<n*m<<"\n";
        return;
    }
    map<PII,int>mm;
    int now_x=x1,now_y=y1;
    auto add=[&](int x1,int y1,int x2,int y2,int v) {
        x2=min(n+1,x2);
        y2=min(y2,m+1);
        pre[x1][y1]+=v;
        pre[x2+1][y1]-=v;
        pre[x1][y2+1]-=v;
        pre[x2+1][y2+1]+=v;
    };
    for(auto c:s) {
        if(mm[{now_x,now_y}]!=1) {
            add(now_x,now_y,now_x+(x2-x1),now_y+(y2-y1),1);
        }
        if(c=='U') {
            now_x--;
            now_x=max(1,now_x);
        }
        if(c=='D') {
            now_x++;
            now_x=min(now_x,n);
        }
        if(c=='L') {
            now_y--;
            now_y=max(now_y,1);
        }
        if(c=='R') {
            now_y++;
            now_y=min(now_y,m);
        }
    }
    if(mm[{now_x,now_y}]!=1) {
        add(now_x,now_y,now_x+(x2-x1),now_y+(y2-y1),1);
    }

    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++)pre[i][j]+=pre[i-1][j];
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++)pre[i][j]+=pre[i][j-1];
    }
    /*cerr<<"pre: "<<"\n";
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cerr<<pre[i][j]<<" ";
        }
        cerr<<"\n";
    }*/

    int res=0;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            res+=(pre[i][j]==k);
        }
    }
    cout<<res<<"\n";
}

signed main() {
    become_faster();
    int T = 1;
    //T=read();
    cin>>T;
    //for(int i=1;i<=100;i++)solve(i);
    while (T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Runtime Error

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:


result: