| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 613766 |
2022-07-30T10:33:26 Z |
karelisp |
Addk (eJOI21_addk) |
C++14 |
|
138 ms |
3912 KB |
#include <bits/stdc++.h>
using namespace std;
int N, K, Q;
long long a[100005], pf1[100005], pf2[100005];
struct SegTree{
long long st[400005];
void update(int pos, long long val, int v=1, int start=1, int end=N){
if(start==end){
st[v] = val;
return;
}
int mid = (start+end)/2;
if(pos<=mid) update(pos, val, 2*v, start, mid);
else update(pos, val, 2*v+1, mid+1, end);
st[v] = st[2*v] + st[2*v+1];
}
long long query(int l, int r, int v=1, int start=1, int end=N){
if(l>r)
return 0;
if(l==start && r==end)
return st[v];
int mid = (start+end)/2;
if(r<=mid) return query(l, r, 2*v, start, mid);
else if(l>mid) return query(l, r, 2*v+1, mid+1, end);
else return query(l, mid, 2*v, start, mid) + query(mid+1, r, 2*v+1, mid+1, end);
}
}st_sum, st_mulsum;
long long sum(int l, int r){
return st_sum.query(l,r);
}
long long mulsum(int l, int r){
return st_mulsum.query(l,r);
}
long long answer(long long int l, long long int r, long long m){
if(2*m <= r-l+1){
long long S1 = mulsum(l, l+m-1) + (1-l)*sum(l, l+m-1);
long long S2 = m * sum(l+m, r-m);
long long S3 = (r+1) * sum(r-m+1, r) - mulsum(r-m+1, r);
return S1 + S2 + S3;
}
else{
int d = r-l+1-m;
long long S1 = mulsum(l, l+d-1) + (1-l)*sum(l, l+d-1);
long long S2 = (d+1)*sum(l+d, r-d);
long long S3 = (r+1)*sum(r-d+1, r) - mulsum(r-d+1, r);
return S1 + S2 + S3;
}
}
int main(){
scanf("%d%d", &N, &K);
for(long long i=1; i<=N; i++){
scanf("%lld", &a[i]);
st_sum.update(i, a[i]);
st_mulsum.update(i, i*a[i]);
}
scanf("%d", &Q);
for(int l,r,m,op,q=0; q<Q; q++){
scanf("%d", &op);
if(op==1){
int cur, prev;
scanf("%d",&prev);
int first_val = st_sum.query(prev, prev);
for(int i= 2 ; i <= K ; i++)
{
scanf("%d",&cur);
long long A_cur = st_sum.query(cur, cur);
st_sum.update(prev, A_cur);
st_mulsum.update(prev, prev*A_cur);
prev = cur;
}
st_sum.update(prev, first_val);
st_mulsum.update(prev, prev*first_val);
}
else{
scanf("%d%d%d", &l, &r, &m);
printf("%lld\n", answer(l,r,m));
}
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | scanf("%d%d", &N, &K);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | scanf("%lld", &a[i]);
| ~~~~~^~~~~~~~~~~~~~~
Main.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%d", &Q);
| ~~~~~^~~~~~~~~~
Main.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | scanf("%d", &op);
| ~~~~~^~~~~~~~~~~
Main.cpp:73:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | scanf("%d",&prev);
| ~~~~~^~~~~~~~~~~~
Main.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | scanf("%d",&cur);
| ~~~~~^~~~~~~~~~~
Main.cpp:88:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | scanf("%d%d%d", &l, &r, &m);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
392 KB |
Output is correct |
| 3 |
Correct |
3 ms |
468 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
468 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
1832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
138 ms |
3912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
