QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#208241 | #4269. Rainy Markets | lmeowdn | 0 | 2ms | 18360kb | C++14 | 3.5kb | 2023-10-09 11:46:30 | 2023-10-09 11:46:30 |
Judging History
answer
//vanitas vanitatum et omnia
#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=1e6+5;
int n,a[N],p[N],u[N],ans,g[N],h[N];
namespace SegT {
int ls[N<<1],rs[N<<1],tot=1,tag[N<<1],s[N<<1];
void add(int p,int z) {s[p]+=z;}
void psd(int p) {
add(ls[p],tag[p]), add(rs[p],tag[p]);
tag[p]=0;
}
void build(int p,int l,int r) {
if(l==r) return; int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
}
void add(int p,int l,int r,int x,int y,int z) {
//if(p==1) cout<<"ADD "<<x<<" "<<y<<" "<<z<<endl;
if(l==x&&r==y) {add(p,z); return;}
int mid=l+r>>1; psd(p);
if(y<=mid) add(ls[p],l,mid,x,y,z);
else if(x>mid) add(rs[p],mid+1,r,x,y,z);
else add(ls[p],l,mid,x,mid,z), add(rs[p],mid+1,r,mid+1,y,z);
s[p]=min(s[ls[p]],s[rs[p]]);
}
void mdf(int p,int l,int r,int x,int y) {
//if(p==1) cout<<"MDF "<<x<<" "<<y<<endl;
if(l==r) {s[p]=y; return;} int mid=l+r>>1; psd(p);
if(x<=mid) mdf(ls[p],l,mid,x,y);
else mdf(rs[p],mid+1,r,x,y);
s[p]=min(s[ls[p]],s[rs[p]]);
}
int qry(int p,int l,int r,int x,int y) {
if(l==x&&r==y) return s[p]; int mid=l+r>>1; psd(p);
if(y<=mid) return qry(ls[p],l,mid,x,y);
else if(x>mid) return qry(rs[p],mid+1,r,x,y);
else return min(qry(ls[p],l,mid,x,mid),qry(rs[p],mid+1,r,mid+1,y));
}
}
signed main() {
n=read(); n--;
rep(i,1,n+1) a[i]=read();
rep(i,1,n) g[i]=p[i]=read();
rep(i,1,n) h[i]=u[i]=read();
SegT::build(1,1,n);
stack<int>q;
rep(i,1,n) {
if(a[i]>=p[i]) {a[i]-=p[i]; continue;}
p[i]-=a[i], a[i]=0;
if(a[i+1]>=p[i]) {
a[i+1]-=p[i], SegT::mdf(1,1,n,i,p[i]);
q.push(i); continue;
}
SegT::mdf(1,1,n,i,a[i+1]);
p[i]-=a[i+1], a[i+1]=0;
if(u[i]>=p[i]) {
u[i]-=p[i], ans+=p[i];
q.push(i); continue;
}
p[i]-=u[i], ans+=u[i], u[i]=0;
while(!q.empty()&&p[i]) {
int x=q.top(); q.pop();
int y=min(u[x],p[i]);
chmin(y,SegT::qry(1,1,n,x,i-1));
SegT::add(1,1,n,x,i-1,-y);
u[x]-=y, p[i]-=y, ans+=y;
}
if(p[i]) return puts("No"), 0;
q.push(i);
}
printf("YES\n%d\n",ans);
rep(i,1,n) {
int fr=SegT::qry(1,1,n,i,i);
int fu=h[i]-u[i];
int fl=g[i]-fr-fu;
printf("%d %d %d\n",fl,fu,fr);
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 18136kb
input:
3 10 15 10 20 20 0 0
output:
No
result:
wrong answer read 'No' but expected 'NO'
Subtask #2:
score: 0
Wrong Answer
Test #36:
score: 5
Accepted
time: 0ms
memory: 18056kb
input:
3 10 15 10 20 20 0 11
output:
YES 5 10 0 10 5 5 10
result:
ok good plan
Test #37:
score: 0
Accepted
time: 2ms
memory: 18360kb
input:
4 5 3 1 2 7 6 2 3 2 4
output:
YES 4 5 2 0 3 2 1 0 0 2
result:
ok good plan
Test #38:
score: 0
Accepted
time: 0ms
memory: 14268kb
input:
2 25 58 103 25
output:
YES 20 25 20 58
result:
ok good plan
Test #39:
score: 0
Accepted
time: 0ms
memory: 14104kb
input:
2 400 400 121 200
output:
YES 0 121 0 0
result:
ok good plan
Test #40:
score: -5
Wrong Answer
time: 2ms
memory: 17980kb
input:
2000 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 9...
output:
No
result:
wrong answer read 'No' but expected 'NO'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%