oj.uz

Submission #814142

# Submission time Handle Problem Language Result Execution time Memory
814142 2023-08-08T05:48:24 Z 박영우(#10123) Posters on the wall (CPSPC17_posters) C++17
100 / 100
 1219 ms 289944 KB 
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 1010100
#define MAXS 5050
#define INF 1000000000
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
struct node {
	int l, r;
	ll val;
};
node MEM[20060606];
int ncnt = 0;
int upd(int s, int e, int i, ll x, int loc = 1) {
	assert(s <= i && i <= e);
	int n = ++ncnt;
	MEM[n] = MEM[loc];
	MEM[n].val += x;
	if (s == e) return n;
	int m = s + e >> 1;
	if (i <= m) MEM[n].l = upd(s, m, i, x, MEM[loc].l);
	else MEM[n].r = upd(m + 1, e, i, x, MEM[loc].r);
	return n;
}
ll query(int s, int e, int l, int r, int loc = 1) {
	if (l > r) return 0;
	if (!loc) return 0;
	if (e < l || r < s) return 0;
	if (l <= s && e <= r) return MEM[loc].val;
	int m = s + e >> 1;
	return query(s, m, l, r, MEM[loc].l) + query(m + 1, e, l, r, MEM[loc].r);
}
int R, C, N, M, Q;
ll X1[MAX];
ll X2[MAX];
ll Y1[MAX];
ll Y2[MAX];
vector<pii> upx[MAX];
vector<pii> upy[MAX];
vector<ll> xs, ys;
int rt1[MAX];
int rtx[MAX];
int rty[MAX];
int rtxy[MAX];
int X, Y;
ll get(int x, int y) {
	int xl, yl;
	xl = upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1;
	yl = upper_bound(ys.begin(), ys.end(), y) - ys.begin() - 1;
	ll ans = 0;
	ans += 1ll * (x + 1) * (y + 1) * query(0, X - 1, xl + 1, X - 1, rt1[yl + 1]);
	ans += 1ll * (y + 1) * query(0, X - 1, 0, xl, rtx[yl + 1]);
	ans += 1ll * (x + 1) * query(0, Y - 1, 0, yl, rty[xl + 1]);
	ans += query(0, X - 1, 0, xl, rtxy[yl]);
	return ans;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> R >> C >> N >> Q >> M;
	int i;
	for (i = 1; i <= N; i++) {
		cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i];
		if (X1[i] > X2[i]) swap(X1[i], X2[i]);
		if (Y1[i] > Y2[i]) swap(Y1[i], Y2[i]);
		X2[i]--, Y2[i]--;
		xs.push_back(X1[i]);
		xs.push_back(X1[i] - 1);
		xs.push_back(X2[i]);
		ys.push_back(Y1[i]);
		ys.push_back(Y1[i] - 1);
		ys.push_back(Y2[i]);
	}
	xs.push_back(0);
	ys.push_back(0);
	sort(xs.begin(), xs.end());
	sort(ys.begin(), ys.end());
	xs.erase(unique(xs.begin(), xs.end()), xs.end());
	ys.erase(unique(ys.begin(), ys.end()), ys.end());
	X = xs.size();
	Y = ys.size();
	for (i = 1; i <= N; i++) {
		X1[i] = lower_bound(xs.begin(), xs.end(), X1[i]) - xs.begin();
		X2[i] = lower_bound(xs.begin(), xs.end(), X2[i]) - xs.begin();
		Y1[i] = lower_bound(ys.begin(), ys.end(), Y1[i]) - ys.begin();
		Y2[i] = lower_bound(ys.begin(), ys.end(), Y2[i]) - ys.begin();
		upx[X2[i]].emplace_back(Y2[i], 1);
		if (Y1[i]) upx[X2[i]].emplace_back(Y1[i] - 1, -1);
		if (X1[i]) upx[X1[i] - 1].emplace_back(Y2[i], -1);
		if (X1[i] && Y1[i]) upx[X1[i] - 1].emplace_back(Y1[i] - 1, 1);
		upy[Y2[i]].emplace_back(X2[i], 1);
		if (X1[i]) upy[Y2[i]].emplace_back(X1[i] - 1, -1);
		if (Y1[i]) upy[Y1[i] - 1].emplace_back(X2[i], -1);
		if (X1[i] && Y1[i]) upy[Y1[i] - 1].emplace_back(X1[i] - 1, 1);
	}
	for (i = Y - 1; i >= 0; i--) {
		int pv = rt1[i + 1];
		for (auto& [x, mul] : upy[i]) pv = upd(0, X - 1, x, mul, pv);
		rt1[i] = pv;
	}
	for (i = Y - 1; i >= 0; i--) {
		int pv = rtx[i + 1];
		for (auto& [x, mul] : upy[i]) pv = upd(0, X - 1, x, (xs[x] + 1) * mul, pv);
		rtx[i] = pv;
	}
	for (i = 0; i < Y; i++) {
		int pv = 0;
		if (i) pv = rtxy[i - 1];
		for (auto& [x, mul] : upy[i]) pv = upd(0, X - 1, x, (xs[x] + 1) * (ys[i] + 1) * mul, pv);
		rtxy[i] = pv;
	}
	for (i = X - 1; i >= 0; i--) {
		int pv = rty[i + 1];
		for (auto& [y, mul] : upx[i]) pv = upd(0, Y - 1, y, (ys[y] + 1) * mul, pv);
		rty[i] = pv;
	}
	ll ans = 0;
	while (Q--) {
		ll a, b, c, d;
		ll v;
		cin >> a >> b >> c >> d;
		cin >> v;
		ans %= M;
		v %= M;
		v *= ans;
		a = (a + v) % M;
		b = (b + v) % M;
		c = (c + v) % M;
		d = (d + v) % M;
		if (a > c) swap(a, c);
		if (b > d) swap(b, d);
		c--, d--;
		ans = get(c, d) - get(a - 1, d) - get(c, b - 1) + get(a - 1, b - 1);
		cout << ans << ln;
	}
}

