oj.uz

Submission #814132

# Submission time Handle Problem Language Result Execution time Memory
814132 2023-08-08T05:45:40 Z 박영우(#10123) Posters on the wall (CPSPC17_posters) C++17
90 / 100
 1270 ms 289760 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--) {
		int a, b, c, d;
		ll v;
		cin >> a >> b >> c >> d;
		cin >> v;
		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 26 ms 48896 KB Output is correct
2 Correct 26 ms 49116 KB Output is correct
3 Correct 31 ms 48984 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 48896 KB Output is correct
2 Correct 26 ms 49116 KB Output is correct
3 Correct 31 ms 48984 KB Output is correct
4 Correct 62 ms 64560 KB Output is correct
5 Correct 63 ms 65176 KB Output is correct
6 Correct 64 ms 63300 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 48896 KB Output is correct
2 Correct 26 ms 49116 KB Output is correct
3 Correct 31 ms 48984 KB Output is correct
4 Correct 62 ms 64560 KB Output is correct
5 Correct 63 ms 65176 KB Output is correct
6 Correct 64 ms 63300 KB Output is correct
7 Correct 334 ms 269488 KB Output is correct
8 Correct 1231 ms 283520 KB Output is correct
9 Correct 613 ms 275380 KB Output is correct
10 Correct 1172 ms 282632 KB Output is correct
11 Correct 845 ms 279948 KB Output is correct
12 Correct 754 ms 274592 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 48896 KB Output is correct
2 Correct 26 ms 49116 KB Output is correct
3 Correct 31 ms 48984 KB Output is correct
4 Correct 62 ms 64560 KB Output is correct
5 Correct 63 ms 65176 KB Output is correct
6 Correct 64 ms 63300 KB Output is correct
7 Correct 364 ms 278868 KB Output is correct
8 Correct 1270 ms 287192 KB Output is correct
9 Correct 624 ms 275476 KB Output is correct
10 Correct 1127 ms 285700 KB Output is correct
11 Correct 917 ms 283668 KB Output is correct
12 Correct 868 ms 278868 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 48896 KB Output is correct
2 Correct 26 ms 49116 KB Output is correct
3 Correct 31 ms 48984 KB Output is correct
4 Correct 62 ms 64560 KB Output is correct
5 Correct 63 ms 65176 KB Output is correct
6 Correct 64 ms 63300 KB Output is correct
7 Correct 334 ms 269488 KB Output is correct
8 Correct 1231 ms 283520 KB Output is correct
9 Correct 613 ms 275380 KB Output is correct
10 Correct 1172 ms 282632 KB Output is correct
11 Correct 845 ms 279948 KB Output is correct
12 Correct 754 ms 274592 KB Output is correct
13 Correct 364 ms 278868 KB Output is correct
14 Correct 1270 ms 287192 KB Output is correct
15 Correct 624 ms 275476 KB Output is correct
16 Correct 1127 ms 285700 KB Output is correct
17 Correct 917 ms 283668 KB Output is correct
18 Correct 868 ms 278868 KB Output is correct
19 Correct 498 ms 284272 KB Output is correct
20 Correct 1192 ms 289760 KB Output is correct
21 Correct 562 ms 275632 KB Output is correct
22 Correct 1045 ms 287924 KB Output is correct
23 Correct 797 ms 285908 KB Output is correct
24 Correct 730 ms 281592 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 260572 KB Output is correct
2 Correct 1083 ms 274396 KB Output is correct
3 Correct 573 ms 275356 KB Output is correct
4 Correct 993 ms 273860 KB Output is correct
5 Correct 792 ms 273004 KB Output is correct
6 Correct 725 ms 269544 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 260572 KB Output is correct
2 Correct 1083 ms 274396 KB Output is correct
3 Correct 573 ms 275356 KB Output is correct
4 Correct 993 ms 273860 KB Output is correct
5 Correct 792 ms 273004 KB Output is correct
6 Correct 725 ms 269544 KB Output is correct
7 Incorrect 674 ms 283640 KB Output isn't correct
8 Halted 0 ms 0 KB -