oj.uz

Submission #1032145

# Submission time Handle Problem Language Result Execution time Memory
1032145 2024-07-23T12:26:48 Z ten_xd Addk (eJOI21_addk) C++17
100 / 100
 117 ms 12172 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-dl+1,p);
				if(idx+1 <= p-dl) wyn += query3(idx+1,p-dl) * (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;
      |              ^~

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 4 ms 6492 KB Output is correct
4 Correct 5 ms 6748 KB Output is correct
5 Correct 5 ms 6748 KB Output is correct
6 Correct 7 ms 6780 KB Output is correct
7 Correct 7 ms 6748 KB Output is correct
8 Correct 8 ms 6748 KB Output is correct
9 Correct 11 ms 7004 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 7372 KB Output is correct
2 Correct 30 ms 7772 KB Output is correct
3 Correct 38 ms 8272 KB Output is correct
4 Correct 67 ms 9480 KB Output is correct
5 Correct 98 ms 10972 KB Output is correct
6 Correct 96 ms 10576 KB Output is correct
7 Correct 90 ms 10580 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 8932 KB Output is correct
2 Correct 83 ms 10392 KB Output is correct
3 Correct 117 ms 12172 KB Output is correct
4 Correct 104 ms 11124 KB Output is correct