QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#864217#9222. Price CombochangziliangWA 625ms11120kbC++2010.8kb2025-01-20 11:58:182025-01-20 11:58:19

Judging History

你现在查看的是最新测评结果

  • [2025-01-20 11:58:19]
  • 评测
  • 测评结果：WA
  • 用时：625ms
  • 内存：11120kb
查看
  • [2025-01-20 11:58:18]
  • 提交

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 ;
		C.mat[0][0] = min({A.mat[0][0]+B.mat[0][0],A.mat[0][1]+B.mat[1][0],A.mat[0][2]+B.mat[2][0],A.mat[0][3]+B.mat[3][0]}) ;
		C.mat[0][1] = min({A.mat[0][0]+B.mat[0][1],A.mat[0][1]+B.mat[1][1],A.mat[0][2]+B.mat[2][1],A.mat[0][3]+B.mat[3][1]}) ;
		C.mat[0][2] = min({A.mat[0][0]+B.mat[0][2],A.mat[0][1]+B.mat[1][2],A.mat[0][2]+B.mat[2][2],A.mat[0][3]+B.mat[3][2]}) ;
		C.mat[0][3] = min({A.mat[0][0]+B.mat[0][3],A.mat[0][1]+B.mat[1][3],A.mat[0][2]+B.mat[2][3],A.mat[0][3]+B.mat[3][3]}) ;
		
		C.mat[1][0] = min({A.mat[1][0]+B.mat[0][0],A.mat[1][1]+B.mat[1][0],A.mat[1][2]+B.mat[2][0],A.mat[1][3]+B.mat[3][0]}) ;
		C.mat[1][1] = min({A.mat[1][0]+B.mat[0][1],A.mat[1][1]+B.mat[1][1],A.mat[1][2]+B.mat[2][1],A.mat[1][3]+B.mat[3][1]}) ;
		C.mat[1][2] = min({A.mat[1][0]+B.mat[0][2],A.mat[1][1]+B.mat[1][2],A.mat[1][2]+B.mat[2][2],A.mat[1][3]+B.mat[3][2]}) ;
		C.mat[1][3] = min({A.mat[1][0]+B.mat[0][3],A.mat[1][1]+B.mat[1][3],A.mat[1][2]+B.mat[2][3],A.mat[1][3]+B.mat[3][3]}) ;
		
		C.mat[2][0] = min({A.mat[2][0]+B.mat[0][0],A.mat[2][1]+B.mat[1][0],A.mat[2][2]+B.mat[2][0],A.mat[2][3]+B.mat[3][0]}) ;
		C.mat[2][1] = min({A.mat[2][0]+B.mat[0][1],A.mat[2][1]+B.mat[1][1],A.mat[2][2]+B.mat[2][1],A.mat[2][3]+B.mat[3][1]}) ;
		C.mat[2][2] = min({A.mat[2][0]+B.mat[0][2],A.mat[2][1]+B.mat[1][2],A.mat[2][2]+B.mat[2][2],A.mat[2][3]+B.mat[3][2]}) ;
		C.mat[2][3] = min({A.mat[2][0]+B.mat[0][3],A.mat[2][1]+B.mat[1][3],A.mat[2][2]+B.mat[2][3],A.mat[2][3]+B.mat[3][3]}) ;
		
		C.mat[3][0] = min({A.mat[3][0]+B.mat[0][0],A.mat[3][1]+B.mat[1][0],A.mat[3][2]+B.mat[2][0],A.mat[3][3]+B.mat[3][0]}) ;
		C.mat[3][1] = min({A.mat[3][0]+B.mat[0][1],A.mat[3][1]+B.mat[1][1],A.mat[3][2]+B.mat[2][1],A.mat[3][3]+B.mat[3][1]}) ;
		C.mat[3][2] = min({A.mat[3][0]+B.mat[0][2],A.mat[3][1]+B.mat[1][2],A.mat[3][2]+B.mat[2][2],A.mat[3][3]+B.mat[3][2]}) ;
		C.mat[3][3] = min({A.mat[3][0]+B.mat[0][3],A.mat[3][1]+B.mat[1][3],A.mat[3][2]+B.mat[2][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(l > r) return ;
//	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(pos <= 0 || pos > tb) return ;
	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() {
//	freopen("data.in", "r", stdin);
//	freopen("data.out", "w", stdout);
	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];
	}
	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 ++ ) {
		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 -- ) { // 倒着转移 
	    int o = idx[i]; // 首先可以在这个 b[o] 的下面乘上一个 a 的转移向量 
		if(i <= n) {
			ret = T; sb = getb(cnt[b[o]], vb[b[o]]); 
			ask(1, b[o] + 1, tb); // 状态 * b 矩阵， 表示这个状态多了若干个 b 矩阵
			ins(1, b[o], ret); // 插入ret 
		    if(i > 0) Change_a(1, 1, b[o], geta(1, va[a[o]])); // 乘上这样一个矩阵，表示a集合多了一个数
			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);
		}
//		cout << "KKK" << ' ' << i << endl;
//		for(int j = 1; j <= tb; j ++ ) {
//			matrix f = Ask_mt(1, j);
//			for(int k = 0; k < 3; k ++ ) printf("f[%d][%d] = %lld\n", j, k, f.mat[0][k]);
//		}
	}
	matrix ret = Ask_mt(1, 1);
	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 

7
10 12 19 99 10 8 49
9 14 15 199 11 7 19
*/
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5968kb

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: 5964kb

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: -100
Wrong Answer
time: 625ms
memory: 11120kb

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:

154296514469

result:

wrong answer 1st lines differ - expected: '154816494865', found: '154296514469'
English 繁體中文 简体中文

Server Time: 2025-02-01 15:58:50 | OpenSource Project