結果
問題 | No.2574 Defect-free Rectangles |
ユーザー |
![]() |
提出日時 | 2023-12-03 11:48:01 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,690 ms / 2,000 ms |
コード長 | 1,758 bytes |
コンパイル時間 | 3,989 ms |
コンパイル使用メモリ | 163,088 KB |
実行使用メモリ | 39,424 KB |
最終ジャッジ日時 | 2024-09-26 22:05:35 |
合計ジャッジ時間 | 11,778 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include<bits/stdc++.h>using namespace std;constexpr int MAX=4096,LOG=12;int lazy[MAX*2];int dat[MAX*2];int a[MAX][MAX];inline void update(int i){dat[i]=dat[i*2]+dat[i*2+1];}inline void push(int i){if(lazy[i]!=-2){lazy[i*2]=lazy[i*2+1]=lazy[i];dat[i*2]=dat[i*2+1]=lazy[i]<<(__builtin_clz(i)+LOG-32);lazy[i]=-2;}}int prod(int r){r+=MAX;int l=MAX;int ret=0;for(int i=LOG;i>=1;i--)if(((r>>i)<<i)!=r)push((r-1)>>i);while(l<r){if(l&1)ret+=dat[l++];if(r&1)ret+=dat[--r];l>>=1;r>>=1;}return ret;}void apply(int l,int f){l+=MAX;int r=MAX*2;for(int i=LOG;i>=1;i--)if(((l>>i)<<i)!=l)push(l>>i);int l2=l,r2=r;while(l<r){if(l&1){dat[l]=f<<(__builtin_clz(l)+LOG-31);lazy[l++]=f;}if(r&1){r--;dat[r]=f<<(__builtin_clz(r)+LOG-31);lazy[r]=f;}l>>=1,r>>=1;}l=l2,r=r2;for(int i=1;i<=LOG;i++){if(((l>>i)<<i)!=l)update(l>>i);}}int read_int() {int ret = 0;char ch = getchar_unlocked();while (isspace(ch)) { ch = getchar_unlocked(); }for (; isdigit(ch); ch = getchar_unlocked())ret = (ret * 10) + (ch - '0');ungetc(ch, stdin);return ret;}int main(){int h,w,n,x,y;h=read_int(),w=read_int(),n=read_int();for(int i=0;i<h;i++)for(int j=0;j<w;j++)a[i][j]=-1;while(n--){x=read_int(),y=read_int();a[x-1][y-1]=0;}for(int i=h;i--;)for(int j=0;j<w;j++)if(a[i][j]==-1){if(i==h)a[i][j]=1;else a[i][j]=a[i+1][j]+1;}for(int i=1;i<MAX*2;i++)lazy[i]=-2;long long ans=0;for(int i=0;i<h;i++){lazy[1]=-1;dat[1]=-MAX;for(int j=0;j<w;j++){ans+=j*a[i][j]-prod(a[i][j]);apply(a[i][j],j);}}cout<<ans<<endl;}