oj.uz

Submission #626709

# Submission time Handle Problem Language Result Execution time Memory
626709 2022-08-11T16:50:30 Z lovrot Addk (eJOI21_addk) C++11
100 / 100
 211 ms 14524 KB 
#include <bits/stdc++.h> 
#include <unistd.h>

#define X first
#define Y second
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define vec vector
#define pri(i, poc, n, pov) for(int i = (int) poc; i < (int) n; i += (int) pov)
#define od(i, poc, n, pov) for(int i = (int) poc; i > (int) n; i -= (int) pov)

using namespace std;

const int LOG = 17;
const int OFF = (1 << LOG);

struct node{ 
	ll len = 0;
	ll sum = 0;
	ll dsc = 0;
	ll asc = 0;
	node(){};
} tour[OFF * 2];

int n, q, c;
ll niz[OFF];
pair<ll, ll> cir[20];

node merge(node a, node b){ 
	node ret;
	ret.len = a.len + b.len;
	ret.sum = a.sum + b.sum;
	ret.asc = a.asc + a.len * b.sum + b.asc;
	ret.dsc = a.dsc + b.len * a.sum + b.dsc;
	return ret;
}

void update(int x, ll val){ 
	x += OFF;
	tour[x].sum = tour[x].asc = tour[x].dsc = val;
	x >>= 1;
	while(x){ 
		tour[x] = merge(tour[x * 2], tour[x * 2 + 1]);
		x >>= 1;
	}
}

node query(int l, int r, int lo = 0, int hi = OFF, int x = 1) {
	if(r <= lo || hi <= l) return node();
	if(l <= lo && hi <= r) return tour[x];
	int mi = (lo + hi) / 2;
	return merge(query(l, r, lo, mi, x * 2), query(l, r, mi, hi, x * 2 + 1));
}

void init(){ 
	cin >> n >> c;
	pri(i, 0, n, 1){ 
		cin >> niz[i];
		tour[i + OFF].len = 1;
		tour[i + OFF].sum = tour[i + OFF].asc = tour[i + OFF].dsc = niz[i];
	}
	od(i, OFF - 1, 0, 1) tour[i] = merge(tour[i * 2], tour[i * 2 + 1]);
}

int nxt(int x){ 
	return (x + c + 1) % c;
}

int main(){ 
	ios_base::sync_with_stdio(false); 
	cin.tie(0);
	cout.tie(0);

	init();

	cin >> q;

	pri(i, 0, q, 1) {
		int t;
		cin >> t;
		if(t == 1){ 
			pri(j, 0, c, 1){
				int x;
				cin >> x;
				x--;
				cir[j] = {x, niz[x]};	
			} 
			pri(j, 0, c, 1){ 
				niz[cir[j].X] = cir[nxt(j)].Y;
				update(cir[j].X, niz[cir[j].X]);
			}	
			// cout << "updated: "; pri(j, 0, n, 1) cout << niz[j] << " "; cout << "\n";
		} else { 
			ll l, r, m, ans = 0;
			cin >> l >> r >> m;
			l--;
			r--; 

			if(r - l + 1 >= m * 2 - 1) {
				ans = query(l, (l + m - 1)).asc + m * query(l + m - 1, r - m + 2).sum + query(r - m + 2, r + 1).dsc; 
				// cout << l << " / " << l + m - 2 << " = " << query(l, (l + m - 1)).asc << "\n";
			} else { 
				ll mx_l = r - m + 1;
				ll mx_r = l + m - 1;
				ll mx = r - mx_r + 1;
				ans = query(l, mx_l).asc + mx * query(mx_l, mx_r + 1).sum + query(mx_r + 1, r + 1).dsc;
				//cout << mx_l << " --- " << mx_r + 1 << " = " << query(mx_l, mx_r + 1).dsc << "\n";
			}
			cout << ans << "\n";
		}

	}
	return 0;
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8532 KB Output is correct
2 Correct 6 ms 8532 KB Output is correct
3 Correct 8 ms 8532 KB Output is correct
4 Correct 10 ms 8660 KB Output is correct
5 Correct 10 ms 8800 KB Output is correct
6 Correct 12 ms 8768 KB Output is correct
7 Correct 13 ms 8788 KB Output is correct
8 Correct 15 ms 8820 KB Output is correct
9 Correct 24 ms 8884 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 8840 KB Output is correct
2 Correct 53 ms 9796 KB Output is correct
3 Correct 90 ms 10336 KB Output is correct
4 Correct 151 ms 11776 KB Output is correct
5 Correct 200 ms 13336 KB Output is correct
6 Correct 166 ms 12956 KB Output is correct
7 Correct 179 ms 13028 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 9296 KB Output is correct
2 Correct 163 ms 12620 KB Output is correct
3 Correct 211 ms 14524 KB Output is correct
4 Correct 189 ms 13520 KB Output is correct