Compilation message

Main.cpp: In function 'int upd(int, int, int, ll, int)':
Main.cpp:30:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |  int m = s + e >> 1;
      |          ~~^~~
Main.cpp: In function 'll query(int, int, int, int, int)':
Main.cpp:40:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |  int m = s + e >> 1;
      |          ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 48796 KB Output is correct
2 Correct 24 ms 49092 KB Output is correct
3 Correct 25 ms 48956 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 48796 KB Output is correct
2 Correct 24 ms 49092 KB Output is correct
3 Correct 25 ms 48956 KB Output is correct
4 Correct 60 ms 64652 KB Output is correct
5 Correct 62 ms 65168 KB Output is correct
6 Correct 53 ms 63376 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 48796 KB Output is correct
2 Correct 24 ms 49092 KB Output is correct
3 Correct 25 ms 48956 KB Output is correct
4 Correct 60 ms 64652 KB Output is correct
5 Correct 62 ms 65168 KB Output is correct
6 Correct 53 ms 63376 KB Output is correct
7 Correct 320 ms 269484 KB Output is correct
8 Correct 1134 ms 283412 KB Output is correct
9 Correct 538 ms 275152 KB Output is correct
10 Correct 1000 ms 282480 KB Output is correct
11 Correct 730 ms 279984 KB Output is correct
12 Correct 721 ms 274652 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 48796 KB Output is correct
2 Correct 24 ms 49092 KB Output is correct
3 Correct 25 ms 48956 KB Output is correct
4 Correct 60 ms 64652 KB Output is correct
5 Correct 62 ms 65168 KB Output is correct
6 Correct 53 ms 63376 KB Output is correct
7 Correct 365 ms 278848 KB Output is correct
8 Correct 1152 ms 287132 KB Output is correct
9 Correct 536 ms 275276 KB Output is correct
10 Correct 1020 ms 285528 KB Output is correct
11 Correct 818 ms 283480 KB Output is correct
12 Correct 751 ms 278740 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 48796 KB Output is correct
2 Correct 24 ms 49092 KB Output is correct
3 Correct 25 ms 48956 KB Output is correct
4 Correct 60 ms 64652 KB Output is correct
5 Correct 62 ms 65168 KB Output is correct
6 Correct 53 ms 63376 KB Output is correct
7 Correct 320 ms 269484 KB Output is correct
8 Correct 1134 ms 283412 KB Output is correct
9 Correct 538 ms 275152 KB Output is correct
10 Correct 1000 ms 282480 KB Output is correct
11 Correct 730 ms 279984 KB Output is correct
12 Correct 721 ms 274652 KB Output is correct
13 Correct 365 ms 278848 KB Output is correct
14 Correct 1152 ms 287132 KB Output is correct
15 Correct 536 ms 275276 KB Output is correct
16 Correct 1020 ms 285528 KB Output is correct
17 Correct 818 ms 283480 KB Output is correct
18 Correct 751 ms 278740 KB Output is correct
19 Correct 455 ms 284196 KB Output is correct
20 Correct 1219 ms 289728 KB Output is correct
21 Correct 564 ms 275484 KB Output is correct
22 Correct 1106 ms 287868 KB Output is correct
23 Correct 860 ms 285660 KB Output is correct
24 Correct 723 ms 281424 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 260416 KB Output is correct
2 Correct 1059 ms 274108 KB Output is correct
3 Correct 595 ms 275224 KB Output is correct
4 Correct 990 ms 273756 KB Output is correct
5 Correct 811 ms 272840 KB Output is correct
6 Correct 761 ms 269468 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 260416 KB Output is correct
2 Correct 1059 ms 274108 KB Output is correct
3 Correct 595 ms 275224 KB Output is correct
4 Correct 990 ms 273756 KB Output is correct
5 Correct 811 ms 272840 KB Output is correct
6 Correct 761 ms 269468 KB Output is correct
7 Correct 443 ms 284180 KB Output is correct
8 Correct 1173 ms 289944 KB Output is correct
9 Correct 591 ms 275632 KB Output is correct
10 Correct 1052 ms 288176 KB Output is correct
11 Correct 722 ms 285984 KB Output is correct
12 Correct 760 ms 281700 KB Output is correct