QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#773923 | #7363. 忙碌的出题人 | Link_Cut_Y# | 100 ✓ | 195ms | 23776kb | C++14 | 5.0kb | 2024-11-23 10:51:06 | 2024-11-23 10:51:06 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <ctime>
#include <set>
#include <map>
#define int long long
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define rop(i, a, b) for (int i = (a); i < (b); i ++ )
#define dep(i, a, b) for (int i = (a); i >= (b); i -- )
#define dop(i, a, b) for (int i = (a); i > (b); i -- )
#define Darr(a, L, R) cerr << #a "[" << L << " ~ " << R << "] = "; rep(x, L, R) cerr << a[x] << " "; cerr << '\n';
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define D(x) (cerr << #x << " = " << x << '\n')
#define vit vector<int>::iterator
#define all(x) x.begin(), x.end()
#define min(a, b) (a < b ? a : b)
#define max(a, b) (a > b ? a : b)
#define chkmin(a, b) (a = min(a, b))
#define chkmax(a, b) (a = max(a, b))
#define sit set<int>::iterator
#define lowbit(x) (x & -x)
#define eb emplace_back
#define ub upper_bound
#define pb push_back
#define pi acos(-1)
#define gc getchar
#define pc putchar
#define db double
#define y second
#define x first
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<db, db> PDD;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const int mod = 998244353;
const int eps = 1e-9;
const int N = 1000010; int T = 1;
void print(int x) { dep(i, 20, 0) pc(((x >> i) & 1) ? '1' : '0'); }
int qpow(int a, int b = mod - 2, int s = 1) { for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) s = 1ll * s * a % mod; return s; }
namespace IO {
void read() { return; }
void write(char ch) { pc(ch); return; }
void write() { return; }
template <typename T> void read(T &x) { x = 0; T w = 0; char ch = gc(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = gc(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ 48), ch = gc(); x = w ? -x : x; }
template <typename T> void print(T x) { if (!x) return; print<T>(x / 10), pc((x % 10) ^ '0'); }
template <typename T> void write(T x) { if (x > 0) print<T>(x); else if (x < 0) pc('-'), print<T>(-x); else pc('0'); }
template <typename T> void write(T x, char en) { write<T>(x), pc(en); }
template <typename T, typename ...T2> void read(T &s, T2 &...oth) { read(s); read(oth...); return; }
}; using namespace IO;
const int INF = 1e15;
int lb[N], rb[N], a[N], stk[N];
int n, L, R, top, a1, a2;
vector<int> ans;
int calc(int i, int lim) {
// 以 i 为中心长度 <= lim 的方案数
int r = rb[i], l = lb[i];
if (lim == 0) return 0;
if (r - l + 1 <= lim) return (i - l + 1) * (r - i + 1);
lim ++ ; int r2 = min(r, i + lim - 1);
int s = (i - l + 1) * (r - r2); int u = (r2 - lim + 1 - l + 1);
int v = (i - l + 1 <= lim) ? 1 : i - lim + 1 - l + 1;
s = s + (u + v) * (u - v + 1) / 2;
return (i - l + 1) * (r - i + 1) - s;
}
int Rank(int mid) {
// 面积为 mid 的矩形排名
int s = 0; rep(i, 1, n)
s += calc(i, (mid + a[i] - 1) / a[i] - 1);
return s + 1;
}
void sub_intake(int i, int ll, int lr) {
// 将 i 为中心,长度在 [ll, lr] 中的矩形统计进答案。
if (ll > lr) return;
int l = lb[i], r = rb[i], len = r - l + 1;
if (len < ll) return;
l = max(l, i - lr + 1);
rep(it, l, i) {
int tl = it + ll - 1, tr = it + lr - 1;
tr = min(tr, r); tl = max(tl, i); if (tl > tr) break;
rep(j, tl, tr) ans.pb((j - it + 1) * a[i]);
}
}
void intake(int sl, int sr) {
// 将面积在 [sl, sr] 中的矩形统计进答案。
rep(i, 1, n) sub_intake(i, (sl + a[i] - 1) / a[i], sr / a[i]);
}
void sub() {
read(n);
rep(i, 1, n) read(a[i]);
read(L, R);
// 第一遍单调栈,处理每个位置左边第一个小于**等于**这个数的位置。
top = 0; rep(i, 0, n) {
while (top and a[stk[top]] > a[i]) top -- ;
lb[i] = stk[top] + 1; stk[ ++ top] = i;
}
// 第二遍单调栈,处理每个位置右边第一个小于这个数的位置。
top = 0; dep(i, n + 1, 1) {
while (top and a[stk[top]] >= a[i]) top -- ;
rb[i] = stk[top] - 1; stk[ ++ top] = i;
}
// 找到面积大于 area(L) 的最小的矩形面积
int l = 0, r = (int)1e13;
while (l < r) {
int mid = l + r >> 1;
if (Rank(mid) > L) r = mid;
else l = mid + 1;
} a1 = l;
// 找到面积小于 area(R) 的最大矩形面积
l = 0, r = (int)1e13;
while (l < r) {
int mid = l + r + 1 >> 1;
if (Rank(mid + 1) <= R) l = mid;
else r = mid - 1;
} a2 = l;
intake(a1, a2);
int area1 = -INF, area2 = INF;
rep(i, 1, n) {
int len = (a1 + a[i] - 1) / a[i] - 1;
if (rb[i] - lb[i] + 1 >= len) area1 = max(area1, len * a[i]);
len = (a2 / a[i]) + 1;
if (rb[i] - lb[i] + 1 >= len) area2 = min(area2, len * a[i]);
} int rk1 = Rank(a1), rk2 = Rank(a2 + 1);
if (rk1 > R) {
rep(i, L, R) write(area1, ' ');
puts(""); return;
}
rop(i, L, rk1) ans.pb(area1);
rep(i, rk2, R) ans.pb(area2);
sort(all(ans)); for (auto i : ans) printf("%lld ", i);
return;
}
signed main() {
while (T -- ) sub();
return 0;
}
詳細信息
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 2ms
memory: 10104kb
input:
500 614716456 379652456 778509712 908766285 482626557 775970238 477579092 475111040 84033329 300444417 73431560 147109232 243351359 715651776 906589179 979825146 111392720 740354295 71803884 532698029 901967612 380599137 384828710 272583565 663907168 748042444 701204179 407381195 718652356 837391507...
output:
1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 1388847207 138...
result:
ok single line: '1388847207 1388847207 13888472...10184949 1510184949 1510184949 '
Test #2:
score: 10
Accepted
time: 2ms
memory: 10236kb
input:
500 27970085 842848466 559426210 242855004 760446676 861565918 507012688 557418543 925681060 348998349 475224243 565932854 537313762 539258245 430870181 530136386 574122855 163938228 132232929 509292002 637264372 773813857 461611804 926821895 783736508 818928522 190826242 931319426 80143413 88698853...
output:
3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 3734861992 373...
result:
ok single line: '3734861992 3734861992 37348619...09997841 4809997841 4809997841 '
Test #3:
score: 10
Accepted
time: 8ms
memory: 10120kb
input:
10000 56558520 24076 532679989 868659433 718470236 669539219 565891426 405613315 228588763 424940173 86535099 213118975 928296103 44601852 413631070 75973939 166671234 688526244 305448983 282598136 319395657 331028407 440988471 395283245 762047634 431077598 141271074 975860182 295187696 102992550 46...
output:
451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 451500065 ...
result:
ok single line: '451500065 451500065 451500065 ... 452680210 452680210 452680210 '
Test #4:
score: 10
Accepted
time: 29ms
memory: 13408kb
input:
10000 480668445 668043016 295399375 732184676 122324282 255982280 355392797 28731822 344107766 662486064 134432824 995270472 102760799 504208968 650338962 765669861 766398985 162302391 519506962 288925253 28846309 383839304 417396720 407846048 96274977 533045195 127900899 888560800 468796310 3198150...
output:
20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 20741385 207...
result:
ok single line: '20741385 20741385 20741385 207...527 21265527 21265527 21265527 '
Test #5:
score: 10
Accepted
time: 124ms
memory: 15952kb
input:
300000 798955753 286250378 502811779 503621397 92925582 6646849 518944397 770834076 203832545 202893671 103819760 610042299 453933804 743345154 539594131 67829879 56530495 165455177 406676438 149176095 634841263 339856850 623804539 159374193 619691965 719363352 749153472 886061303 174499069 85917864...
output:
65599584
result:
ok single line: '65599584 '
Test #6:
score: 10
Accepted
time: 150ms
memory: 18056kb
input:
300000 766376442 928503862 759758373 732880914 717705081 564401126 39391912 266563115 890722259 420256593 140756365 543550091 115541768 746823302 612292685 767316055 635845043 654973645 544337001 290376461 576914449 914856675 671199356 713784470 363344552 601573876 31583713 603168080 72489400 375080...
output:
199533222
result:
ok single line: '199533222 '
Test #7:
score: 10
Accepted
time: 119ms
memory: 16432kb
input:
300000 956686221 414741964 493043893 629807942 180972256 269970594 772545182 612006785 867693543 216559503 730247279 226568318 935026662 707433164 809741369 574785329 807598034 357521029 855386 479475104 141336111 354931933 914443894 54780578 926960727 223607222 373442712 304014927 7965636 516364169...
output:
61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 61009314 610...
result:
ok single line: '61009314 61009314 61009314 610...589 61009589 61009589 61009589 '
Test #8:
score: 10
Accepted
time: 182ms
memory: 22372kb
input:
300000 332562455 457596 240326487 540486075 656909416 733563955 536158780 516014015 725473229 159996733 966117635 384123908 554648950 941913359 735104878 70264708 321207149 649076932 934217283 526740938 203318592 536910059 813024672 584090471 456303660 92830681 922008025 776817225 41208957 906313981...
output:
264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 264657536 ...
result:
ok single line: '264657536 264657536 264657536 ... 264662102 264662102 264662102 '
Test #9:
score: 10
Accepted
time: 195ms
memory: 21744kb
input:
300000 301865399 920265572 576682447 938152861 235472173 759617172 880358770 815285188 557222986 661313551 3537362 758595883 848808290 94541657 186990789 889266656 106528936 255663327 696637470 36185472 196015631 455909180 119220747 337639792 278234577 249069942 500351390 923290017 293186423 3671731...
output:
290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 290501960 ...
result:
ok single line: '290501960 290501960 290501960 ... 290507752 290507752 290507752 '
Test #10:
score: 10
Accepted
time: 139ms
memory: 23776kb
input:
300000 562625121 376819377 685468134 992506922 669101061 952159043 54304806 579126651 572881783 369989807 986688430 603593700 835219329 394853362 13206834 806309995 546320046 681607475 647209229 637169228 918784301 522067469 924188583 892205985 859578401 796516404 614799206 256380193 797680503 70500...
output:
53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 53967000 539...
result:
ok single line: '53967000 53967000 53967000 539...625 53969625 53969625 53969625 '