| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1032138 |
2024-07-23T12:25:19 Z |
ten_xd |
Addk (eJOI21_addk) |
C++17 |
|
59 ms |
9196 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back
const int N = 1e5+5, INF = 2e9+54321, base = (1<<17), rozmiar_drzewa = base * 2;
const ll INF_L = (ll)2e18+54321;
int n,k,q;
int A[N];
vector<ll> tree, tree2, tree3;
void update(int v, int val)
{
ll val1 = (ll)val * (v+1), val2 = (ll)val * (n-v);
v += base, tree[v] = val1, tree2[v] = val2, tree3[v] = val, v /= 2;
while(v > 0) tree[v] = tree[v*2] + tree[v*2+1], tree2[v] = tree2[v*2] + tree2[v*2+1], tree3[v] = tree3[v*2] + tree3[v*2+1], v /= 2;
}
ll query3(int l, int p)
{
int la = l, pa = p;
l = l + base - 1, p = p + base + 1;
ll res = 0;
while(l/2 != p/2)
{
if(l % 2 == 0) res += tree3[l+1];
if(p % 2 == 1) res += tree3[p-1];
l /= 2, p /= 2;
}
//cout << '\n';
//cout << "LLL: " << la << " PPP: " << pa << " RES: " << res << '\n';
//cout << '\n';
return res;
}
ll query(int l, int p)
{
ll res = -(ll)l * query3(l,p);
//cout << '\n';
//cout << "LL: " << l << " P: " << p << " RES: " << res << '\n';
l = l + base - 1, p = p + base + 1;
while(l/2 != p/2)
{
if(l % 2 == 0) res += tree[l+1];
if(p % 2 == 1) res += tree[p-1];
l /= 2, p /= 2;
}
//cout << "L: " << l << " P: " << p << " RES: " << res << '\n';
//cout << '\n';
return res;
}
ll query2(int l, int p)
{
ll res = -(ll)(n-p-1) * query3(l,p);
//cout << '\n';
//cout << "LL2: " << l << " P: " << p << " RES: " << res << '\n';
l = l + base - 1, p = p + base + 1;
while(l/2 != p/2)
{
if(l % 2 == 0) res += tree2[l+1];
if(p % 2 == 1) res += tree2[p-1];
l /= 2, p /= 2;
}
//cout << "L2: " << l << " P: " << p << " RES: " << res << '\n';
//cout << '\n';
return res;
}
void solve()
{
cin >> n >> k;
rep(i,n) cin >> A[i];
tree.assign(rozmiar_drzewa,0), tree2.assign(rozmiar_drzewa,0), tree3.assign(rozmiar_drzewa,0);
rep(i,n) update(i,A[i]);
cin >> q;
while(q--)
{
int dec;
cin >> dec;
if(dec == 1)
{
vector<int> V, H;
V.assign(k,-1), H.assign(k,-1);
rep(i,k) cin >> V[i], --V[i], H[i] = A[V[i]];
int val = A[V[0]];
for(int i = 0; i < k-1; ++i) A[V[i]] = A[V[i+1]], update(V[i],A[V[i]]);
A[V[k-1]] = val, update(V[k-1],A[V[k-1]]);
}
else
{
int l,p,m,len;
cin >> l >> p >> m;
--l, --p, len = p-l+1;
if(len >= 2*m-1)
{
ll wyn = query(l,l+m-2) + query2(p-m+2,p) + query3(l+m-1,p-(m-1)) * (ll)m;
cout << wyn << '\n';
}
else
{
int idx = p-m+1, dl = idx-l+1;
ll wyn = query(l,idx) + query2(p-idx+1,p);
if(idx+1 <= p-idx) wyn += query3(idx+1,p-idx) * (ll)dl;
cout << wyn << '\n';
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int T = 1;
//cin >> T;
while(T--) solve();
return 0;
}
Compilation message
Main.cpp: In function 'll query3(int, int)':
Main.cpp:25:6: warning: unused variable 'la' [-Wunused-variable]
25 | int la = l, pa = p;
| ^~
Main.cpp:25:14: warning: unused variable 'pa' [-Wunused-variable]
25 | int la = l, pa = p;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
7244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
9196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
