QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #865997 | #9986. Shiori | Hanghang | WA | 102ms | 11876kb | C++20 | 2.2kb | 2025-01-22 10:26:54 | 2025-01-22 10:27:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+3,M=1<<20|3,INF=1e9;
ll n,m,a[N],mn[M],mx[M],sum[M],tag[M];
vector<array<ll,4>>res;
#define ls (p<<1)
#define rs (p<<1|1)
#define mi ((l+r)>>1)
#define lson ls,l,mi
#define rson rs,mi+1,r
void Up(int p)
{
sum[p]=sum[ls]+sum[rs];
mn[p]=min(mn[ls],mn[rs]);
mx[p]=max(mx[ls],mx[rs]);
}
void Build(int p=1,int l=1,int r=n)
{
tag[p]=-1;
if(l==r){mn[p]=mx[p]=a[l];return;}
Build(lson);Build(rson);Up(p);
}
void Add(ll d,int p,int l,int r){tag[p]=mn[p]=mx[p]=d;sum[p]=d*(r-l+1);}
void Down(int p,int l,int r){if(tag[p]!=-1)Add(tag[p],lson),Add(tag[p],rson),tag[p]=-1;}
void Upd(int L,int R,ll d,int p=1,int l=1,int r=n)
{
if(L<=l&&r<=R)return Add(d,p,l,r);
Down(p,l,r);
if(L<=mi)Upd(L,R,d,lson);
if(R>mi)Upd(L,R,d,rson);
Up(p);
}
ll Ask(int L,int R,int p=1,int l=1,int r=n)
{
if(L<=l&&r<=R)return sum[p];
Down(p,l,r);
if(R<=mi)return Ask(L,R,lson);
if(L>mi)return Ask(L,R,rson);
return Ask(L,R,lson)+Ask(L,R,rson);
}
ll Mn(int L,int R,int p=1,int l=1,int r=n)
{
if(L<=l&&r<=R)return mn[p];
Down(p,l,r);
if(R<=mi)return Mn(L,R,lson);
if(L>mi)return Mn(L,R,rson);
return min(Mn(L,R,lson),Mn(L,R,rson));
}
void Dfs(int L,int R,ll d,int p=1,int l=1,int r=n)
{
if(L<=l&&r<=R)
{
if(mn[p]>d)return;
if(mx[p]==d)
{
res.push_back({d,p,l,r});Add(INF,p,l,r);
return;
}
}
Down(p,l,r);
if(L<=mi)Dfs(L,R,d,lson);
if(R>mi)Dfs(L,R,d,rson);
Up(p);
}
void Mdf(int L,int R,ll d,int p=1,int l=1,int r=n)
{
if(L<=l&&r<=R)
{
if(mn[p]==mx[p])return Add(mn[p]+d,p,l,r);
}
Down(p,l,r);
if(L<=mi)Mdf(L,R,d,lson);
if(R>mi)Mdf(L,R,d,rson);
Up(p);
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
Build();
while(m--)
{
ll op,l,r,d;cin>>op>>l>>r;
if(op==1){cin>>d;Upd(l,r,d);continue;}
if(op==3){cout<<Ask(l,r)<<"\n";continue;}
ll s=0,las=l;res.clear();
while(Mn(l,r)==s)Dfs(l,r,s++);
sort(res.begin(),res.end(),[](array<ll,4>A,array<ll,4>B){return A[2]<B[2];});
for(auto t:res)
{
if(t[2]>las)Mdf(las,t[2]-1,s);
int p=t[1];las=t[3]+1;Add(t[0]+s,p,t[2],t[3]);
while(p>1)Up(p>>=1);
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9956kb
input:
5 8 0 7 2 1 0 1 2 4 0 2 1 3 2 3 4 3 1 3 1 2 3 4 3 1 4 2 1 5 3 2 5
output:
5 11 22
result:
ok 3 number(s): "5 11 22"
Test #2:
score: 0
Accepted
time: 0ms
memory: 11876kb
input:
1 1 0 1 1 1 0
output:
result:
ok 0 number(s): ""
Test #3:
score: -100
Wrong Answer
time: 102ms
memory: 9828kb
input:
10 500000 0 0 0 0 0 0 0 0 0 0 3 2 9 2 4 10 2 2 7 2 7 9 3 1 1 3 5 8 1 5 10 0 3 1 9 3 5 9 2 2 4 1 2 4 0 2 5 6 3 8 8 1 4 6 0 1 6 6 0 2 4 10 3 1 9 3 5 7 1 4 10 0 3 6 9 3 2 6 2 1 8 1 5 9 0 3 7 8 3 4 8 2 4 8 2 5 8 2 1 9 2 3 8 1 5 10 0 2 4 8 3 1 6 2 1 4 2 3 7 3 4 10 1 4 6 0 1 1 6 0 2 3 7 1 1 1 0 2 1 10 1 5...
output:
0 0 10 7 0 0 6 3 0 0 0 1 25 12 10 0 0 0 0 17 17 1 15 2 8 20 19 2 18 2 2 0 0 0 2 4 1 0 0 0 7 2 0 4 32 15 7 11 0 4 5 2 8 5 1 6 0 7 0 7 6 3 2 5 0 0 0 7 14 2 5 0 2 0 0 6 12 6 0 3 4 0 0 1 16 12 1 1 12 0 3 4 4 10 3 16 0 17 2 4 0 0 16 8 2 8 18 23 2 24 4 12 7 4 14 5 0 2 6 4 15 8 4 6 22 15 1 4 3 0 2 5 0 2 0 ...
result:
wrong answer 21st numbers differ - expected: '23', found: '17'