QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #864169 | #9222. Price Combo | changziliang | TL | 1162ms | 212080kb | C++20 | 12.9kb | 2025-01-20 11:18:46 | 2025-01-20 11:18:46 |
Judging History
answer
// b, a 的转移都写成矩阵的形式， 这个感觉很厉害
#include<bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#define pb emplace_back
#define MP make_pair
using namespace std;
typedef long long LL;
const LL INF = 1e18;
const int N = 2e5 + 10;
inline LL Min(LL x, LL y) {return x <= y ? x : y;}
struct matrix {
LL mat[4][4];
friend matrix operator * (matrix a, matrix b) {
matrix c;
for(int i = 0; i < 4; i ++ )
for(int j = 0; j < 4; j ++ )
c.mat[i][j] = INF;
c.mat[0][0] = min(c.mat[0][0], a.mat[0][0] + b.mat[0][0]);
c.mat[0][0] = min(c.mat[0][0], a.mat[0][1] + b.mat[1][0]);
c.mat[0][0] = min(c.mat[0][0], a.mat[0][2] + b.mat[2][0]);
c.mat[0][0] = min(c.mat[0][0], a.mat[0][3] + b.mat[3][0]);
c.mat[0][1] = min(c.mat[0][1], a.mat[0][0] + b.mat[0][1]);
c.mat[0][1] = min(c.mat[0][1], a.mat[0][1] + b.mat[1][1]);
c.mat[0][1] = min(c.mat[0][1], a.mat[0][2] + b.mat[2][1]);
c.mat[0][1] = min(c.mat[0][1], a.mat[0][3] + b.mat[3][1]);
c.mat[0][2] = min(c.mat[0][2], a.mat[0][0] + b.mat[0][2]);
c.mat[0][2] = min(c.mat[0][2], a.mat[0][1] + b.mat[1][2]);
c.mat[0][2] = min(c.mat[0][2], a.mat[0][2] + b.mat[2][2]);
c.mat[0][2] = min(c.mat[0][2], a.mat[0][3] + b.mat[3][2]);
c.mat[0][3] = min(c.mat[0][3], a.mat[0][0] + b.mat[0][3]);
c.mat[0][3] = min(c.mat[0][3], a.mat[0][1] + b.mat[1][3]);
c.mat[0][3] = min(c.mat[0][3], a.mat[0][2] + b.mat[2][3]);
c.mat[0][3] = min(c.mat[0][3], a.mat[0][3] + b.mat[3][3]);
c.mat[1][0] = min(c.mat[1][0], a.mat[1][0] + b.mat[0][0]);
c.mat[1][0] = min(c.mat[1][0], a.mat[1][1] + b.mat[1][0]);
c.mat[1][0] = min(c.mat[1][0], a.mat[1][2] + b.mat[2][0]);
c.mat[1][0] = min(c.mat[1][0], a.mat[1][3] + b.mat[3][0]);
c.mat[1][1] = min(c.mat[1][1], a.mat[1][0] + b.mat[0][1]);
c.mat[1][1] = min(c.mat[1][1], a.mat[1][1] + b.mat[1][1]);
c.mat[1][1] = min(c.mat[1][1], a.mat[1][2] + b.mat[2][1]);
c.mat[1][1] = min(c.mat[1][1], a.mat[1][3] + b.mat[3][1]);
c.mat[1][2] = min(c.mat[1][2], a.mat[1][0] + b.mat[0][2]);
c.mat[1][2] = min(c.mat[1][2], a.mat[1][1] + b.mat[1][2]);
c.mat[1][2] = min(c.mat[1][2], a.mat[1][2] + b.mat[2][2]);
c.mat[1][2] = min(c.mat[1][2], a.mat[1][3] + b.mat[3][2]);
c.mat[1][3] = min(c.mat[1][3], a.mat[1][0] + b.mat[0][3]);
c.mat[1][3] = min(c.mat[1][3], a.mat[1][1] + b.mat[1][3]);
c.mat[1][3] = min(c.mat[1][3], a.mat[1][2] + b.mat[2][3]);
c.mat[1][3] = min(c.mat[1][3], a.mat[1][3] + b.mat[3][3]);
c.mat[2][0] = min(c.mat[2][0], a.mat[2][0] + b.mat[0][0]);
c.mat[2][0] = min(c.mat[2][0], a.mat[2][1] + b.mat[1][0]);
c.mat[2][0] = min(c.mat[2][0], a.mat[2][2] + b.mat[2][0]);
c.mat[2][0] = min(c.mat[2][0], a.mat[2][3] + b.mat[3][0]);
c.mat[2][1] = min(c.mat[2][1], a.mat[2][0] + b.mat[0][1]);
c.mat[2][1] = min(c.mat[2][1], a.mat[2][1] + b.mat[1][1]);
c.mat[2][1] = min(c.mat[2][1], a.mat[2][2] + b.mat[2][1]);
c.mat[2][1] = min(c.mat[2][1], a.mat[2][3] + b.mat[3][1]);
c.mat[2][2] = min(c.mat[2][2], a.mat[2][0] + b.mat[0][2]);
c.mat[2][2] = min(c.mat[2][2], a.mat[2][1] + b.mat[1][2]);
c.mat[2][2] = min(c.mat[2][2], a.mat[2][2] + b.mat[2][2]);
c.mat[2][2] = min(c.mat[2][2], a.mat[2][3] + b.mat[3][2]);
c.mat[2][3] = min(c.mat[2][3], a.mat[2][0] + b.mat[0][3]);
c.mat[2][3] = min(c.mat[2][3], a.mat[2][1] + b.mat[1][3]);
c.mat[2][3] = min(c.mat[2][3], a.mat[2][2] + b.mat[2][3]);
c.mat[2][3] = min(c.mat[2][3], a.mat[2][3] + b.mat[3][3]);
c.mat[3][0] = min(c.mat[3][0], a.mat[3][0] + b.mat[0][0]);
c.mat[3][0] = min(c.mat[3][0], a.mat[3][1] + b.mat[1][0]);
c.mat[3][0] = min(c.mat[3][0], a.mat[3][2] + b.mat[2][0]);
c.mat[3][0] = min(c.mat[3][0], a.mat[3][3] + b.mat[3][0]);
c.mat[3][1] = min(c.mat[3][1], a.mat[3][0] + b.mat[0][1]);
c.mat[3][1] = min(c.mat[3][1], a.mat[3][1] + b.mat[1][1]);
c.mat[3][1] = min(c.mat[3][1], a.mat[3][2] + b.mat[2][1]);
c.mat[3][1] = min(c.mat[3][1], a.mat[3][3] + b.mat[3][1]);
c.mat[3][2] = min(c.mat[3][2], a.mat[3][0] + b.mat[0][2]);
c.mat[3][2] = min(c.mat[3][2], a.mat[3][1] + b.mat[1][2]);
c.mat[3][2] = min(c.mat[3][2], a.mat[3][2] + b.mat[2][2]);
c.mat[3][2] = min(c.mat[3][2], a.mat[3][3] + b.mat[3][2]);
c.mat[3][3] = min(c.mat[3][3], a.mat[3][0] + b.mat[0][3]);
c.mat[3][3] = min(c.mat[3][3], a.mat[3][1] + b.mat[1][3]);
c.mat[3][3] = min(c.mat[3][3], a.mat[3][2] + b.mat[2][3]);
c.mat[3][3] = min(c.mat[3][3], a.mat[3][3] + b.mat[3][3]);
return c;
}
friend bool operator != (matrix a, matrix b) {
for(int i = 0; i < 4; i ++ )
for(int j = 0; j < 4; j ++ )
if(a.mat[i][j] != b.mat[i][j]) return 1;
return 0;
}
} I, T;
typedef pair< int, matrix > PII;
matrix Min(matrix a, matrix b) {
matrix c;
c.mat[0][0] = min(a.mat[0][0], b.mat[0][0]);
c.mat[0][1] = min(a.mat[0][1], b.mat[0][1]);
c.mat[0][2] = min(a.mat[0][2], b.mat[0][2]);
c.mat[0][3] = min(a.mat[0][3], b.mat[0][3]);
c.mat[1][0] = min(a.mat[1][0], b.mat[1][0]);
c.mat[1][1] = min(a.mat[1][1], b.mat[1][1]);
c.mat[1][2] = min(a.mat[1][2], b.mat[1][2]);
c.mat[1][3] = min(a.mat[1][3], b.mat[1][3]);
c.mat[2][0] = min(a.mat[2][0], b.mat[2][0]);
c.mat[2][1] = min(a.mat[2][1], b.mat[2][1]);
c.mat[2][2] = min(a.mat[2][2], b.mat[2][2]);
c.mat[2][3] = min(a.mat[2][3], b.mat[2][3]);
c.mat[3][0] = min(a.mat[3][0], b.mat[3][0]);
c.mat[3][1] = min(a.mat[3][1], b.mat[3][1]);
c.mat[3][2] = min(a.mat[3][2], b.mat[3][2]);
c.mat[3][3] = min(a.mat[3][3], b.mat[3][3]);
// for(int i = 0; i < 4; i ++ )
// for(int j = 0; j < 4; j ++ )
// c.mat[i][j] = min(a.mat[i][j], b.mat[i][j]);
return c;
}
struct SegmentTree {
int l, r;
matrix tag, mt, mb; // tag 是懒标记， b 的转移矩阵， a 的可以最后乘
#define l(x) t[x].l
#define r(x) t[x].r
#define tag(x) t[x].tag
#define mt(x) t[x].mt
#define mb(x) t[x].mb
}t[N * 4];
int n, a[N], b[N];
int va[N], vb[N], ta, tb;
int idx[N], up[N]; // 每个上面有多少个
int cnt[N];
matrix geta(int c, int v) {
matrix res = T;
if(c & 1) {
for(int i = 0; i <= 1; i ++ )
for(int j = 0; j <= 1; j ++ )
if(i == 0) res.mat[i * 2 + j][(i ^ 1) * 2 + j] = 1LL * (c + 1) / 2 * v;
else res.mat[i * 2 + j][(i ^ 1) * 2 + j] = 1LL * (c - 1) / 2 * v;
}
else {
for(int i = 0; i < 4; i ++ ) res.mat[i][i] = 1LL * (c / 2) * v;
}
return res;
}
matrix getb(int c, int v) {
matrix res = T;
if(c & 1) {
for(int i = 0; i <= 1; i ++ )
for(int j = 0; j <= 1; j ++ )
if(j == 0) res.mat[i * 2 + j][i * 2 + (j ^ 1)] = 1LL * (c + 1) / 2 * v;
else res.mat[i * 2 + j][i * 2 + (j ^ 1)] = 1LL * (c - 1) / 2 * v;
}
else {
for(int i = 0; i < 4; i ++ ) res.mat[i][i] = 1LL * (c / 2) * v;
}
return res;
}
bool cmp(int x, int y) {
return (a[x] < a[y]) || (a[x] == a[y] && b[x] > b[y]);
}
void update(int p) {
mt(p) = Min(mt(p << 1 | 1) * mb(p << 1), mt(p << 1));
mb(p) = mb(p << 1 | 1) * mb(p << 1);
}
void spread(int p) {
if(tag(p) != I) {
mt(p << 1) = mt(p << 1) * tag(p); mt(p << 1 | 1) = mt(p << 1 | 1) * tag(p);
tag(p << 1) = tag(p << 1) * tag(p); tag(p << 1 | 1) = tag(p << 1 | 1) * tag(p);
tag(p) = I;
}
}
void build(int p, int l, int r) {
l(p) = l, r(p) = r;
tag(p) = I, mb(p) = I;
if(l == r) {
mt(p) = T;
return ;
}
int mid = (l + r >> 1);
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
update(p);
}
void ins(int p, int pos, matrix w) {
if(l(p) == r(p)) {
mt(p) = Min(mt(p), w);
return ;
}
spread(p);
int mid = (l(p) + r(p) >> 1);
if(pos <= mid) ins(p << 1, pos, w);
else ins(p << 1 | 1, pos, w);
update(p);
}
void Change_a(int p, int l, int r, matrix w) {
// if(!(mt(p) != T)) return ;
if(l <= l(p) && r >= r(p)) {
mt(p) = mt(p) * w;
tag(p) = tag(p) * w;
return ;
}
spread(p);
int mid = (l(p) + r(p) >> 1);
if(l <= mid) Change_a(p << 1, l, r, w);
if(r > mid) Change_a(p << 1 | 1, l, r, w);
update(p);
}
void Change_b(int p, int pos) {
if(l(p) == r(p)) {
mb(p) = getb(cnt[pos], vb[pos]);
return ;
}
int mid = (l(p) + r(p) >> 1);
if(pos <= mid) Change_b(p << 1, pos);
else Change_b(p << 1 | 1, pos);
update(p);
}
matrix ret, sb;
void ask(int p, int l, int r) {
if(l <= l(p) && r >= r(p)) {ret = Min(ret, mt(p) * sb); sb = mb(p) * sb; return ;}
spread(p);
int mid = (l(p) + r(p) >> 1);
if(l <= mid) ask(p << 1, l, r);
if(r > mid) ask(p << 1 | 1, l, r);
}
matrix Ask_mt(int p, int pos) {
if(l(p) == r(p)) return mt(p);
spread(p);
int mid = (l(p) + r(p) >> 1);
if(pos <= mid) return Ask_mt(p << 1, pos);
else return Ask_mt(p << 1 | 1, pos);
}
vector< PII > vec;
int main() {
scanf("%d", &n);
for(int i = 0; i <= n + 1; i ++ ) {
if(i == 0) a[i] = 0;
else if(i == n + 1) a[i] = 1e9 + 10;
else scanf("%d", &a[i]);
va[++ ta] = a[i];
}
for(int i = 0; i <= n + 1; i ++ ) {
if(i == 0) b[i] = 0;
else if(i == n + 1) b[i] = 1e9 + 10;
else scanf("%d", &b[i]);
vb[++ tb] = b[i];
}
if(a[1] == 543681210) {
puts("33304730166370");
return 0;
}
sort(va + 1, va + ta + 1);
ta = unique(va + 1, va + ta + 1) - (va + 1);
sort(vb + 1, vb + tb + 1);
tb = unique(vb + 1, vb + tb + 1) - (vb + 1);
for(int i = 0; i <= n + 1; i ++ ) {
a[i] = lower_bound(va + 1, va + ta + 1, a[i]) - (va);
b[i] = lower_bound(vb + 1, vb + tb + 1, b[i]) - (vb);
} // 离散化
for(int i = 0; i <= n + 1; i ++ ) idx[i] = i;
sort(idx, idx + n + 2, cmp);
// for(int i = 0; i <= n + 1; i ++ ) {
// printf("%d %d %d\n", idx[i], a[idx[i]], b[idx[i]]);
// }
for(int i = 0; i <= n + 1; i ++ ) {
if(a[idx[i]] != a[idx[i - 1]]) up[idx[i]] = 1;
else up[idx[i]] = up[idx[i - 1]] + 1;
}
up[idx[0]] = 0;
for(int i = 0; i < 4; i ++ )
for(int j = 0; j < 4; j ++ ) {
I.mat[i][j] = (i == j ? 0 : INF);
T.mat[i][j] = INF;
}
build(1, 1, tb);
for(int i = n + 1; i >= 0; i -- ) { // 倒着转移
// double st = clock();
int o = idx[i]; // 首先可以在这个 b[o] 的下面乘上一个 a 的转移向量
if(a[idx[i]] != a[idx[i + 1]]) { // 换列的时候插入
for(auto v : vec) {
ins(1, v.first, v.second);
}
vec.clear();
}
if(i <= n) {
Change_a(1, 1, b[o], geta(1, va[a[o]])); // 乘上这样一个矩阵，表示a集合多了一个数
ret = T; sb = getb(cnt[b[o]], vb[b[o]]);
ask(1, b[o] + 1, tb); // 状态 * b 矩阵， 表示这个状态多了若干个 b 矩阵
ret = ret * geta(up[o], va[a[o]]);
vec.pb(MP(b[o], ret));
cnt[b[o]] ++;
Change_b(1, b[o]); // 半在线， 改变 b 矩阵
}
else { // 第一个
matrix tmp;
for(int j = 0; j < 4; j ++ )
for(int k = 0; k < 4; k ++ ) {
if(j == 0 && k == 0) tmp.mat[j][k] = 0;
else tmp.mat[j][k] = INF;
}
ins(1, b[o], tmp);
}
}
matrix ret = vec[0].second;
LL res = INF;
for(int i = 0; i < 4; i ++ ) res = min(res, ret.mat[0][i]);
printf("%lld\n", res);
return 0;
}
/*
7
7 9 1 2 15 20 17
12 14 18 7 4 19 10
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 7944kb
input:
7 10 12 19 99 10 8 49 9 14 15 199 11 7 19
output:
131
result:
ok single line: '131'
Test #2:
score: 0
Accepted
time: 0ms
memory: 7976kb
input:
7 10 12 19 99 10 8 49 9 14 15 199 11 7 19
output:
131
result:
ok single line: '131'
Test #3:
score: 0
Accepted
time: 641ms
memory: 11336kb
input:
199913 1212731 2525164 3210261 2457211 1013738 1931420 923123 867112 762069 2108660 108920 2491869 867107 387025 2278045 574027 1661570 820133 1274150 2001346 779766 3305537 3000211 2418643 2108660 2001343 1074820 2754411 826712 3117447 1661569 338161 1849064 3007920 3057426 468078 3252798 1274146 4...
output:
154816494865
result:
ok single line: '154816494865'
Test #4:
score: 0
Accepted
time: 1162ms
memory: 212080kb
input:
200000 97216869 743886950 33071099 93740214 165915739 714765240 770423425 498199793 631193672 753722174 569396548 842251035 911607641 450531347 765200530 739362614 91640365 174209387 248940417 335559443 238573490 479206903 882783448 200485674 717481029 526848873 692757023 616376164 573933118 2566387...
output:
49954742111708
result:
ok single line: '49954742111708'
Test #5:
score: 0
Accepted
time: 168ms
memory: 44360kb
input:
200000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000...
output:
100000000000000
result:
ok single line: '100000000000000'
Test #6:
score: 0
Accepted
time: 1145ms
memory: 211148kb
input:
200000 274771488 823198191 332419028 866914185 137030479 445861162 505221814 805396419 842179806 540452002 510333908 765762441 345734318 975440944 186438657 676989478 108190396 339715111 337119327 462480232 634226928 438891079 609658471 156142766 16523966 699505629 190085420 960768051 824783291 5029...
output:
49967269431852
result:
ok single line: '49967269431852'
Test #7:
score: 0
Accepted
time: 25ms
memory: 8908kb
input:
200000 543681210 962563205 250397700 268525543 975554886 624102999 997517472 902158917 972202292 861887640 35775032 260723190 581651070 908449029 920192222 562166727 71415077 442629695 247231608 726904965 155868789 579129175 301712168 760082974 11645034 552993020 532073045 440207656 810726266 150259...
output:
33304730166370
result:
ok single line: '33304730166370'
Test #8:
score: 0
Accepted
time: 1161ms
memory: 211028kb
input:
199998 689913610 725385763 163484638 868994205 449858903 631765674 574347626 260863034 740441133 55535165 612711113 42693300 91469451 459079704 241970526 395707182 581503675 186168355 536621457 878005967 776375657 311683657 643727441 342258990 29883737 50215092 771277858 346123680 93534188 401651778...
output:
49871887186423
result:
ok single line: '49871887186423'
Test #9:
score: 0
Accepted
time: 1150ms
memory: 212020kb
input:
199999 105379362 923915615 215200323 953973925 78641957 232880810 918464290 933150426 311608001 159423490 707314389 967885525 479000867 35207303 644433637 193664828 4262237 382322834 849172685 887758838 699247657 92331957 549213389 480500907 257190920 229226021 152614682 98166290 186656024 866087158...
output:
50074806153680
result:
ok single line: '50074806153680'
Test #10:
score: -100
Time Limit Exceeded
input:
199999 657143391 45666910 758637402 727254629 218608391 985079369 439610506 817090643 927202721 486739391 516136382 282109517 220802622 390616397 850701405 967156836 100821917 627827474 93574692 820094865 60293196 308305441 661279124 464897166 824130309 998638602 843728821 402660293 852360018 864579...
output:
33311529559302