Submission #330573

---

Source Code Expand

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

const int kM = 1002, kQ = 1002;

typedef long long ll;
typedef pair<ll,ll> P;

ll N, M;
ll A[kM], B[kM], C[kM];

ll Q;
ll D[kQ], E[kQ], F[kQ];

struct Rect {
  ll lx, ly, width, height;
  ll value;

  bool operator<(const Rect& other) const {
    return value < other.value;
  }
};

ll rect_lattice_point(const Rect& r, const Rect& ref) {
  ll temp = 0;

  ll edge_lesser = min(ref.width, ref.height);
  ll edge_greater = max(ref.width, ref.height);

  if (r.value < edge_lesser) {
    temp = (r.value + 1) * (r.value + 2) / 2;
  }
  else if (r.value < edge_greater) {
    ll delta = r.value - edge_lesser;
    temp += delta * (edge_lesser + 1);
    temp += (edge_lesser + 1) * (edge_lesser + 2) / 2;
    if (r.value >= ref.width) {
      temp -= 1 + r.value - ref.width;
    }
  }
  else {
    temp = (ref.width + 1) * (ref.height + 1);
    ll delta = r.value - edge_greater;
    temp -= (edge_lesser - delta) * (edge_lesser - delta + 1) / 2;

    if (r.value >= ref.width) {
      temp -= 1 + r.value - ref.width;
    }

  }
  return temp;
}

ll square_lattice_point(const Rect& r, const Rect& ref) {
  ll temp = 0;
  if (r.value < ref.width) {
    temp = (r.value + 1) * (r.value + 2) / 2;
  }
  else {
    if (ref.width == 1) {
      temp = 2;
    }
    else {
      temp = (ref.width + 1) * (ref.width + 2) / 2; // 斜線以外全部
    }
    temp += ref.width + 1; // 斜線
    ll delta = r.value - ref.width;
    temp -= (ref.width - delta) * (ref.width + 1 - delta) / 2;
    temp -= 1 + (r.value - ref.width); // 右端
  }
  return temp;
}

