商城网站建设哪家专业,软装设计师培训中心,建立手机网站,项目外包网站题目中给出的h和w范围均大#xff0c;其实n的最大范围才200000#xff0c;所以我们建立的线段树大小为min(h,n),线段树的每一个节点包含一个变量c#xff0c;记录当前区间内还剩下的可以put on的最大长度。插入一个数时#xff0c;如果该数大于该区间最大值#xff0c;则返… 题目中给出的h和w范围均大其实n的最大范围才200000所以我们建立的线段树大小为min(h,n),线段树的每一个节点包含一个变量c记录当前区间内还剩下的可以put on的最大长度。插入一个数时如果该数大于该区间最大值则返回-1说明put on不了。否则将它插入到页节点并返回插入的下标接着一定不要忘记更新父节点的c值。 #define _CRT_SECURE_NO_DEPRECATE
#includeiostream
#includealgorithm
using namespace std;
const int MAXN 200001;
struct Tnode{int e, b;int c;
};
int h, w, n,ans;;
Tnode tree[4 * MAXN];
void Create(int v, int b, int e){tree[v].b b;tree[v].e e;tree[v].c w;if (e b){int mid (b e) 1;Create(2 * v 1, b, mid);Create(2 * v 2, mid 1, e);}
}
void Insert(int v,int x){if (x tree[v].c){ans -1;return;}if (tree[v].btree[v].e){tree[v].c - x;ans tree[v].b;return;}if (x tree[2 * v 1].c)Insert(2 * v 1, x);elseInsert(2 * v 2, x);tree[v].c max(tree[2 * v 1].c, tree[2 * v 2].c);
}
int main(){int x;while (~scanf(%d%d%d, h, w, n)){int len min(h, n);Create(0, 1, len);for (int i 0; i n; i){scanf(%d,x);Insert(0, x);printf(%d\n, ans);}}return 0;
}转载于:https://www.cnblogs.com/td15980891505/p/5747735.html
