oj.uz

Submission #814128

# Submission time Handle Problem Language Result Execution time Memory
814128 2023-08-08T05:43:01 Z 박영우(#10123) Posters on the wall (CPSPC17_posters) C++17
20 / 100
 293 ms 308352 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[6060606];
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 27 ms 48852 KB Output is correct
2 Correct 30 ms 49172 KB Output is correct
3 Correct 31 ms 48936 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 48852 KB Output is correct
2 Correct 30 ms 49172 KB Output is correct
3 Correct 31 ms 48936 KB Output is correct
4 Correct 61 ms 64792 KB Output is correct
5 Correct 58 ms 65360 KB Output is correct
6 Correct 56 ms 63480 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 48852 KB Output is correct
2 Correct 30 ms 49172 KB Output is correct
3 Correct 31 ms 48936 KB Output is correct
4 Correct 61 ms 64792 KB Output is correct
5 Correct 58 ms 65360 KB Output is correct
6 Correct 56 ms 63480 KB Output is correct
7 Runtime error 272 ms 307600 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 48852 KB Output is correct
2 Correct 30 ms 49172 KB Output is correct
3 Correct 31 ms 48936 KB Output is correct
4 Correct 61 ms 64792 KB Output is correct
5 Correct 58 ms 65360 KB Output is correct
6 Correct 56 ms 63480 KB Output is correct
7 Runtime error 293 ms 308352 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 48852 KB Output is correct
2 Correct 30 ms 49172 KB Output is correct
3 Correct 31 ms 48936 KB Output is correct
4 Correct 61 ms 64792 KB Output is correct
5 Correct 58 ms 65360 KB Output is correct
6 Correct 56 ms 63480 KB Output is correct
7 Runtime error 272 ms 307600 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 265 ms 306532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 265 ms 306532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -