Submission #88406

#	Time	Username	Problem	Language	Result	Execution time	Memory
88406		ltomic	Strah (COCI18_strah)	C++14	110 / 110	676 ms	41552 KiB

strah

#include <cstdio>
#include <vector>
#include <algorithm>

#define sc second
#define fi first

using namespace std;

using llint = long long;
using par = pair<int, int>;

const int MAXNUM = 1e9;
const int MAXN = 2e3+3;
const par MAX = par(-1, 1e9);

char C[MAXN];
int up[MAXN][MAXN];
int n, m;

struct segment_tree {
  vector<par> data;
  int offset;

//  static const par MAX = par(-1, 1e9);

  segment_tree() {}

  segment_tree(int a[], int n) {
    for (offset = 1; offset <= n; offset <<= 1);
    data = vector<par>(2*offset, MAX);

    for (int i = 0; i < n; ++i) data[i+offset] = par(i, a[i]);
    for (int i = offset-1; i > 0; --i) {
      data[i] = merge(data[2*i], data[2*i+1]);
    }
  }

  par merge(const par &l, const par &r) {
    return l.sc < r.sc ? l : r;
  }

  par calc_min(int p, int lo, int hi, const int &qlo, const int &qhi) {
    if (lo >= qhi || hi <= qlo) return MAX;
    if (qlo <= lo && hi <= qhi) return data[p];

    int mid = (lo+hi)/2;
    return merge(calc_min(2*p, lo, mid, qlo, qhi), 
               calc_min(2*p+1, mid, hi, qlo, qhi)
               );
  }
  
  int calc_min(int l, int r) {
    return calc_min(1, 0, offset, l, r).fi;
  }

} t;

llint calc(int l, int _r, int _k, const llint &h) {
  llint r = _r-l, k = _k-l;
//    printf("CALC:%d %d %d %lld (%lld - %lld + %lld) \n", l, _r, _k, h,
//      ((k+1)*((r-1)*r - (k-1)*k))/2, ((r-k)*k*(k+1))/2, (k+1)*(r-k));

  return (((k+1)*((r-1)*r - (k-1)*k))/2 - ((r-k)*k*(k+1))/2 + (k+1)*(r-k)) * (h*(h+1))/2;
}

llint solve_row(int k, int l, int r) {
  if (l == r) return 0;

  int min_ind = t.calc_min(l, r);
//  printf("RED:%d %d %d :: %d, CALC:%lld\n", k, l, r, min_ind, calc(l, r, min_ind, up[k][min_ind]));
  if (min_ind == -1) exit(0);
  return solve_row(k, l, min_ind) + solve_row(k, min_ind+1, r) +
    calc(l, r, min_ind, up[k][min_ind]);
}

llint solve() {
  llint sum = 0;

  for (int i = 0; i < n; ++i) {
    t = segment_tree(up[i], m);
    sum += solve_row(i, 0, m);
  }

  return sum;
}


int main() {
  scanf("%d%d", &n, &m);

  for (int i = 0; i < n; ++i) {
    scanf("%s", C);
    for (int j = 0; j < m; ++j) {
      if (i == 0) up[i][j] = C[j] == '.';
      else up[i][j] = C[j] == '.' ? up[i-1][j]+1 : 0;
    }
  }

  printf("%lld\n", solve());
  return 0;
}

Compilation message (stderr)

strah.cpp: In function 'int main()':
strah.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~
strah.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", C);
     ~~~~~^~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11