QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#864297 | #9311. Protection War | niucard | TL | 1204ms | 8532kb | C++14 | 4.2kb | 2025-01-20 14:15:19 | 2025-01-20 14:15:19 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,q,a[300010],len,l[1010],r[1010],id[300010];
long long b1[1010],b2[1010],c[300010];
set<pair<int,int> > s;
void Add(int L,int R,long long y)
{
b2[id[L]]-=c[L]*L,b2[id[R+1]]-=c[R+1]*(R+1);
c[L]+=y,c[R+1]-=y;
b1[id[L]]+=y,b1[id[R+1]]-=y;
b2[id[L]]+=c[L]*L,b2[id[R+1]]+=c[R+1]*(R+1);
}
long long ask(int L,int R)
{
long long num1=0,num2=0;
if(L!=1)
{
for(int i=1;i<id[L-1];i++)
num1+=b1[i]*L-b2[i];
for(int i=l[id[L-1]];i<L;i++)
num1+=L*c[i]-i*c[i];
}
for(int i=1;i<id[R];i++)
num2+=b1[i]*(R+1)-b2[i];
for(int i=l[id[R]];i<=R;i++)
num2+=(R+1)*c[i]-i*c[i];
return num2-num1;
}
void bh()
{
set<pair<int,int> >::iterator it=s.begin();
while(it!=s.end())
{
pair<int,int> x=(*it);
if(x.second!=n)
{
Add(x.second,x.second,-ask(x.second,x.second));
s.erase(it);
if(x.first!=x.second)
{
it=(s.insert(make_pair(x.first,x.second-1))).first;
it++;
}
else
it=s.lower_bound(make_pair(x.first,0));
}
else
it++;
}
}
int main()
{
// freopen("cin.in","r",stdin);
// freopen("out.out","w",stdout);
memset(l,0x3f,sizeof l);
scanf("%d%d",&n,&q);
len=1000;
for(int i=1;i<=n;i++)
{
id[i]=(i-1)/len+1;
l[id[i]]=min(l[id[i]],i),r[id[i]]=max(r[id[i]],i);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
Add(i,i,a[i]);
}
s.insert(make_pair(1,n));
while(q--)
{
int op;
scanf("%d",&op);
if(op==1)
{
int x,y;
scanf("%d%d",&x,&y);
Add(x,x,y-ask(x,x));
if(y)
{
set<pair<int,int> >::iterator it=s.upper_bound(make_pair(x,1e9)),itt;
if(it!=s.begin())
it--;
else
{
if(it==s.end()||(*it).first>x+1)
s.insert(make_pair(x,x));
else
{
int R=(*it).second;
s.erase(it);
s.insert(make_pair(x,R));
}
bh();
continue;
}
if((*it).second>=x)
{
bh();
continue;
}
itt=it,it++;
pair<int,int> x1=(*itt),x2=(*it);
if(x1.second+1==x&&x2.first-1==x)
{
it++;
s.erase(itt,it);
s.insert(make_pair(x1.first,x2.second));
}
else if(x1.second+1==x)
{
s.erase(itt);
s.insert(make_pair(x1.first,x));
}
else if(x2.first-1==x)
{
s.erase(it);
s.insert(make_pair(x,x2.second));
}
else
s.insert(make_pair(x,x));
}
else
{
set<pair<int,int> >::iterator it=s.upper_bound(make_pair(x,1e9)),itt;
if(it!=s.begin())
it--;
else
{
bh();
continue;
}
if((*it).second<x)
{
bh();
continue;
}
pair<int,int> x1=(*it);
s.erase(it);
if(x1.first==x)
{
if(x1.first!=x1.second)
s.insert(make_pair(x1.first+1,x1.second));
}
else if(x1.second==x)
s.insert(make_pair(x1.first,x1.second-1));
else
{
s.insert(make_pair(x1.first,x-1));
s.insert(make_pair(x+1,x1.second));
}
}
}
else if(op==2)
{
int L,R,v;
scanf("%d%d%d",&L,&R,&v);
Add(L,R,v);
set<pair<int,int> >::iterator it1=s.lower_bound(make_pair(L,0)),it2=s.upper_bound(make_pair(R,1e9)),it3;
if(it2!=s.begin())
{
it3=it2;
it3--;
R=max(R,(*it3).second);
}
s.erase(it1,it2);
it1=(s.insert(make_pair(L,R))).first;
if(it1!=s.begin())
{
it2=it1;
it1--;
pair<int,int> x=(*it1);
if(x.second>=L-1)
{
it2++;
s.erase(it1,it2);
it1=(s.insert(make_pair(x.first,R))).first;
}
else
it1=it2;
}
it2=it1,it1++;
if(it1!=s.end())
{
pair<int,int> x=(*it1),y=(*it2);
if(x.first<=R+1)
{
it1++;
s.erase(it2,it1);
s.insert(make_pair(y.first,x.second));
}
}
}
else if(op==3)
{
for(set<pair<int,int> >::iterator it=s.begin();it!=s.end();it++)
{
pair<int,int> x=(*it);
Add(x.first,x.second,1);
}
}
else if(op==4)
{
for(set<pair<int,int> >::iterator it=s.begin();it!=s.end();it++)
{
pair<int,int> x=(*it);
Add(x.first,x.second,x.second-x.first+1);
}
}
else
{
int L,R;
scanf("%d%d",&L,&R);
printf("%lld\n",ask(L,R));
}
bh();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5964kb
input:
10 8 1 2 3 4 5 6 7 8 9 10 1 5 0 4 5 1 10 2 1 7 10 5 1 7 1 5 0 3 5 1 7
output:
74 97 71
result:
ok 3 number(s): "74 97 71"
Test #2:
score: 0
Accepted
time: 310ms
memory: 5960kb
input:
500 300000 20001 40132 29212 16930 79791 32181 87513 9436 61594 60199 23626 56049 76877 26228 46852 90808 52774 97868 84080 20953 39737 27635 93897 50290 59947 50049 48449 69397 73015 60257 27292 82311 2349 40210 30130 62403 95726 30729 28690 69685 48849 16781 91994 30976 22114 43258 99392 77848 384...
output:
1777087 6304031 39352977 61099409 15756683 31610555 44754327 12487869 59587103 2013274 3787120 9520811 30097273 0 29379053 97470237 16716946 10173160 60903053 77967400 42424120 82321580 1362621 19339692 48461160 173887621 191344136 26872842 98980145 89270173 54079590 73055561 53268415 64611723 21370...
result:
ok 60308 numbers
Test #3:
score: 0
Accepted
time: 305ms
memory: 5964kb
input:
500 300000 3661 36740 51832 61516 76116 24936 6180 33534 84366 8372 97227 47341 2526 19922 41191 86094 37721 71264 99337 54956 80744 56721 73555 85761 89738 85868 62174 27710 74319 38092 35510 44105 96574 35486 72952 53626 88784 66790 47099 37245 17138 48570 66404 18867 14727 93189 20368 208 92836 9...
output:
14046143 20948450 2866449 26237759 17432940 22077719 42448823 6203132 42995489 13023558 83271628 46227856 14594620 72259746 31434457 53554700 57705358 17165033 162671227 128280776 146609232 133716010 94318636 13656985 73755685 8630665 77502753 144457801 106411744 8636969 186415804 59188599 141850862...
result:
ok 59918 numbers
Test #4:
score: 0
Accepted
time: 1114ms
memory: 8532kb
input:
300000 300000 57451 36906 78465 95706 19070 48873 54372 46322 22034 19942 23717 25586 79904 74145 51471 62558 50792 70621 4724 68730 47246 26210 7754 60498 54168 7614 62761 36563 92242 46335 69583 58448 61354 34810 64860 92478 82964 20840 36278 63608 90438 51236 50182 48955 68925 67502 90010 6315 60...
output:
24038355781 17520159076 77426274356 112236455136 233944213210 127898744311 175688445771 426885053349 239002345886 22295671469 136802216849 462348680839 382946706667 801141945001 573484605895 173524140651 14447679142 630305728424 9442569891 261017396115 1080207552674 110655277820 340172946827 1636415...
result:
ok 59603 numbers
Test #5:
score: 0
Accepted
time: 1204ms
memory: 8532kb
input:
300000 300000 84215 66218 44189 40293 72291 413 40336 37716 44806 820 97317 49582 72849 67839 13106 66357 35739 11313 19982 2733 55549 31105 87412 4481 83959 10729 84999 27581 17737 48362 45097 87537 31387 5894 74978 7892 76021 56901 20096 31167 50215 83025 24593 79950 28835 84729 10986 61379 5950 1...
output:
211281268649 81904713663 107994432954 237079419347 158601219821 374047091474 216749096504 326901757608 269358863804 581445761431 301095611648 206331558554 334116145342 739321744537 93840133893 212593254720 813432938058 263696251557 385499825902 75141830842 74764348483 52704328099 212029381920 806844...
result:
ok 60164 numbers
Test #6:
score: -100
Time Limit Exceeded
input:
300000 300000 7412 76492 94901 3626 78858 87917 49058 88554 92597 75867 27429 17150 46087 10141 39105 55151 34067 21758 7067 86217 65749 79659 86528 76796 45415 16470 84095 63419 53805 89782 83595 24384 44746 66757 53466 4838 91272 40992 89896 71278 65749 15979 31381 12347 82272 80779 48547 79990 90...
output:
13122639444 13095679258 13093395236 13087814669 13053282543 13052721576 13041630291 13016365397 13013741533 12997505496 12989617831 12979637756 12955892310 12951817252 12946528851 12920024861 12915843420 12896461225 12866329898 12869025185 12841320314 12844736862 12821848130 12792783793 12796548834 ...