結果

問題 No.2574 Defect-free Rectangles
ユーザー Taiki0715Taiki0715
提出日時 2023-12-02 16:39:55
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,302 bytes
コンパイル時間 6,100 ms
コンパイル使用メモリ 391,144 KB
実行使用メモリ 21,376 KB
最終ジャッジ日時 2024-09-26 20:34:59
合計ジャッジ時間 10,867 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 4 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 243 ms
9,472 KB
testcase_07 AC 298 ms
9,344 KB
testcase_08 AC 284 ms
9,344 KB
testcase_09 TLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 AC 845 ms
12,288 KB
testcase_15 AC 336 ms
8,704 KB
testcase_16 AC 64 ms
5,888 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <immintrin.h>

//
#include <bits/stdc++.h>
#include<atcoder/lazysegtree>
using namespace std;
using namespace atcoder;
using ll=long long;
#define rep(i,n) for(int i=0;i<n;i++)
namespace fastio {
static constexpr int SZ = 1 << 17;
char ibuf[SZ], obuf[SZ];
int pil = 0, pir = 0, por = 0;

struct Pre {
  char num[40000];
  constexpr Pre() : num() {
    for (int i = 0; i < 10000; i++) {
      int n = i;
      for (int j = 3; j >= 0; j--) {
        num[i * 4 + j] = n % 10 + '0';
        n /= 10;
      }
    }
  }
} constexpr pre;

inline void load() {
  memcpy(ibuf, ibuf + pil, pir - pil);
  pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin);
  pil = 0;
}
inline void flush() {
  fwrite(obuf, 1, por, stdout);
  por = 0;
}

inline void rd(char &c) { c = ibuf[pil++]; }
template <typename T>
inline void rd(T &x) {
  if (pil + 32 > pir) load();
  char c;
  do
    c = ibuf[pil++];
  while (c < '-');
  x = 0;
  while (c >= '0') {
    x = x * 10 + (c & 15);
    c = ibuf[pil++];
  }
}
inline void rd() {}
template <typename Head, typename... Tail>
inline void rd(Head &head, Tail &... tail) {
  rd(head);
  rd(tail...);
}

inline void wt(char c) { obuf[por++] = c; }
template <typename T>
inline void wt(T x) {
  if (por > SZ - 32) flush();
  if (!x) {
    obuf[por++] = '0';
    return;
  }
  int i = 12;
  char buf[16];
  while (x >= 10000) {
    memcpy(buf + i, pre.num + (x % 10000) * 4, 4);
    x /= 10000;
    i -= 4;
  }
  if (x < 100) {
    if (x < 10) {
      wt(char('0' + char(x)));
    } else {
      uint32_t q = (uint32_t(x) * 205) >> 11;
      uint32_t r = uint32_t(x) - q * 10;
      obuf[por + 0] = '0' + q;
      obuf[por + 1] = '0' + r;
      por += 2;
    }
  } else {
    if (x < 1000) {
      memcpy(obuf + por, pre.num + (x << 2) + 1, 3);
      por += 3;
    } else {
      memcpy(obuf + por, pre.num + (x << 2), 4);
      por += 4;
    }
  }
  memcpy(obuf + por, buf + i + 4, 12 - i);
  por += 12 - i;
}

inline void wt() {}
template <typename Head, typename... Tail>
inline void wt(Head head, Tail... tail) {
  wt(head);
  wt(tail...);
}
template <typename T>
inline void wtn(T x) {
  wt(x, '\n');
}

} 
using fastio::rd;
using fastio::wt;
using fastio::wtn;
using namespace std;
constexpr int SZ = 1 << 19;
uint32_t buf1_[SZ * 2] __attribute__((aligned(64)));
uint32_t buf2_[SZ * 2] __attribute__((aligned(64)));
struct S{
  int sz;
  int sum;
};
S op(S x,S y){return {x.sz+y.sz,x.sum+y.sum};}
S e(){return {0,0};}
S mapping(int f,S x){
  if(f!=-10)x.sum=f*x.sz;
  return x;
}
int composition(int f,int g){
  if(f!=-10)return f;
  return g;
}
int id(){return -10;}
short a[3000][3000];
int main(){
  int h,w;
  int n;
  rd(h,w,n);
  ll ans=0;
  rep(i,h)rep(j,w)a[i][j]=-1;
  int x,y;
  while(n--){
    rd(x,y);
    a[x-1][y-1]=0;
  }
  for(short i=h-1;i>=0;--i)rep(j,w)if(a[i][j]==-1){
    if(i==h-1)a[i][j]=1;
    else a[i][j]=a[i+1][j]+1;
  }
  vector<S>dat(h,{1,0});
  lazy_segtree<S,op,e,int,mapping,composition,id>seg(dat);
  for(short i=0;i<h;i++){
    seg.apply(0,h,-1);
    for(int j=0;j<w;j++){
      ans+=j*a[i][j]-seg.prod(0,a[i][j]).sum;
      seg.apply(a[i][j],h,j);
    }
  }
  cout<<ans<<endl;
}
//手元では1850msなんだ助けてあぷ〜
0