首页 > 代码库 > CodeForces 15D Map 单调队列优化
CodeForces 15D Map 单调队列优化
两次单调队列求出每个子矩阵的最小值,区间减法求出每个子矩阵的和,然后丢到优先队列里跑出来就好了。
写锉了,加了读入挂才过。
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <cmath> #include <stack> #include <map> #include <ctime> #include <iomanip> #pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-6) #define LL long long #define ULL unsigned long long #define _LL __int64 #define INF 0x3f3f3f3f #define Mod 1000000007 /** I/O Accelerator Interface .. **/ #define g (c=getchar()) #define d isdigit(g) #define p x=x*10+c-‘0‘ #define n x=x*10+‘0‘-c #define pp l/=10,p #define nn l/=10,n template<class T> inline T& RD(T &x) { char c; while(!d); x=c-‘0‘; while(d)p; return x; } template<class T> inline T& RDD(T &x) { char c; while(g,c!=‘-‘&&!isdigit(c)); if (c==‘-‘) { x=‘0‘-g; while(d)n; } else { x=c-‘0‘; while(d)p; } return x; } inline double& RF(double &x) //scanf("%lf", &x); { char c; while(g,c!=‘-‘&&c!=‘.‘&&!isdigit(c)); if(c==‘-‘)if(g==‘.‘) { x=0; double l=1; while(d)nn; x*=l; } else { x=‘0‘-c; while(d)n; if(c==‘.‘) { double l=1; while(d)nn; x*=l; } } else if(c==‘.‘) { x=0; double l=1; while(d)pp; x*=l; } else { x=c-‘0‘; while(d)p; if(c==‘.‘) { double l=1; while(d)pp; x*=l; } } return x; } #undef nn #undef pp #undef n #undef p #undef d #undef g using namespace std; const int BLOCK = sqrt(1000.0); LL Map[1010][1010]; bool mark[1010][1010]; LL ans[1010][1010] = {0}; LL Min[1010][1010]; struct N { int x,y; LL val; bool operator < (const N &a) const { if(val != a.val) return a.val < val; if(x != a.x) return a.x < x; return a.y < y; } } tmp; int x[1000100],y[1000100]; LL val[1000100]; priority_queue<N> q; int que[1010]; void CalMin(int n,int m,int a,int b) { int i,j,S,E; for(i = 1; i <= n; ++i) { S = 0,E = 0; for(j = m; j >= 1; --j) { while(E > S && Map[i][que[E-1]] > Map[i][j]) E--; que[E++] = j; while(S < E && que[S] > j+b-1) S++; Min[i][j] = Map[i][que[S]]; } } for(j = 1; j <= m; ++j) { S = 0,E = 0; for(i = n; i >= 1; --i) { while(E > S && Min[que[E-1]][j] > Min[i][j]) E--; que[E++] = i; while(S < E && que[S] > i+a-1) S++; Map[i][j] = Min[que[S]][j]; } } } int main() { int i,j,n,m,a,b; RD(n); RD(m); RD(a); RD(b); // scanf("%d %d %d %d",&n,&m,&a,&b); for(i = 1; i <= n; ++i) for(j = 1; j <= m; ++j) RD(Map[i][j]);//scanf("%I64d",&Map[i][j]); for(i = n; i >= 1; --i) for(j = m; j >= 1; --j) ans[i][j] = Map[i][j] + ans[i+1][j] + ans[i][j+1] - ans[i+1][j+1]; int N = n-a+1,M = m-b+1; for(i = 1; i <= N; ++i) for(j = 1; j <= M; ++j) ans[i][j] = ans[i][j] - ans[i+a][j] - ans[i][j+b] + ans[i+a][j+b]; CalMin(n,m,a,b); // for(i = 1;i <= n; ++i) // { // for(j = 1;j <= m; ++j) // printf("%3I64d ",ans[i][j]); // puts(""); // } // // puts(""); // // for(i = 1;i <= n; ++i) // { // for(j = 1;j <= m; ++j) // printf("%3I64d ",Min[i][j]); // puts(""); // } for(i = N; i >= 1; --i) for(j = M; j >= 1; --j) q.push( {i,j,ans[i][j]-Map[i][j]*a*b}); memset(mark,false,sizeof(mark)); int L,R,T,B,Top = 0; while(q.empty() == false) { tmp = q.top(); q.pop(); if(mark[tmp.x][tmp.y]) continue; T = max(1,tmp.x-a+1),B = min(n,tmp.x+a-1); L = max(1,tmp.y-b+1),R = min(m,tmp.y+b-1); for(i = T; i <= B; ++i) for(j = L; j <= R; ++j) mark[i][j] = true; x[Top] = tmp.x,y[Top] = tmp.y,val[Top] = tmp.val,Top++; } printf("%d\n",Top); for(i = 0; i < Top; ++i) printf("%d %d %I64d\n",x[i],y[i],val[i]); return 0; }
CodeForces 15D Map 单调队列优化
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。