All-one Matrices
#include <bits/stdc++.h> using namespace std; const int maxn=3010; char c; int n,m,a[maxn][maxn],top,ans,mx[maxn][maxn],stk[maxn],l[maxn],r[maxn]; int main() { memset(mx,0x3f,sizeof(mx)); scanf("%d%d",&n,&m); for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) { scanf(" %c",&c); if (c=='0') { a[i][j]=0; } else { a[i][j]=a[i-1][j]+1; } } } for (int i=n;i>=1;i--){ top=0; stk[0]=0; for (int j=1;j<=m;j++){ while (top&&a[i][j]<=a[i][stk[top]]){ top--; } l[j]=stk[top]; stk[++top]=j; } top=0; stk[0]=m+1; for (int j=m;j>=1;j--){ while (top&&a[i][j]<=a[i][stk[top]]){ top--; } r[j]=stk[top]; stk[++top]=j; } for (int j=1;j<=m;j++){ if (a[i][j]&&i<mx[l[j]+1][r[j]-1]){ ans++; mx[l[j]+1][r[j]-1]=i-a[i][j]+1; } } } printf("%d ",ans); return 0; }Beauty Values
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll n,a,v[100000],ans; int main(){ scanf("%lld",&n); for (ll i=1;i<=n;i++){ scanf("%lld",&a); ans+=(n-i+1)*(i-v[a]); v[a]=i; } printf("%lld ",ans); }CDMA
#include<bits/stdc++.h> using namespace std; const int maxn=100101; typedef long long ll; int ans[2000][2000],n; int main() { scanf("%d",&n); ans[1][1]=1; ans[1][2]=1; ans[2][1]=1; ans[2][2]=-1; for (int i=1; i<=2; i++) { for (int j=1; j<=2; j++) { ans[i+2][j]=-ans[i][j]; } } for (int i=1; i<=2; i++) { for (int j=1; j<=2; j++) { ans[i+2][j+2]=ans[i][j]; ans[i][j+2]=ans[i][j]; } } for (int i=1; i<=4; i++) { for (int j=1; j<=4; j++) { ans[i+4][j]=-ans[i][j]; } } for (int i=1; i<=4; i++) { for (int j=1; j<=4; j++) { ans[i+4][j+4]=ans[i][j]; ans[i][j+4]=ans[i][j]; } } for (int i=1; i<=8; i++) { for (int j=1; j<=8; j++) { ans[i+8][j]=-ans[i][j]; } } for (int i=1; i<=8; i++) { for (int j=1; j<=8; j++) { ans[i+8][j+8]=ans[i][j]; ans[i][j+8]=ans[i][j]; } } for (int i=1; i<=16; i++) { for (int j=1; j<=16; j++) { ans[i+16][j]=-ans[i][j]; } } for (int i=1; i<=16; i++) { for (int j=1; j<=16; j++) { ans[i+16][j+16]=ans[i][j]; ans[i][j+16]=ans[i][j]; } } for (int i=1; i<=32; i++) { for (int j=1; j<=32; j++) { ans[i+32][j]=-ans[i][j]; } } for (int i=1; i<=32; i++) { for (int j=1; j<=32; j++) { ans[i+32][j+32]=ans[i][j]; ans[i][j+32]=ans[i][j]; } } for (int i=1; i<=64; i++) { for (int j=1; j<=64; j++) { ans[i+64][j]=-ans[i][j]; } } for (int i=1; i<=64; i++) { for (int j=1; j<=64; j++) { ans[i+64][j+64]=ans[i][j]; ans[i][j+64]=ans[i][j]; } } for (int i=1; i<=128; i++) { for (int j=1; j<=128; j++) { ans[i+128][j]=-ans[i][j]; } } for (int i=1; i<=128; i++) { for (int j=1; j<=128; j++) { ans[i+128][j+128]=ans[i][j]; ans[i][j+128]=ans[i][j]; } } for (int i=1; i<=256; i++) { for (int j=1; j<=256; j++) { ans[i+256][j]=-ans[i][j]; } } for (int i=1; i<=256; i++) { for (int j=1; j<=256; j++) { ans[i+256][j+256]=ans[i][j]; ans[i][j+256]=ans[i][j]; } } for (int i=1; i<=512; i++) { for (int j=1; j<=512; j++) { ans[i+512][j]=-ans[i][j]; } } for (int i=1; i<=512; i++) { for (int j=1; j<=512; j++) { ans[i+512][j+512]=ans[i][j]; ans[i][j+512]=ans[i][j]; } } for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) { printf("%d",ans[i][j]); if (j==n) { printf(" "); } else { printf(" "); } } } }Explorer
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; int f[maxn],n,m,u[maxn],v[maxn],a[maxn*2],siz[maxn],ans,l[maxn],r[maxn],cnt; vector<int>e[maxn*8]; int get_fa(int x) { return x==f[x]?x:get_fa(f[x]); } void ins(int rt,int L,int R,int l,int r,int x) { if (l==L&&R==r) { e[rt].push_back(x); return; } int mid=(L+R)>>1; if (r<=mid) ins(rt<<1,L,mid,l,r,x); else if (l>mid) ins(rt<<1|1,mid+1,R,l,r,x); else { ins(rt<<1,L,mid,l,mid,x); ins(rt<<1|1,mid+1,R,mid+1,r,x); } } void dfs(int rt,int l,int r) { vector<int>lastf; int m=e[rt].size(),mid=(l+r)>>1; for (int i=0; i<m; i++) { int x=get_fa(u[e[rt][i]]),y=get_fa(v[e[rt][i]]); if (siz[x]>siz[y]) { swap(x,y); } lastf.push_back(x); f[x]=y; siz[y]+=siz[x]; } if (get_fa(1)==get_fa(n)) { ans+=a[r+1]-a[l]; } else if (l<r) { dfs(rt<<1,l,mid); dfs(rt<<1|1,mid+1,r); } m=lastf.size(); for (int i=m-1; i>=0; i--) { f[lastf[i]]=lastf[i]; } lastf.clear(); } int main() { scanf("%d%d",&n,&m); for (int i=1; i<=n; i++) { f[i]=i; siz[i]=1; } for (int i=1; i<=m; i++) { scanf("%d%d%d%d",&u[i],&v[i],&l[i],&r[i]); a[++cnt]=l[i]; a[++cnt]=r[i]+1; } sort(a+1,a+cnt+1); cnt=unique(a+1,a+cnt+1)-a-1; for (int i=1; i<=m; i++) { ins(1,1,cnt-1,lower_bound(a+1,a+cnt+1,l[i])-a,lower_bound(a+1,a+cnt+1,r[i]+1)-a-1,i); } dfs(1,1,cnt-1); printf("%d ",ans); return 0; }Gemstones
#include<bits/stdc++.h> using namespace std; char s[100010],ch1,ch2; stack<char>st; int len,ans; int main() { scanf("%s",s); len=strlen(s); for (int i=0; i<len; i++) { if (st.size()<2) { st.push(s[i]); } else { ch1=st.top(); st.pop(); ch2=st.top(); st.pop(); if (ch1==ch2&&ch2==s[i]) { // printf("%d ",i); ans++; } else { st.push(ch2); st.push(ch1); st.push(s[i]); } } } printf("%d ",ans); }Just Jump
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=998244353; const int L=1e7+10; const int maxn=3100; typedef pair<int,int> PII; ll ans; ll f1[L+5],inv[L+5]; ll dp[L+5],sum[L+5],f[maxn][maxn]; PII a[maxn]; ll pow_mod(ll a,ll b) { ll res=1; while (b) { if (b&1) { res=res*a%mod; } a=a*a%mod; b>>=1; } return res; } void init() { f1[0]=1; for (int i=1; i<=L; i++) { f1[i]=f1[i-1]*i%mod; } inv[L]=pow_mod(f1[L],mod-2); for (int i=L-1; i>=0; i--) { inv[i]=inv[i+1]*(i+1)%mod; } } ll C(ll n,ll m) { return f1[n]*inv[m]%mod*inv[n-m]%mod; } int main() { init(); int l,d,m; scanf("%d%d%d",&l,&d,&m); for (int i=1; i<=m; i++) { scanf("%d%d",&a[i].second,&a[i].first); } sort(a+1,a+m+1); dp[0]=sum[0]=1; for (int i=1; i<d; i++) { dp[i]=0; sum[i]=(sum[i-1]+dp[i])%mod; } for (int i=d; i<=l; i++) { dp[i]=sum[i-d]; sum[i]=(sum[i-1]+dp[i])%mod; } ans=dp[l]; f[0][0]=1; for (int i=1; i<=m; i++) { for (int j=0; j<i; j++) { ll dt=a[i].second-a[j].second; ll dlen=a[i].first-a[j].first; if (dt<1||dlen<dt*d) continue; ll tmp=C(dlen-dt*d+dt-1,dt-1); f[i][0]=(f[i][0]+f[j][1]*tmp%mod)%mod; f[i][1]=(f[i][1]+f[j][0]*tmp%mod)%mod; } ans=(ans+(f[i][0]-f[i][1]+mod)%mod*dp[l-a[i].first])%mod; } printf("%lld ",ans); return 0; }Distance
#include <bits/stdc++.h> using namespace std; const int maxn=3e5+10; struct node{ int x,y,z; }; int dp[maxn],n,m,h,Q; vector<int>ex,ey,ez; int dx[]={1,-1,0,0,0,0}; int dy[]={0,0,1,-1,0,0}; int dz[]={0,0,0,0,1,-1}; int getid(int x,int y,int z){ return x*m*h+y*h+z; } queue<node>q; void update(){ while (!q.empty()){ q.pop(); } int sz=ex.size(); for (int i=0;i<sz;i++){ dp[getid(ex[i],ey[i],ez[i])]=0; q.push(node{ex[i],ey[i],ez[i]}); } while (!q.empty()){ node cur=q.front(); q.pop(); for (int i=0;i<6;i++){ int nx=cur.x+dx[i]; int ny=cur.y+dy[i]; int nz=cur.z+dz[i]; if (nx<1||ny<1||nz<1||nx>n||ny>m||nz>h){ continue; } if (dp[getid(nx,ny,nz)]>dp[getid(cur.x,cur.y,cur.z)]+1){ dp[getid(nx,ny,nz)]=dp[getid(cur.x,cur.y,cur.z)]+1; q.push(node{nx,ny,nz}); } } } ex.clear(); ey.clear(); ez.clear(); } int query(int x,int y,int z){ int ans=dp[getid(x,y,z)]; int sz=ex.size(); for (int i=0;i<sz;i++){ ans=min(ans,abs(x-ex[i])+abs(y-ey[i])+abs(z-ez[i])); } return ans; } int main() { scanf("%d%d%d%d",&n,&m,&h,&Q); memset(dp,0x3f,sizeof(dp)); int op,x,y,z; while (Q--) { scanf("%d%d%d%d",&op,&x,&y,&z); if (op==1) { ex.push_back(x); ey.push_back(y); ez.push_back(z); } else { printf("%d ",query(x,y,z)); } if (ex.size()==1000) { update(); } } return 0; }