void solve() {
  vector<ll> verts, horis;
  for (int i = 0; i < M; i++) {
    int a = A[i], b = B[i], c = C[i];
    int vert_index = a + (c - 1),
      hori_index = b;
    verts.push_back(vert_index);
    horis.push_back(hori_index);
  }
  for (int i = 0; i < Q; i++) {
    int d = D[i], e = E[i], f = F[i];
    int vert_index = d + (f - 1),
      hori_index = e;
    verts.push_back(vert_index);
    horis.push_back(hori_index);
  }

  verts.push_back(0);
  verts.push_back(1);
  verts.push_back(N + 2);

  horis.push_back(0);
  horis.push_back(1);
  horis.push_back(N + 2);

  sort(verts.begin(), verts.end());
  sort(horis.begin(), horis.end());

  verts.erase(unique(verts.begin(), verts.end()), verts.end());
  horis.erase(unique(horis.begin(), horis.end()), horis.end());

  const int kV = verts.size(), kH = horis.size();
  map<P, Rect> rects;

  // start as 1
  for (int i = 1; i < kV-1; i++) {
    int height = verts[i] - verts[i-1];
    for (int j = 0; j < kH-1; j++) {
      int width = horis[j+1] - horis[j];
      rects[P(verts[i], horis[j])] = (Rect){-1, -1, width, height, -1};
    }
  }

  // foreach(rects, i) {
  //   printf("lx,ly,w,h=%lld,%lld,%lld,%lld\n",
  //     i->first.first, i->first.second,
  //     i->second.width, i->second.height);
  // }

  priority_queue<Rect> PQ;
  // 1. set init x-size
  for (int i = 0; i < M; i++) {
    int v_idx = A[i] + (C[i] - 1);
    int h_idx = B[i];
    PQ.push((Rect){v_idx, h_idx, -1, -1, C[i] - 1});
  }
  while (!PQ.empty()) {
    Rect r = PQ.top(); PQ.pop();
    Rect& ref = rects[P(r.lx, r.ly)];
    if (r.value > ref.value) {
      ref.value = r.value;
      // printf("write as lx,ly,w,h,x=%lld,%lld,%lld,%lld,%lld\n",
      //   r.lx, r.ly, r.value, ref.width, ref.height);
    } else {
      break;
    }

    if (ref.value >= ref.width) {
      PQ.push((Rect){r.lx, *upper_bound(horis.cbegin(), horis.cend(), r.ly),
        -1, -1, ref.value - ref.width});
      //  printf("push(right) lx,ly,x=%lld,%lld,%lld\n", r.lx,
      //  *upper_bound(horis.cbegin(), horis.cend(), r.ly) , ref.value - ref.width);
    }
    if (ref.value > ref.height) {
      vector<ll>::iterator ptr = lower_bound(verts.begin(), verts.end(), r.lx);
      if (*ptr != verts.front()) {
        --ptr;
        PQ.push((Rect){*ptr, r.ly, -1, -1, ref.value - ref.height});
        //printf("push(up) lx,ly,x=%lld,%lld,%lld\n", *ptr, r.ly, ref.value - ref.height);
      }
    }
  }

  // 2. couting
  queue<Rect> wq;
  for (int i = 0; i < Q; i++) {
    int v_idx = D[i] + (F[i] - 1);
    int h_idx = E[i];
    ll ans = 0;
    wq.push((Rect){v_idx, h_idx, -1, -1, F[i] - 1});

    while (!wq.empty()) {
      const Rect& r = wq.front(); wq.pop();
      const Rect& ref = rects[P(r.lx, r.ly)];
      const int x_idx =
        lower_bound(verts.cbegin(), verts.cend(), r.lx) - verts.cbegin();
      // 重複部分の計算
      if (r.value > ref.value) {

        // printf("[]--- cur x,y,w,h,new,old=%lld,%lld,%lld,%lld,%lld,%lld\n",
        //   r.lx, r.ly, ref.width, ref.height, r.value, ref.value);

        ll temp = 0;
        // 正方形
        if (ref.width == ref.height) {
          temp = square_lattice_point(r, ref);
          // printf("(square)by new value=%lld\n", temp);
          if (ref.value != -1) {
            // printf("subtract value=%lld\n", rect_lattice_point(ref, ref));
            temp -= rect_lattice_point(ref, ref);
          }
        }
        // 長方形
        else {
          temp = rect_lattice_point(r, ref);
          // printf("(rect)by new value=%lld\n", temp);
          if (ref.value != -1) {
            // printf("subtract value=%lld\n", rect_lattice_point(ref, ref));
            temp -= rect_lattice_point(ref, ref);
          }
        }

        if (x_idx != 1) {
          if (r.value > ref.height) {
            temp -= r.value - ref.height; // not necessaty plus one
          }
          else if (r.value == ref.height) {
            temp -= 1;
          }
        }

        // printf("lx,ly,w,h,new_x,temp=%lld,%lld,%lld,%lld,%lld,%lld\n",
        //   r.lx, r.ly, ref.width, ref.height, r.value, temp);

        ans += temp;

      } else {
        continue;
      }

      if (r.value >= ref.width) {
        auto itr = upper_bound(horis.cbegin(), horis.cend(), r.ly);
        ll delta = r.value - ref.width;
        // printf("push(right,counting) lx,ly,delta=%lld,%lld,%lld\n",
        //   r.lx, *itr, delta);
        wq.push((Rect){r.lx, *itr, -1, -1, delta});
      }

      if (x_idx != 1 && r.value >= ref.height) {
        auto itr = lower_bound(verts.cbegin(), verts.cend(), r.lx);
        if (*itr != verts.front()) {
          --itr;
          ll delta = r.value - ref.height;
          // printf("push(up,counting) lx,ly,delta=%lld,%lld,%lld\n",
          //   *itr, r.ly, delta);
          wq.push((Rect){*itr, r.ly, -1, -1, delta});
        }
      }
    }
    printf("%lld\n", ans);
  }
}

int main() {
  while (cin >> N >> M) {
    for (int i = 0; i < M; i++) {
      cin >> A[i] >> B[i] >> C[i];
    }
    cin >> Q;
    for (int i = 0; i < Q; i++) {
      cin >> D[i] >> E[i] >> F[i];
    }
    solve();
  }
  return 0;
}

Submission Info

Judge Result