| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 833673 |
2023-08-22T07:43:28 Z |
dshfjka |
Addk (eJOI21_addk) |
C++14 |
|
277 ms |
15708 KB |
#include <bits/stdc++.h>
#define LL long long
#define mp make_pair
#define fi first
#define se second
#define int long long
using namespace std;
LL n;
const LL maxn=1e5+5;
LL arr[maxn+5];
struct Segtree {
LL inc[4*maxn+5],dec[4*maxn+5],sum[4*maxn+5];
LL N;
void init(LL x)
{
// printf("SININININ\n");
N=x;
// printf("N=%lld\n",N);
}
LL combine(LL x, LL y) {
return x+y;
}
void build(int v, int s, int e) {
// printf("%lld %lld %lld\n",v,s,e);
if (s == e) {
sum[v] =arr[s];
inc[v]=arr[s]*s;
dec[v]=arr[s]*(N+1-e);
// printf("%lld=%lld*(%lld+1-%lld)\n",dec[v],arr[s],N,e);
} else {
int mid = (s + e) >> 1;
build(v << 1, s, mid);
build(v << 1 | 1, mid + 1, e);
sum[v] = combine(sum[v << 1], sum[v << 1 | 1]);
inc[v] = combine(inc[v << 1], inc[v << 1 | 1]);
dec[v] = combine(dec[v << 1], dec[v << 1 | 1]);
// printf("dec[%lld]=%lld\n",v,dec[v]);
}
// printf("t[%lld]=%lld\n",v,t[v]);
}
pair<LL,pair<LL,LL>> get(int v, int s, int e, int l, int r) {
if (e < l || s > r || l > r)
return make_pair(0LL,mp(0,0));
if (l <= s && e <= r)
return mp(sum[v],mp(inc[v],dec[v]));
int mid = (s + e) >> 1;
auto p1 = get(v << 1, s, mid, l, r);
auto p2 = get(v << 1 | 1, mid + 1, e, l, r);
LL temp =combine(p1.fi, p2.fi);
LL temp2=combine(p1.se.fi,p2.se.fi);
LL temp3=combine(p1.se.se,p2.se.se);
return mp(temp,mp(temp2,temp3));
}
void update(LL v, LL l, LL r,LL x,LL idx)
{
if( l==r){
sum[v] =idx;
inc[v]=idx*l;
dec[v]=idx*(N+1-r);
// printf("x=%lld t[%lld]=%lld\n",x,v,t[v]);
return;
}
LL mid=(l+r)/2;
if(x<=mid)update(v<<1,l,mid,x,idx);
else update(v<<1 |1,mid+1,r,x,idx);
sum[v] = combine(sum[v << 1], sum[v << 1 | 1]);
inc[v] = combine(inc[v << 1], inc[v << 1 | 1]);
dec[v] = combine(dec[v << 1], dec[v << 1 | 1]);
}
};
signed main()
{
LL n,k;
scanf("%lld %lld",&n,&k);
Segtree s;
for(LL a=1;a<=n;a++)
{
scanf("%lld",&arr[a]);
}
s.init(n);
s.build(1,1,n);
LL q;
scanf("%lld",&q);
while(q--)
{
LL type;
scanf("%lld",&type);
if(type==1)
{
LL temp[k+5];
for(LL x=1;x<=k;x++)
{
LL y;
scanf("%lld",&y);
temp[x]=y;
}
LL dorr=temp[1];
LL dor=arr[temp[1]];
for(LL x=1;x<=k;x++)
{
if(x!=k)
{
arr[temp[x]]=arr[temp[x+1]];
s.update(1,1,n,temp[x],arr[temp[x]]);
}
else
{
arr[temp[x]]=dor;
s.update(1,1,n,temp[x],dor);
}
}
// for(LL a=1;a<=n;a++)printf("%lld ",arr[a]);
// cout<<endl;
}
else
{
// sum increment decrement
LL l,r,m;
scanf("%lld %lld %lld",&l,&r,&m);
LL ans=0;
if(l+m-1<r-m+1)
{
// dia tidak bersinggungan
// printf("SINI\n");
ans+=s.get(1,1,n,l,l+m-2).se.fi-s.get(1,1,n,l,l+m-2).fi*(l-1);
// printf("ans1= %lld\n",ans);
ans+=s.get(1,1,n,l+m-1,r-m+1).fi*m;
// printf("ans2 = %lld\n",ans);
ans+=s.get(1,1,n,r-m+2,r).se.se-s.get(1,1,n,r-m+2,r).fi*(n-r);
// printf("ans3= %lld-%lld*%lld\n",s.get(1,1,n,r-m+2,r).se.se,s.get(1,1,n,r-m+2,r).fi,(n-r));
}
else
{
// printf("MASUK\n");
ans+=s.get(1,1,n,l,r-m).se.fi-s.get(1,1,n,l,r-m).fi*(l-1);
// printf("ans1=%lld-%lld*%lld\n",s.get(1,1,n,l,r-m).se.fi,s.get(1,1,n,l,r-m).fi,(l-1));
// printf("ans1= %lld\n",ans);
ans+=s.get(1,1,n,r-m+1,l+m-1).fi*(r-l-m+2);
// printf("ans2+=%lld*%lld=%lld\n",s.get(1,1,n,r-m+1,l+m-1).fi,(r-l-m+2),ans);
ans+=s.get(1,1,n,l+m,r).se.se-s.get(1,1,n,l+m,r).fi*(n-r);
// printf("ans3=%lld-%lld*%lld\n",s.get(1,1,n,l+m,r).se.se,s.get(1,1,n,l+m,r).fi,(n-r));
}
printf("%lld\n",ans);
}
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:100:7: warning: unused variable 'dorr' [-Wunused-variable]
100 | LL dorr=temp[1];
| ^~~~
Main.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf("%lld %lld",&n,&k);
| ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%lld",&arr[a]);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | scanf("%lld",&q);
| ~~~~~^~~~~~~~~~~
Main.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
90 | scanf("%lld",&type);
| ~~~~~^~~~~~~~~~~~~~
Main.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | scanf("%lld",&y);
| ~~~~~^~~~~~~~~~~
Main.cpp:122:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
122 | scanf("%lld %lld %lld",&l,&r,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9720 KB |
Output is correct |
| 4 |
Correct |
8 ms |
9812 KB |
Output is correct |
| 5 |
Correct |
10 ms |
9812 KB |
Output is correct |
| 6 |
Correct |
12 ms |
9892 KB |
Output is correct |
| 7 |
Correct |
16 ms |
9844 KB |
Output is correct |
| 8 |
Correct |
16 ms |
9988 KB |
Output is correct |
| 9 |
Correct |
22 ms |
10072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
10468 KB |
Output is correct |
| 2 |
Correct |
70 ms |
10984 KB |
Output is correct |
| 3 |
Correct |
91 ms |
11488 KB |
Output is correct |
| 4 |
Correct |
164 ms |
13116 KB |
Output is correct |
| 5 |
Correct |
231 ms |
14452 KB |
Output is correct |
| 6 |
Correct |
211 ms |
14184 KB |
Output is correct |
| 7 |
Correct |
211 ms |
14132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
12352 KB |
Output is correct |
| 2 |
Correct |
199 ms |
13876 KB |
Output is correct |
| 3 |
Correct |
224 ms |
15708 KB |
Output is correct |
| 4 |
Correct |
277 ms |
14712 KB |
Output is correct |
