QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#572071 | #9222. Price Combo | DaiRuiChen007 | WA | 185ms | 52232kb | C++17 | 2.3kb | 2024-09-18 11:42:12 | 2024-09-18 11:42:13 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
const ll inf=1e18;
typedef array<array<ll,2>,2> Info;
struct Tag { int o;array<ll,2> s; };
Info operator +(const Info &X,const Info &Y) {
return {min(X[0][0],Y[0][0]),min(X[0][1],Y[0][1]),min(X[1][0],Y[1][0]),min(X[1][1],Y[1][1])};
}
Tag operator +(const Tag &X,const Tag &Y) {
return {X.o^Y.o,X.s[0]+Y.s[X.o],X.s[1]+Y.s[X.o^1]};
}
Info mulA(const Info &I,const Tag &Y) {
int c=Y.o;
return {I[c][0]+Y.s[c],I[c][1]+Y.s[c],I[c^1][0]+Y.s[c^1],I[c^1][1]+Y.s[c^1]};
}
Info mulB(const Info &I,const Tag &Y) {
int c=Y.o;
return {I[0][c]+Y.s[c],I[0][c^1]+Y.s[c^1],I[1][c]+Y.s[c],I[1][c^1]+Y.s[c^1]};
}
int n,vb[MAXN];
struct SegmentTree {
Info F[MAXN<<2];
Tag A[MAXN<<2],B[MAXN<<2];
void adt(int p,Tag T) { A[p]=A[p]+T,F[p]=mulA(F[p],T); }
void psd(int p) { adt(p<<1,A[p]),adt(p<<1|1,A[p]),A[p]={0,0,0}; }
void psu(int p) { B[p]=B[p<<1]+B[p<<1|1],F[p]=mulB(F[p<<1],B[p<<1|1])+F[p<<1|1]; }
void init(int l=0,int r=n,int p=1) {
if(l==r) {
F[p]={inf,inf,inf,inf},B[p]={1,0,vb[l]};
if(!l) F[p]={0,0,0,0};
return ;
}
int mid=(l+r)>>1;
init(l,mid,p<<1),init(mid+1,r,p<<1|1),psu(p);
}
void mul(int ul,int ur,Tag T,int l=0,int r=n,int p=1) {
if(ul<=l&&r<=ur) return adt(p,T);
int mid=(l+r)>>1; psd(p);
if(ul<=mid) mul(ul,ur,T,l,mid,p<<1);
if(mid<ur) mul(ul,ur,T,mid+1,r,p<<1|1);
psu(p);
}
void upd(int u,Info I,int l=0,int r=n,int p=1) {
if(l==r) return F[p]=I,B[p]={0,0,0},void();
int mid=(l+r)>>1;
u<=mid?upd(u,I,l,mid,p<<1):upd(u,I,mid+1,r,p<<1|1);
psu(p);
}
void qry(int ul,int ur,Info &I,int l=0,int r=n,int p=1) {
if(ul<=l&&r<=ur) return I=mulB(I,B[p])+F[p],void();
int mid=(l+r)>>1; psd(p);
if(ul<=mid) qry(ul,ur,I,l,mid,p<<1);
if(mid<ur) qry(ul,ur,I,mid+1,r,p<<1|1);
}
} T;
struct Z {
int a,b;
} a[MAXN];
signed main() {
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i].a);
for(int i=1;i<=n;++i) scanf("%d",&a[i].b);
sort(a+1,a+n+1,[&](Z i,Z j){ return i.b<j.b; });
for(int i=1;i<=n;++i) vb[i]=a[i].b,a[i].b=i;
sort(a+1,a+n+1,[&](Z i,Z j){ return i.a^j.a?i.a<j.b:i.b<j.b; });
T.init();
for(int i=1;i<=n;++i) {
Info I={inf,inf,inf,inf};
T.qry(0,a[i].b,I),T.upd(a[i].b,I);
T.mul(0,a[i].b-1,{1,0,a[i].a});
}
printf("%lld\n",T.F[1][0][0]);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5992kb
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: 1ms
memory: 5876kb
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: 185ms
memory: 52232kb
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:
154801476954
result:
wrong answer 1st lines differ - expected: '154816494865', found: '154801476954'