ICPC2015 国内予選 参加記
作りました。みなさんプレイしましょう。
AOJ 0618: Rampart
2011合宿のDragon原液1mlを1000倍に薄めて付属の計量カップ1杯とってきたくらい簡単。
これで本選5とは…(というか去年と一昨年が難しすぎるだけかも)
#include<stdio.h> #include<set> #include<algorithm> #include<vector> using namespace std; bool t[4100][4100]; short ul[4100][4100]; short dl[4100][4100]; short ll[4100][4100]; short rl[4100][4100]; int bit[5000]; int sum(int a,int b){ if(a)return sum(0,b)-sum(0,a-1); int ret=0; for(;b>=0;b=(b&(b+1))-1)ret+=bit[b]; return ret; } void add(int a,int b){ for(;a<5000;a|=a+1)bit[a]+=b; } pair<int,int>ev[5000]; int P; long long count(vector<int>L,vector<int>R){ int n=L.size(); for(int i=0;i<5000;i++)bit[i]=0; for(int i=0;i<n;i++)ev[i]=make_pair(i-L[i],i); std::sort(ev,ev+n); long long ret=0; int at=0; for(int i=0;i<n;i++){ while(at<n&&ev[at].first<i){ add(ev[at].second,1); at++; } int left=i+P-1; int right=i+R[i]-1; if(left<=right)ret+=sum(left,right); } //printf("%lld ",ret); return ret; } int main(){ int H,W,L; scanf("%d%d%d%d",&H,&W,&P,&L); bool hanten=false; if(H>W){ swap(H,W); hanten=true; } for(int i=0;i<L;i++){ int p,q; scanf("%d%d",&p,&q); p--;q--; if(hanten)swap(p,q); t[p][q]=1; } for(int i=0;i<H;i++)for(int j=0;j<W;j++){ if(t[i][j]){ ul[i][j]=ll[i][j]=0; }else{ if(i==0)ul[i][j]=1; else ul[i][j]=ul[i-1][j]+1; if(j==0)ll[i][j]=1; else ll[i][j]=ll[i][j-1]+1; } } for(int i=H-1;i>=0;i--)for(int j=W-1;j>=0;j--){ if(t[i][j]){ dl[i][j]=rl[i][j]=0; }else{ if(i==H-1)dl[i][j]=1; else dl[i][j]=dl[i+1][j]+1; if(j==W-1)rl[i][j]=1; else rl[i][j]=rl[i][j+1]+1; } } for(int i=0;i<H;i++)for(int j=0;j<W;j++){ rl[i][j]=min(rl[i][j],dl[i][j]); ll[i][j]=min(ll[i][j],ul[i][j]); } long long ret=0; for(int i=1;i<H;i++){ vector<int>tl(i); vector<int>tr(i); for(int j=0;j<i;j++){ tl[j]=ll[H-i+j][j]; tr[j]=rl[H-i+j][j]; } ret+=count(tl,tr); } for(int i=1;i<H;i++){ vector<int>tl(i); vector<int>tr(i); for(int j=0;j<i;j++){ tl[j]=ll[j][W-i+j]; tr[j]=rl[j][W-i+j]; } ret+=count(tl,tr); } for(int i=0;i<=W-H;i++){ vector<int>tl(H); vector<int>tr(H); for(int j=0;j<H;j++){ tl[j]=ll[j][i+j]; tr[j]=rl[j][i+j]; } ret+=count(tl,tr); } printf("%lld\n",ret); }