QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#106484#6337. Mizuyokan 2oscaryang0 0ms0kbC++173.5kb2023-05-17 21:26:492023-05-17 21:26:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-17 21:26:53]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-05-17 21:26:49]
  • 提交

answer

#include<bits/stdc++.h>

#define ll long long
#define vc vector
#define pb emplace_back
#define int long long
#define mem(a) memset(a,0,sizeof(a))
#define memu(a) memset(a,0x3f,sizeof(a))
#define memd(a) memset(a,-0x3f,sizeof(a))

using namespace std;
const int N=3e5+5,P=998244353,lim=70;
const int inf=0x3f3f3f3f;

//in&out
inline int read() {
    int x=0,w=0; char ch=getchar(); while(!isdigit(ch)) w|=(ch=='-'), ch=getchar();
    while(isdigit(ch)) x=x*10+(ch^48), ch=getchar(); return w?-x:x;
}
inline void write(int x) { if(x<0) putchar('-'), x=-x; if(x>9) write(x/10); putchar(x%10+'0'); }
inline void writee(int x) { write(x); putchar(10); }
inline void writec(int x) { write(x); putchar(32); }

//calc
inline void inc(int &x,int y) { x+=y-P; x+=(x>>31)&P; }
inline void dec(int &x,int y) { x-=y;   x+=(x>>31)&P; }
inline int pls(int x,int y) { return x+=y-P, x+=(x>>31)&P, x; }
inline void Min(int &x,int y) { if(x>y) x=y; }
inline void Max(int &x,int y) { if(x<y) x=y; }

int n,a[N],lp[N],rp[N];

inline void get_lp(int x) {
    for(int i=x-1,s=a[i];i>=max(2ll,x-lim+1);i--,s+=a[i]) 
        if(s>max(a[x],a[i-1])) return lp[x]=i-1, void();
    lp[x]=0;
}
inline void get_rp(int x) {
    for(int i=x+1;i<=x+lim;i++)
        if(lp[i]>=x) return rp[x]=i, void();
    rp[x]=n+1;
}

//segment_tree 
#define mid (l+r>>1)
#define ls (k<<1)
#define rs (k<<1|1)
vc<pair<int,int> > tre[N<<2];
vc<tuple<int,int,int> > seq;
inline void psu(int k,int l,int r) {
    tre[k].clear();
    for(int i=l;i<=min(r,l+lim);i++) 
        if(i<=mid) {
            auto [p,d]=tre[ls][i-l];
            if(rp[p]<=r) {
                auto [nx,di]=tre[rs][rp[p]-mid-1];
                p=nx; d+=di+1;
            }
            tre[k].pb(p,d);
        }
        else tre[k].pb(tre[rs][i-mid-1]);
}
inline void build(int k,int l,int r) { 
    if(l==r) return tre[k].pb(l,0), void();
    build(ls,l,mid); build(rs,mid+1,r); psu(k,l,r);
}
inline void modify(int k,int l,int r,int L,int R) {
    if(L>R || L>r || R<l || l==r) return ;
    modify(ls,l,mid,L,R); modify(rs,mid+1,r,L,R); psu(k,l,r);
}
inline void ask(int k,int l,int r,int L,int R) {
    if(L>R || L>r || R<l) return ;
    if(L<=l && R>=r) return seq.pb(k,l,r), void();
    ask(ls,l,mid,L,R); ask(rs,mid+1,r,L,R);
}

inline void get_st(vc<int> &A,int x) {
    int s=a[x]; A.pb(x);
    for(int i=x+1;i<=min(n,x+lim);i++,s+=a[i])
        if(s>a[i]) A.pb(i);
}
inline void get_ed(vc<int> &A,int x) {
    int s=a[x]; A.pb(x);
    for(int i=x-1;i>=max(1ll,x-lim);i--,s+=a[i])
        if(s>a[i]) A.pb(i);
}

inline int query(int L,int R) {
    int x=L,d=0; 
    seq.clear(); ask(1,1,n,L,R);
    for(auto [k,l,r]:seq) if(x<=r) {
        auto [nx,di]=tre[k][x-l];
        x=nx; d+=di;
        if(rp[x]>R) return d;
        x=rp[nx]; ++d;
    }
    return d;
}

signed main() {
    freopen("a.in","r",stdin);
    n=read(); for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) get_lp(i);
    for(int i=1;i<=n;i++) get_rp(i);
    build(1,1,n);
    int Q=read(),x,y,l,r,ans; 
    while(Q--) {
        x=read(); y=read(); l=read()+1; r=read(); 
        a[x]=y; 
        for(int i=x;i<=min(n,x+lim);i++) get_lp(i);
        for(int i=x;i>=max(1ll,x-lim);i--) get_rp(i);
        modify(1,1,n,max(1ll,x-lim),x);
        vc<int> st,ed; ans=1;
        get_st(st,l);  get_ed(ed,r);
        for(auto L:st) for(auto R:ed) if(L<=R) 
            Max(ans,2*query(L,R)+1+(L!=l)+(R!=r));
        writee(ans);
    }
    return 0;
}

詳細信息

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

170
581553716 290776853 145388421 581553716 168947671 936760822 849346471 126291564 133104657 125887494 136786623 123143788 137803872 129733949 849346471 880499329 202732710 611312524 152828126 305656257 611312524 121295297 6875889 74507235 419967909 333601507 281557968 740824934 370412466 185206229...

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Time Limit Exceeded

Test #59:

score: 0
Time Limit Exceeded

input:

185137
895278847 447639418 223819705 895278847 25847602 892542542 725274571 68345857 72124244 67050536 71135605 66549838 72378749 66083078 72261084 67667076 70423484 68942136 725274571 798132375 68764887 958288578 703862250 55104628 58120315 54690522 57110282 54279470 56516680 54581941 58474132 5445...

output:


result:


Subtask #5:

score: 0
Time Limit Exceeded

Test #76:

score: 0
Time Limit Exceeded

input:

235469
96936 48463 24226 96936 25951 73765 63933 7121 7884 7166 7731 7464 7559 7300 7767 7314 63933 88750 6093 115886 111307 16371 17529 15944 17376 16099 18186 15910 111307 116042 13997 111982 95565 10713 11748 10849 11375 11093 11406 10874 11810 11197 95565 98914 1302 65917 16473 32953 65917 15943...

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #1:

0%