| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1074391 |
2024-08-25T10:15:51 Z |
MrPavlito |
Addk (eJOI21_addk) |
C++17 |
|
315 ms |
15992 KB |
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
//#define endl "\n"
#define pii pair<int,int>
using namespace std;
const int MAXN = 1e6+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;
int niz[MAXN];
int n;
int seg[MAXN<<2];
int prefseg[MAXN<<2];
int sufseg[MAXN<<2];
void build(int nod, int tl, int tr)
{
if(tl==tr)
{
seg[nod] = niz[tl];
prefseg[nod] = niz[tl]*tl;
sufseg[nod] = niz[tl]*(n- tl+1);
return;
}
int mid = tl+tr>>1;
build(nod<<1, tl, mid);
build(nod<<1|1, mid+1, tr);
seg[nod] = seg[nod<<1] + seg[nod<<1|1];
prefseg[nod] = prefseg[nod<<1] + prefseg[nod<<1|1];
sufseg[nod] = sufseg[nod<<1] + sufseg[nod<<1|1];
}
void update(int nod, int tl, int tr, int index, int v)
{
if(tl == tr)
{
niz[tl] = v;
seg[nod] = niz[tl];
prefseg[nod] = niz[tl]*tl;
sufseg[nod] = niz[tl]*(n- tl+1);
return;
}
int mid = tl+tr>>1;
if(index<= mid)update(nod<<1, tl, mid, index, v);
else update(nod<<1|1, mid+1, tr, index, v);
seg[nod] = seg[nod<<1] + seg[nod<<1|1];
prefseg[nod] = prefseg[nod<<1] + prefseg[nod<<1|1];
sufseg[nod] = sufseg[nod<<1] + sufseg[nod<<1|1];
}
int querysuf(int nod, int tl, int tr, int l, int r)
{
if(tl> r || tr< l || tl>tr)return 0;
if(tl>=l && tr<=r)return sufseg[nod];
int mid = tl+tr>>1;
return querysuf(nod<<1, tl, mid, l, r) + querysuf(nod<<1|1, mid+1, tr, l, r);
}
int querypref(int nod, int tl, int tr, int l, int r)
{
if(tl> r || tr< l || tl>tr)return 0;
if(tl>=l && tr<=r)return prefseg[nod];
int mid = tl+tr>>1;
int q1 = querypref(nod<<1, tl, mid, l, r);
int q2 = querypref(nod<<1|1, mid+1, tr, l, r);
return q1 + q2;
}
int query(int nod, int tl, int tr, int l, int r)
{
if(tl> r || tr< l || tl>tr)return 0;
if(tl>=l && tr<=r)return seg[nod];
int mid = tl+tr>>1;
return query(nod<<1, tl, mid, l, r) + query(nod<<1|1, mid+1, tr, l, r);
}
signed main()
{
ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
int tt=1;
//cin >> tt;
while(tt--)
{
int q,k;
cin >> n >> k;
for(int i=1; i<=n; i++)cin >> niz[i];
cin >> q;
int svi[k];
build(1,1,n);
while(q--)
{
int t;cin >> t;
if(t == 1)
{
for(int i=0; i<k; i++)cin >> svi[i];
int prvi = niz[svi[0]];
for(int i=0; i<k-1; i++)update(1,1,n, svi[i], niz[svi[i+1]]);
update(1,1,n, svi[k-1], prvi);
}
else
{
int m,l,r;cin >> l >> r >> m;
if(r-l+1 == m)cout << query(1,1,n,l,r) << endl;
else if(m <= (r-l+2)/2)
{
int mid = m-1;
int p1 = querypref(1,1,n, 1, l+mid-1) - querypref(1,1,n,1, l-1)- query(1,1,n,l,l+mid-1)*(l-1);
int p2 = querysuf(1,1,n, r-mid+1, n) - querysuf(1,1,n,r+1, n) - query(1,1,n,r-mid+1,r)*(n-r);
int p3 = query(1,1,n,l+mid, r- mid)*m;
cout << p1+p2+p3 << endl;
}
else
{
int mid = (r-l+1) - m;
int p1 = querypref(1,1,n, 1, l+mid-1) - querypref(1,1,n,1, l-1)- query(1,1,n,l,l+mid-1)*(l-1);
int p2 = querysuf(1,1,n, r-mid+1, n) - querysuf(1,1,n,r+1, n) - query(1,1,n,r-mid+1,r)*(n-r);
int p3 = query(1,1,n,l+mid, r- mid)*(mid+1);
cout << p1+p2+p3 << endl;
}
}
}
}
}
/*
10 1
1 1 1 1 1 1 1 1 1 1
5
2 2 9 6
*/
Compilation message
Main.cpp: In function 'void build(long long int, long long int, long long int)':
Main.cpp:32:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
32 | int mid = tl+tr>>1;
| ~~^~~
Main.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:50:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
50 | int mid = tl+tr>>1;
| ~~^~~
Main.cpp: In function 'long long int querysuf(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:62:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
62 | int mid = tl+tr>>1;
| ~~^~~
Main.cpp: In function 'long long int querypref(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:71:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
71 | int mid = tl+tr>>1;
| ~~^~~
Main.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:81:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
81 | int mid = tl+tr>>1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2652 KB |
Output is correct |
| 4 |
Correct |
7 ms |
4700 KB |
Output is correct |
| 5 |
Correct |
9 ms |
4840 KB |
Output is correct |
| 6 |
Correct |
12 ms |
4952 KB |
Output is correct |
| 7 |
Correct |
13 ms |
4984 KB |
Output is correct |
| 8 |
Correct |
16 ms |
4956 KB |
Output is correct |
| 9 |
Correct |
39 ms |
3420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
6340 KB |
Output is correct |
| 2 |
Correct |
100 ms |
6584 KB |
Output is correct |
| 3 |
Correct |
107 ms |
8020 KB |
Output is correct |
| 4 |
Correct |
199 ms |
11348 KB |
Output is correct |
| 5 |
Correct |
315 ms |
11352 KB |
Output is correct |
| 6 |
Correct |
291 ms |
14420 KB |
Output is correct |
| 7 |
Correct |
278 ms |
11068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
129 ms |
6200 KB |
Output is correct |
| 2 |
Correct |
271 ms |
10720 KB |
Output is correct |
| 3 |
Correct |
251 ms |
15992 KB |
Output is correct |
| 4 |
Correct |
315 ms |
11636 KB |
Output is correct |
