#P10309. [2023年重庆八中NOI模拟]最佳观影

    ID: 9427 传统题 2000ms 512MiB 尝试: 9 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-不变量分析等差数列求和二叉堆普通线段树

[2023年重庆八中NOI模拟]最佳观影

题目描述

电影院有 kk 行、每行 kk 个座位,kk 为奇数。令 c=(k+1)/2c=(k+1)/2。座位 (x,y)(x,y) 的观影代价为 ∣x−c∣+∣y−c∣|x-c|+|y-c|,代价越小越好。

最初所有座位均未售出。nn 个团队依次到来,第 ii 个团队有 mim_i 人。为该团队选择一行中的 mim_i 个连续未售座位,使这些座位的观影代价总和最小。若最优选择不唯一,优先选行号较小的,再优先选左端座位编号较小的。

一旦售出,座位就不能再次选择。若没有一组符合要求的座位,则这个团队放弃购票。

输入格式

第一行两个整数 n,kn,k。第二行 nn 个整数 m1,…,mnm_1,\ldots,m_n。

输出格式

按团队到来的顺序输出 nn 行。未购票输出 -1,否则输出 x,l,rx,l,r,表示第 xx 行从第 ll 个到第 rr 个座位,含两端。

样例

7 3
1 2 1 2 1 2 1
2 2 2
1 1 2
2 1 1
3 1 2
2 3 3
-1
1 3 3

数据范围

测试点 nn 上界 kk 上界
1–2 50 25
3–4 200 101
5 1000 501
6 2000 1001
7 10510^5 50001
8 2×1052\times10^5 105+110^5+1
9 3×1053\times10^5 2×105+12\times10^5+1
10 4×1054\times10^5 3×105+13\times10^5+1

原 PDF 题面