oj.uz

Submission #813852

# Submission time Handle Problem Language Result Execution time Memory
813852 2023-08-08T04:12:47 Z GEN 이지후(#10370) Posters on the wall (CPSPC17_posters) C++17
80 / 100
 137 ms 18420 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
const int MAXN = 800005;
int mod;

using pi = array<lint, 2>;

struct fen {
	pi tree[MAXN];
	void add(int x, pi v) {
		for (int i = x + 2; i < MAXN; i += i & -i) {
			tree[i][0] += v[0];
			tree[i][1] += v[1];
		}
	}
	pi query(int x) {
		pi v{0, 0};
		for (int i = x + 2; i; i -= i & -i) {
			v[0] += tree[i][0];
			v[1] += tree[i][1];
		}
		return v;
	}
};

vector<int> v;

struct bit {
	fen fwt;
	void rangeAdd(int l, int r, lint z) {
		fwt.add(l, pi{z, -z * lint(v[l])});
		fwt.add(r, pi{-z, z * lint(v[r])});
	}
	lint query(int x) {
		auto [a, b] = fwt.query(x);
		return a * lint(v[x]) + b;
	}
	lint rangeSum(int u, int v) { return query(v) - query(u); }
} bit[2];

struct event {
	int x, s, e;
	lint val;
};

struct quer {
	int x, s, e, buho, idx;
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int r, c, n, q, mod;
	cin >> r >> c >> n >> q >> mod;
	vector<event> rect;
	vector<quer> query;
	for (int i = 0; i < n; i++) {
		int x1, y1, x2, y2, w = 1;
		cin >> x1 >> y1 >> x2 >> y2;
		if (x1 > x2)
			swap(x1, x2);
		if (y1 > y2)
			swap(y1, y2);
		rect.push_back({x1, y1, y2, lint(w)});
		rect.push_back({x2, y1, y2, -lint(w)});
		v.push_back(y1);
		v.push_back(y2);
	}
	for (int i = 0; i < q; i++) {
		int x1, y1, x2, y2, vv;
		cin >> x1 >> y1 >> x2 >> y2 >> vv;
		if (x1 > x2)
			swap(x1, x2);
		if (y1 > y2)
			swap(y1, y2);
		assert(vv == 0);
		query.push_back({x1, y1, y2, -1, i});
		query.push_back({x2, y1, y2, +1, i});
		v.push_back(y1);
		v.push_back(y2);
	}
	sort(all(v));
	v.resize(unique(all(v)) - v.begin());
	for (auto &x : rect) {
		x.s = lower_bound(all(v), x.s) - v.begin();
		x.e = lower_bound(all(v), x.e) - v.begin();
	}
	for (auto &x : query) {
		x.s = lower_bound(all(v), x.s) - v.begin();
		x.e = lower_bound(all(v), x.e) - v.begin();
	}
	vector<lint> ans(q);
	sort(all(rect), [&](const event &a, const event &b) { return a.x < b.x; });
	sort(all(query), [&](const quer &a, const quer &b) { return a.x < b.x; });
	int j = 0;
	for (auto &z : query) {
		while (j < sz(rect) && rect[j].x <= z.x) {
			bit[0].rangeAdd(rect[j].s, rect[j].e, rect[j].val);
			bit[1].rangeAdd(rect[j].s, rect[j].e, -rect[j].val * lint(rect[j].x));
			j++;
		}
		ans[z.idx] += lint(z.buho) * (bit[0].rangeSum(z.s, z.e) * lint(z.x) + bit[1].rangeSum(z.s, z.e));
	}
	for (auto &z : ans)
		cout << z << "\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 552 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 552 KB Output is correct
4 Correct 10 ms 1700 KB Output is correct
5 Correct 10 ms 1716 KB Output is correct
6 Correct 9 ms 1676 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 552 KB Output is correct
4 Correct 10 ms 1700 KB Output is correct
5 Correct 10 ms 1716 KB Output is correct
6 Correct 9 ms 1676 KB Output is correct
7 Correct 76 ms 11368 KB Output is correct
8 Correct 137 ms 15112 KB Output is correct
9 Correct 113 ms 14052 KB Output is correct
10 Correct 118 ms 14960 KB Output is correct
11 Correct 114 ms 14040 KB Output is correct
12 Correct 117 ms 15072 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 552 KB Output is correct
4 Correct 10 ms 1700 KB Output is correct
5 Correct 10 ms 1716 KB Output is correct
6 Correct 9 ms 1676 KB Output is correct
7 Correct 83 ms 11940 KB Output is correct
8 Correct 129 ms 15312 KB Output is correct
9 Correct 116 ms 14400 KB Output is correct
10 Correct 125 ms 15176 KB Output is correct
11 Correct 115 ms 14384 KB Output is correct
12 Correct 120 ms 15168 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 552 KB Output is correct
4 Correct 10 ms 1700 KB Output is correct
5 Correct 10 ms 1716 KB Output is correct
6 Correct 9 ms 1676 KB Output is correct
7 Correct 76 ms 11368 KB Output is correct
8 Correct 137 ms 15112 KB Output is correct
9 Correct 113 ms 14052 KB Output is correct
10 Correct 118 ms 14960 KB Output is correct
11 Correct 114 ms 14040 KB Output is correct
12 Correct 117 ms 15072 KB Output is correct
13 Correct 83 ms 11940 KB Output is correct
14 Correct 129 ms 15312 KB Output is correct
15 Correct 116 ms 14400 KB Output is correct
16 Correct 125 ms 15176 KB Output is correct
17 Correct 115 ms 14384 KB Output is correct
18 Correct 120 ms 15168 KB Output is correct
19 Correct 115 ms 14396 KB Output is correct
20 Correct 130 ms 18420 KB Output is correct
21 Correct 122 ms 16368 KB Output is correct
22 Correct 126 ms 18184 KB Output is correct
23 Correct 127 ms 16772 KB Output is correct
24 Correct 130 ms 18272 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 8168 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 8168 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -