Submission #2943901

Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair


ll solve(int N,int M,vector<string>& s) {
    // vvi aH(N+1, vi(M+1, 0)), aV(M+1, vi(N+1, 0));
    // rep(r,N) rep(c,M) {
    //     if (s[r][c] == '#') {
    //         ++aH[1+r][1+c]; ++aV[1+c][1+c];
    //     }
    // }
    vvi aH(N+1, vi(M+1, 0)), aV(M+1, vi(N+1, 0));
    rep(r,N){
        rep(c,M) {
            aH[r][c+1] = aH[r][c] + (s[r][c]=='#');
        }
#ifdef DEBUG
        cerr << aH[r] << endl;
#endif
    }
#ifdef DEBUG
    cerr << "-" << endl;
#endif
    rep(c,M){
        rep(r,N) {
            aV[c][r+1] = aV[c][r] + (s[r][c]=='#');
        }
#ifdef DEBUG
        cerr << aV[c] << endl;
#endif
    }

    ll ans = 0LL;
    int left, right, up, down;
    rep(r,N) rep(c,M) {
        if (s[r][c] == '#') continue;
        left = right = up = down = 0;

        {
            int hcurr = aH[r][1+c];
            int lx = lower_bound(ALL(aH[r]), hcurr) - aH[r].begin();
            int rx = upper_bound(ALL(aH[r]), hcurr) - aH[r].begin();
            left = (1+c) - lx - 1;
            right = rx - (1+c) - 1;
        }

        {
            int vcurr = aV[c][1+r];
            int lx = lower_bound(ALL(aV[c]), vcurr) - aV[c].begin();
            int rx = upper_bound(ALL(aV[c]), vcurr) - aV[c].begin();
            up = (1+r) - lx - 1;
            down = rx - (1+r) - 1;
        }

        ans += left*up + left*down + right*up + right*down;
#ifdef DEBUG
        fprintf(stderr,"[%d][%d] %d %d | %d %d\n", r,c, left,right, up,down);
#endif
    }
    return ans;
}

int main() {
    int N,M; cin >> N >> M;
    vector<string> s(N);
    rep(i,N) cin >> s[i];
    cout << solve(N,M,s) << endl;
    return 0;
}

Submission Info

Submission Time
Task C - 右折
User naoya_t
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2912 Byte
Status
Exec Time 971 ms
Memory 37760 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 400 / 400 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 531 ms 35712 KB
02.txt 532 ms 35712 KB
03.txt 531 ms 35712 KB
04.txt 530 ms 35712 KB
05.txt 721 ms 35712 KB
06.txt 721 ms 35712 KB
07.txt 721 ms 35712 KB
08.txt 722 ms 35712 KB
09.txt 971 ms 35712 KB
10.txt 970 ms 35712 KB
11.txt 967 ms 35712 KB
12.txt 968 ms 35712 KB
13.txt 272 ms 35712 KB
14.txt 273 ms 35712 KB
15.txt 507 ms 35840 KB
16.txt 502 ms 35712 KB
17.txt 188 ms 35712 KB
18.txt 188 ms 35712 KB
19.txt 488 ms 35712 KB
20.txt 490 ms 35712 KB
21.txt 696 ms 35712 KB
22.txt 695 ms 37760 KB
23.txt 691 ms 35712 KB
24.txt 692 ms 35712 KB
25.txt 787 ms 35712 KB
26.txt 776 ms 35712 KB
27.txt 777 ms 35712 KB
28.txt 775 ms 35712 KB
29.txt 1 ms 256 KB
30.txt 1 ms 256 KB
31.txt 1 ms 256 KB
32.txt 1 ms 256 KB
33.txt 1 ms 256 KB
34.txt 1 ms 256 KB
35.txt 1 ms 256 KB
36.txt 1 ms 256 KB
s1.txt 1 ms 256 KB
s2.txt 1 ms 256 KB
s3.txt 1 ms 256 KB