← Real problems

ioi01p1

easyfenwick2ddata-structuresStatement on DMOJ

CP Lang

13 lineschecks
// ioi01p1 Mobile Phones: point additions and rectangle sums on an s by s grid, until command 3.
let (_, s) = read<(0..=0, 1..=1_024)>()
domain X = 0..s
var phones = Fenwick2D<X, X, Int>()
enum Cmd:
    @tag("1") Add(x: X, y: X, a: Int)
    @tag("2") Ask(l: X, b: X, r: X, t: X)
    @tag("3") Stop
while true:
    match read<Cmd>():
        Add(x, y, a) => phones.add(x, y, a)
        Ask(l, b, r, t) => print(phones.fold(l..=r, b..=t))
        Stop => break

Accepted C++

175 lines · 0.38 s on the judge
#include "bits/stdc++.h"

using namespace std;

//sad; long long double doesn't exist
using ld = long double;

//imagine a language where int = long
#define long long long

//typing too hard
#define endl "\n"

#define sz(x) int((x).size())

//const int maxn = 1024, tmaxn = maxn * 2 + 1;
//
//int n;
//int v[tmaxn][tmaxn];
//
//void update2(int xo, int o, int l, int r, int ind, int x) {
//	v[xo][o] += x;
//	if(l < r) {
//		int mid = (l + r) / 2;
//		if(ind <= mid) {
//			update2(xo, o * 2, l, mid, ind, x);
//		}else {
//			update2(xo, o * 2 + 1, mid + 1, r, ind, x);
//		}
//	}
//}
//
//void update1(int o, int l, int r, int i, int j, int x) {
//	update2(o, 1, 0, n - 1, j, x);
//	if(l < r) {
//		int mid = (l + r) / 2;
//		if(i <= mid) {
//			update1(o * 2, l, mid, i, j, x);
//		}else {
//			update1(o * 2 + 1, mid + 1, r, i, j, x);
//		}
//	}
//}
//
//void update(int i, int j, int x) {
//	update1(1, 0, n - 1, i, j, x);
//}
//
//int query2(int xo, int o, int l, int r, int ql, int qr) {
//	if(ql <= l && r <= qr) {
//		return v[xo][o];
//	}else {
//		int ans = 0;
//		int mid = (l + r) / 2;
//		if(ql <= mid) {
//			ans += query2(xo, o * 2, l, mid, ql, qr);
//		}
//		if(qr > mid) {
//			ans += query2(xo, o * 2 + 1, mid + 1, r, ql, qr);
//		}
//		return ans;
//	}
//}
//
//int query1(int o, int l, int r, int x1, int y1, int x2, int y2) {
//	if(x1 <= l && r <= x2) {
//		return query2(o, 1, 0, n - 1, y1, y2);
//	}else {
//		int ans = 0;
//		int mid = (l + r) / 2;
//		if(x1 <= mid) {
//			ans += query1(o * 2, l, mid, x1, y1, x2, y2);
//		}
//		if(x2 > mid) {
//			ans += query1(o * 2 + 1, mid + 1, r, x1, y1, x2, y2);
//		}
//		return ans;
//	}
//}
//
//int query(int x1, int y1, int x2, int y2) {
//	return query1(1, 0, n - 1, x1, y1, x2, y2);
//}
//
//void init() {
//	memset(v, 0, sizeof(v));
//}
//
//mt19937 cowng(chrono::steady_clock::now().time_since_epoch().count());
//
//void stress() {
//	n = 1024;
//	init();
//	int q = 6e4;
//	while(q--) {
//		if(cowng() & 1) {
//			int i = cowng() % n, j = cowng() % n, x = cowng() % 1024;
//			update(i, j, x);
//		}else {
//			int x1 = cowng() % n, y1 = cowng() % n, x2 = cowng() % n, y2 = cowng() % n;
//			query(x1, y1, x2, y2);
//		}
//	}
//}

const int maxn = 1024;

int n;
int bit[maxn + 1][maxn + 1];

void update2(int i, int j, int x) {
	int ind = j + 1;
	while(ind <= n) {
		bit[i][ind] += x;
		ind += ind & -ind;
	}
}

void update(int i, int j, int x) {
	int ind = i + 1;
	while(ind <= n) {
		update2(ind, j, x);
		ind += ind & -ind;
	}
}

int psum2(int i, int j) {
	int ind = j, ans = 0;
	while(ind > 0) {
		ans += bit[i][ind];
		ind -= ind & -ind;
	}
	return ans;
}

int psum(int i, int j) {
	int ind = i, ans = 0;
	while(ind > 0) {
		ans += psum2(ind, j);
		ind -= ind & -ind;
	}
	return ans;
}

int query(int x1, int y1, int x2, int y2) {
	return psum(x2 + 1, y2 + 1) - psum(x1, y2 + 1) - psum(x2 + 1, y1) + psum(x1, y1);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::failbit);
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
//	for(int i = 0; i < 10000; i++) {
//		stress();
//	}
#endif
	while(true) {
		int type;
		cin >> type;
		if(type == 0) {
			cin >> n;
		}else if(type == 1) {
			int i, j, x;
			cin >> i >> j >> x;
			update(i, j, x);
		}else if(type == 2) {
			int x1, y1, x2, y2;
			cin >> x1 >> y1 >> x2 >> y2;
			cout << query(x1, y1, x2, y2) << endl;
		}else {
			break;
		}
	}
}