QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#208241#4269. Rainy Marketslmeowdn0 2ms18360kbC++143.5kb2023-10-09 11:46:302023-10-09 11:46:30

Judging History

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

  • [2023-10-09 11:46:30]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:18360kb
  • [2023-10-09 11:46:30]
  • 提交

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%