QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#106485#6337. Mizuyokan 2oscaryang0 13ms31660kbC++173.5kb2023-05-17 21:27:292023-05-17 21:27:33

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:27:33]
  • 评测
  • 测评结果:0
  • 用时:13ms
  • 内存:31660kb
  • [2023-05-17 21:27:29]
  • 提交

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() {
    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
Wrong Answer

Test #1:

score: 6
Accepted
time: 4ms
memory: 31612kb

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:

59
56
61
61
56
37
42
46

result:

ok 8 numbers

Test #2:

score: 0
Accepted
time: 13ms
memory: 31652kb

input:

200
517847507 258923750 129461870 517847507 106915073 712580593 512811829 12657894 12715954 12534704 12759073 12554236 12685369 12563357 12817887 12534566 12752501 12518874 12746471 12524663 12730053 12586182 12803851 12628464 12778716 12645600 12701929 12550298 12754947 12548765 12765210 12592487 1...

output:

118
162
114
113
143
105
109
165
139
152

result:

ok 10 numbers

Test #3:

score: 0
Accepted
time: 8ms
memory: 31604kb

input:

156
689580506 344790254 172395128 689580506 344790254 689580506 344790252 172395125 86197561 86197567 86197565 86197566 43098784 86197566 86197565 86197567 86197561 172395125 344790252 689580506 344790254 689580506 172395128 344790254 689580506 3985467 453082635 861305238 430652620 215326311 8613052...

output:

19
26
27
21
15
11

result:

ok 6 numbers

Test #4:

score: 0
Accepted
time: 5ms
memory: 31556kb

input:

200
545371756 272685879 136342940 545371756 272685879 545371756 272685877 136342937 68171467 68171474 68171472 68171473 34085737 68171473 68171472 68171474 68171467 136342937 272685877 545371756 272685879 545371756 136342940 272685879 545371756 327464463 455363267 859187150 429593576 214796789 85918...

output:

27
36
25
26
16
11
15
21
19
22

result:

ok 10 numbers

Test #5:

score: 0
Accepted
time: 8ms
memory: 31616kb

input:

200
433494437 165580141 63245986 24157817 9227465 3524578 1346269 514229 196418 75025 28657 10946 4181 1597 610 233 89 34 13 5 2 1 1 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 832040 2178309 5702887 14930352 39088169 102334155 267914296 701408733 863735928 433494437 165580141 632459...

output:

5
13
5
5
8
5
13
5
5
6

result:

ok 10 numbers

Test #6:

score: 0
Accepted
time: 5ms
memory: 31572kb

input:

187
433494437 165580141 63245986 24157817 9227465 3524578 1346269 514229 196418 75025 28657 10946 4181 1597 610 233 89 34 13 5 2 1 1 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 832040 2178309 5702887 14930352 39088169 102334155 267914296 701408733 868260277 433494437 165580141 632459...

output:

4
36
18
10
19
11
3
29

result:

ok 8 numbers

Test #7:

score: 0
Accepted
time: 8ms
memory: 31652kb

input:

200
942616273 418940008 209470430 104734784 104734784 104735481 523675545 247785 701408733 267914296 102334155 39088169 14930352 5702887 2178309 832040 317811 121393 46368 17711 6765 2584 987 377 144 55 21 8 3 1 1 1 2 5 13 34 89 233 610 1597 4181 10946 28657 75025 196418 514229 1346269 3524578 92274...

output:

5
21
8
5
9
8
20
17
5
5

result:

ok 10 numbers

Test #8:

score: 0
Accepted
time: 4ms
memory: 31660kb

input:

200
641304094 22086510 5470810 2634455 1317187 658631 329083 126285 49415 22321 11410 5273 359 133 50 20 9 3 3 3 9 30 79 220 585 1226 2467 4851 27355 76469 202803 2836339 8307675 16614893 38701275 77401954 154804637 309608784 619217509 353775485 433494437 165580141 63245986 24157817 9227465 3524578 ...

output:

5
13
9
9
9
4
12
12
11
5

result:

ok 10 numbers

Test #9:

score: -6
Wrong Answer
time: 7ms
memory: 31576kb

input:

200
433494437 165580141 63245986 24157817 9227465 3524578 1346269 514229 196418 75025 28657 10946 4181 1597 610 233 89 34 13 5 2 1 1 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 832040 2178309 5702887 14930352 39088169 102334155 267914296 701408733 693739790 701408733 267914296 102334...

output:

5
5
5
4
5
5
11
19
10
17

result:

wrong answer 6th numbers differ - expected: '3', found: '5'

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:

59
26
80
55
43
41
79
37
57
79
69
29
31
25
26
76
32
25
28
36
34
39
67
40
67
71
45
40
49
52
64
61
29
40
39
34
41
19
28
51
31
43
62
23
31
26
73
39
63
36
53
27
46
56
30
67
61
37
71
22
42
59
67
87
16
27
20
39
14
64
20
19
41
34
55
53
15
51
43
30
71
60
49
9
76
18
86
29
73
61
38
46
21
62
20
20
67
71
83
82
5...

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:

34
56
73
61
41
13
74
46
33
33
14
53
36
46
18
63
65
79
72
15
21
57
66
83
19
46
62
58
44
76
76
68
41
56
9
29
59
73
64
21
63
33
29
62
27
36
20
65
54
71
29
47
13
32
48
74
64
75
79
17
25
49
20
41
57
17
23
67
67
19
19
54
63
74
72
45
61
30
27
61
33
36
49
49
24
56
42
60
20
53
32
76
44
57
17
34
71
45
25
39
2...

result:


Subtask #6:

score: 0
Skipped

Dependency #1:

0%