oj.uz

Submission #813964

# Submission time Handle Problem Language Result Execution time Memory
813964 2023-08-08T04:46:46 Z 이동현(#10122) Posters on the wall (CPSPC17_posters) C++17
100 / 100
 907 ms 1020948 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

struct Node{
	int l, r, A, B, Alazy, Blazy;

	Node(){
		l = 0, r = 0, A = 0, B = 0, Alazy = 0, Blazy = 0;
	}
};
const int SZ = (int)21500000;
Node tr[SZ];
int tn;

void push(int x, int s, int e, int ps, int pe, int pa, int pb){
	// cout << x << ' ' << s << ' ' << e << ' ' << ps << ' ' << pe << ' ' << pa << ' ' << pb << endl;
	if(ps <= s && pe >= e){
		tr[x].A += pa * (e - s + 1), tr[x].Alazy += pa;
		tr[x].B += pb * (e - s + 1), tr[x].Blazy += pb;
		return;
	}

	int m = s + e >> 1;

	if(tr[x].Alazy || tr[x].Blazy || ps <= m){
		tr[++tn] = tr[tr[x].l];
		tr[x].l = tn;
	}
	if(tr[x].Alazy || tr[x].Blazy || pe > m){
		tr[++tn] = tr[tr[x].r];
		tr[x].r = tn;
	}

	tr[tr[x].l].A += tr[x].Alazy * (m - s + 1), tr[tr[x].l].Alazy += tr[x].Alazy;
	tr[tr[x].l].B += tr[x].Blazy * (m - s + 1), tr[tr[x].l].Blazy += tr[x].Blazy;
	tr[tr[x].r].A += tr[x].Alazy * (e - m), tr[tr[x].r].Alazy += tr[x].Alazy;
	tr[tr[x].r].B += tr[x].Blazy * (e - m), tr[tr[x].r].Blazy += tr[x].Blazy;

	tr[x].Alazy = tr[x].Blazy = 0;

	if(ps <= m){
		push(tr[x].l, s, m, ps, pe, pa, pb);
	}
	if(pe > m){
		push(tr[x].r, m + 1, e, ps, pe, pa, pb);
	}

	tr[x].A = tr[tr[x].l].A + tr[tr[x].r].A;
	tr[x].B = tr[tr[x].l].B + tr[tr[x].r].B;
}

pair<int, int> get(int x, int s, int e, int fs, int fe){
	if(fe < s || fs > e) return {0, 0};
	if(fs <= s && fe >= e){
		return {tr[x].A, tr[x].B};
	}
	
	int m = s + e >> 1;

	if(tr[x].Alazy || tr[x].Blazy){
		tr[++tn] = tr[tr[x].l];
		tr[x].l = tn;
		tr[++tn] = tr[tr[x].r];
		tr[x].r = tn;
		
		tr[tr[x].l].A += tr[x].Alazy * (m - s + 1), tr[tr[x].l].Alazy += tr[x].Alazy;
		tr[tr[x].l].B += tr[x].Blazy * (m - s + 1), tr[tr[x].l].Blazy += tr[x].Blazy;
		tr[tr[x].r].A += tr[x].Alazy * (e - m), tr[tr[x].r].Alazy += tr[x].Alazy;
		tr[tr[x].r].B += tr[x].Blazy * (e - m), tr[tr[x].r].Blazy += tr[x].Blazy;

		tr[x].Alazy = tr[x].Blazy = 0;
	}

	auto lv = get(tr[x].l, s, m, fs, fe);
	auto rv = get(tr[x].r, m + 1, e, fs, fe);

	return {lv.first + rv.first, lv.second + rv.second};
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int h, w, n, m, mod;
	cin >> h >> w >> n >> m >> mod;

	vector<array<int, 5>> que;
	vector<int> srt;
	for(int i = 0; i < n; ++i){
		int x1, y1, x2, y2;
		cin >> y1 >> x1 >> y2 >> x2;
		if(x1 > x2) swap(x1, x2);
		if(y1 > y2) swap(y1, y2);

		que.push_back({x1, y1, y2 - 1, 1, -x1});
		que.push_back({x2, y1, y2 - 1, -1, x2});

		srt.push_back(x1);
		srt.push_back(x2);
	}

	sort(que.begin(), que.end());
	sort(srt.begin(), srt.end());
	srt.erase(unique(srt.begin(), srt.end()), srt.end());
	vector<int> rt((int)srt.size());

	int lst = 0;
	for(auto&[x, y1, y2, A, B]:que){
		int nrt = ++tn;

		tr[nrt] = tr[lst];
		push(nrt, 0, h - 1, y1, y2, A, B);

		int pos = lower_bound(srt.begin(), srt.end(), x) - srt.begin();
		rt[pos] = nrt;
		lst = nrt;
	}

	int preans = 0;
	for(int rep = 0; rep < m; ++rep){
		int x1, y1, x2, y2, v;
		cin >> y1 >> x1 >> y2 >> x2 >> v;

		x1 = (x1 + preans * v) % mod;
		x2 = (x2 + preans * v) % mod;
		y1 = (y1 + preans * v) % mod;
		y2 = (y2 + preans * v) % mod;
		
		if(x1 > x2) swap(x1, x2);
		if(y1 > y2) swap(y1, y2);

		auto sol = [&](int x, int y1, int y2)->int{
			int pos = lower_bound(srt.begin(), srt.end(), x + 1) - srt.begin() - 1;
			if(pos < 0){
				return 0;
			}

			auto rv = get(rt[pos], 0, h - 1, y1, y2 - 1);
			return rv.first * x + rv.second;
		};

		preans = sol(x2, y1, y2) - sol(x1, y1, y2);

		cout << preans << '\n';

		preans %= mod;
	}

	assert(tn < SZ);
	
	return 0;
}

Compilation message

Main.cpp: In function 'void push(long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:27:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |  int m = s + e >> 1;
      |          ~~^~~
Main.cpp: In function 'std::pair<long long int, long long int> get(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:62:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |  int m = s + e >> 1;
      |          ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 1010040 KB Output is correct
2 Correct 321 ms 1010048 KB Output is correct
3 Correct 323 ms 1010164 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 1010040 KB Output is correct
2 Correct 321 ms 1010048 KB Output is correct
3 Correct 323 ms 1010164 KB Output is correct
4 Correct 325 ms 1010836 KB Output is correct
5 Correct 343 ms 1010856 KB Output is correct
6 Correct 331 ms 1010884 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 1010040 KB Output is correct
2 Correct 321 ms 1010048 KB Output is correct
3 Correct 323 ms 1010164 KB Output is correct
4 Correct 325 ms 1010836 KB Output is correct
5 Correct 343 ms 1010856 KB Output is correct
6 Correct 331 ms 1010884 KB Output is correct
7 Correct 453 ms 1016244 KB Output is correct
8 Correct 691 ms 1016268 KB Output is correct
9 Correct 557 ms 1016224 KB Output is correct
10 Correct 650 ms 1016192 KB Output is correct
11 Correct 589 ms 1016228 KB Output is correct
12 Correct 597 ms 1016248 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 1010040 KB Output is correct
2 Correct 321 ms 1010048 KB Output is correct
3 Correct 323 ms 1010164 KB Output is correct
4 Correct 325 ms 1010836 KB Output is correct
5 Correct 343 ms 1010856 KB Output is correct
6 Correct 331 ms 1010884 KB Output is correct
7 Correct 594 ms 1016344 KB Output is correct
8 Correct 834 ms 1016400 KB Output is correct
9 Correct 661 ms 1016332 KB Output is correct
10 Correct 800 ms 1016428 KB Output is correct
11 Correct 713 ms 1016372 KB Output is correct
12 Correct 687 ms 1016388 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 1010040 KB Output is correct
2 Correct 321 ms 1010048 KB Output is correct
3 Correct 323 ms 1010164 KB Output is correct
4 Correct 325 ms 1010836 KB Output is correct
5 Correct 343 ms 1010856 KB Output is correct
6 Correct 331 ms 1010884 KB Output is correct
7 Correct 453 ms 1016244 KB Output is correct
8 Correct 691 ms 1016268 KB Output is correct
9 Correct 557 ms 1016224 KB Output is correct
10 Correct 650 ms 1016192 KB Output is correct
11 Correct 589 ms 1016228 KB Output is correct
12 Correct 597 ms 1016248 KB Output is correct
13 Correct 594 ms 1016344 KB Output is correct
14 Correct 834 ms 1016400 KB Output is correct
15 Correct 661 ms 1016332 KB Output is correct
16 Correct 800 ms 1016428 KB Output is correct
17 Correct 713 ms 1016372 KB Output is correct
18 Correct 687 ms 1016388 KB Output is correct
19 Correct 558 ms 1016600 KB Output is correct
20 Correct 868 ms 1016536 KB Output is correct
21 Correct 649 ms 1016348 KB Output is correct
22 Correct 792 ms 1016696 KB Output is correct
23 Correct 869 ms 1016636 KB Output is correct
24 Correct 681 ms 1016568 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 1016276 KB Output is correct
2 Correct 686 ms 1016152 KB Output is correct
3 Correct 524 ms 1016244 KB Output is correct
4 Correct 658 ms 1016396 KB Output is correct
5 Correct 554 ms 1016240 KB Output is correct
6 Correct 617 ms 1016220 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 1016276 KB Output is correct
2 Correct 686 ms 1016152 KB Output is correct
3 Correct 524 ms 1016244 KB Output is correct
4 Correct 658 ms 1016396 KB Output is correct
5 Correct 554 ms 1016240 KB Output is correct
6 Correct 617 ms 1016220 KB Output is correct
7 Correct 597 ms 1016600 KB Output is correct
8 Correct 907 ms 1020924 KB Output is correct
9 Correct 670 ms 1020772 KB Output is correct
10 Correct 874 ms 1020948 KB Output is correct
11 Correct 766 ms 1020820 KB Output is correct
12 Correct 699 ms 1020908 KB Output is correct