QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#106480 | #6337. Mizuyokan 2 | oscaryang | 0 | 10ms | 31636kb | C++17 | 3.4kb | 2023-05-17 21:23:56 | 2023-05-17 21:24:00 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define vc vector
#define pb emplace_back
#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(2,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(1,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;
}
int 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(1,x-lim);i--) get_rp(i);
modify(1,1,n,max(1,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: 3ms
memory: 31540kb
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: 7ms
memory: 31588kb
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: 10ms
memory: 31616kb
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: 6ms
memory: 31624kb
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: 7ms
memory: 31636kb
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: 7ms
memory: 31568kb
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: 10ms
memory: 31552kb
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: 31632kb
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: 9ms
memory: 31516kb
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%