結果

問題 No.1997 X Lighting
ユーザー tnakao0123tnakao0123
提出日時 2022-07-03 11:43:03
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 54 ms / 2,000 ms
コード長 1,925 bytes
コンパイル時間 471 ms
コンパイル使用メモリ 46,440 KB
実行使用メモリ 4,592 KB
最終ジャッジ日時 2023-08-19 10:27:29
合計ジャッジ時間 3,156 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge10
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 3 ms
4,380 KB
testcase_06 AC 16 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 3 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 28 ms
4,560 KB
testcase_14 AC 40 ms
4,496 KB
testcase_15 AC 14 ms
4,380 KB
testcase_16 AC 18 ms
4,380 KB
testcase_17 AC 41 ms
4,380 KB
testcase_18 AC 24 ms
4,376 KB
testcase_19 AC 49 ms
4,572 KB
testcase_20 AC 54 ms
4,580 KB
testcase_21 AC 53 ms
4,592 KB
testcase_22 AC 48 ms
4,500 KB
testcase_23 AC 28 ms
4,376 KB
testcase_24 AC 3 ms
4,380 KB
testcase_25 AC 51 ms
4,500 KB
testcase_26 AC 44 ms
4,380 KB
testcase_27 AC 45 ms
4,376 KB
testcase_28 AC 16 ms
4,380 KB
testcase_29 AC 15 ms
4,376 KB
testcase_30 AC 50 ms
4,428 KB
testcase_31 AC 34 ms
4,376 KB
testcase_32 AC 10 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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