結果

問題 No.1997 X Lighting
コンテスト
ユーザー tnakao0123
提出日時 2022-07-03 11:43:03
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 54 ms / 2,000 ms
コード長 1,925 bytes
コンパイル時間 475 ms
コンパイル使用メモリ 46,792 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-29 02:01:03
合計ジャッジ時間 2,852 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 1997.cc:  No.1997 X Lighting - yukicoder
 */

#include<cstdio>
#include<algorithm>
 
using namespace std;

/* constant */

const int MAX_M = 100000;

/* typedef */

typedef long long ll;

/* global variables */

int ks0[2], ks1[2];
ll ds0[2][MAX_M], ds1[2][MAX_M];

/* subroutines */

inline ll xy2id0(ll n, ll x, ll y) { return x + y; }
inline ll xy2id1(ll n, ll x, ll y) { return x + (n - 1 - y); }

/* main */

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

  for (int i = 0; i < m; i++) {
    ll xi, yi;
    scanf("%lld%lld", &xi, &yi);
    xi--, yi--;

    ll d0 = xy2id0(n, xi, yi);
    ll d1 = xy2id1(n, xi, yi);
    int p0 = d0 & 1, p1 = d1 & 1;
    ds0[p0][ks0[p0]++] = d0;
    ds1[p1][ks1[p1]++] = d1;
  }

  for (int i = 0; i < 2; i++) {
    sort(ds0[i], ds0[i] + ks0[i]);
    sort(ds1[i], ds1[i] + ks1[i]);
    ks0[i] = unique(ds0[i], ds0[i] + ks0[i]) - ds0[i];
    ks1[i] = unique(ds1[i], ds1[i] + ks1[i]) - ds1[i];
  }

  ll sum = 0;
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < ks0[i]; j++) {
      ll d0 = ds0[i][j];
      ll minx = max(0LL, d0 - (n - 1));
      ll maxx = min(n - 1, d0);
      sum += maxx + 1 - minx;
      //printf("%lld: %lld,%lld\n", d0, minx, maxx);
    }
  }

  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < ks1[i]; j++) {
      ll d1 = ds1[i][j];
      ll minx = max(0LL, d1 - (n - 1));
      ll maxx = min(n - 1, d1);
      sum += maxx + 1 - minx;

      ll miny = n - 1 - (d1 - minx);
      ll maxy = n - 1 - (d1 - maxx);
      //printf("%lld: %lld,%lld %lld,%lld\n", d1, minx, miny, maxx, maxy);
      ll mind0 = xy2id0(n, minx, miny);
      ll maxd0 = xy2id0(n, maxx, maxy);
      int p0 = mind0 & 1;

      int j0 = lower_bound(ds0[p0], ds0[p0] + ks0[p0], mind0) - ds0[p0];
      int j1 = upper_bound(ds0[p0], ds0[p0] + ks0[p0], maxd0) - ds0[p0];
      sum -= j1 - j0;
    }
  }

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