oj.uz

Submission #813942

# Submission time Handle Problem Language Result Execution time Memory
813942 2023-08-08T04:41:49 Z 이동현(#10122) Posters on the wall (CPSPC17_posters) C++17
90 / 100
 847 ms 993224 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)21000000;
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);

		// cout << tr[nrt].A << ' ' << tr[nrt].B << endl;

		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);
			// cout << pos << ' ' << rv.first << ' ' << rv.second << endl;
			return rv.first * x + rv.second;
		};

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

		// cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
		cout << preans << '\n';
	}
	
	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 318 ms 986672 KB Output is correct
2 Correct 300 ms 986668 KB Output is correct
3 Correct 296 ms 986572 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 986672 KB Output is correct
2 Correct 300 ms 986668 KB Output is correct
3 Correct 296 ms 986572 KB Output is correct
4 Correct 314 ms 987352 KB Output is correct
5 Correct 336 ms 987400 KB Output is correct
6 Correct 311 ms 987408 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 986672 KB Output is correct
2 Correct 300 ms 986668 KB Output is correct
3 Correct 296 ms 986572 KB Output is correct
4 Correct 314 ms 987352 KB Output is correct
5 Correct 336 ms 987400 KB Output is correct
6 Correct 311 ms 987408 KB Output is correct
7 Correct 462 ms 992780 KB Output is correct
8 Correct 727 ms 992780 KB Output is correct
9 Correct 533 ms 992736 KB Output is correct
10 Correct 655 ms 992852 KB Output is correct
11 Correct 574 ms 992768 KB Output is correct
12 Correct 586 ms 992784 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 986672 KB Output is correct
2 Correct 300 ms 986668 KB Output is correct
3 Correct 296 ms 986572 KB Output is correct
4 Correct 314 ms 987352 KB Output is correct
5 Correct 336 ms 987400 KB Output is correct
6 Correct 311 ms 987408 KB Output is correct
7 Correct 538 ms 992872 KB Output is correct
8 Correct 847 ms 993016 KB Output is correct
9 Correct 637 ms 992780 KB Output is correct
10 Correct 774 ms 993052 KB Output is correct
11 Correct 699 ms 992972 KB Output is correct
12 Correct 697 ms 992844 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 986672 KB Output is correct
2 Correct 300 ms 986668 KB Output is correct
3 Correct 296 ms 986572 KB Output is correct
4 Correct 314 ms 987352 KB Output is correct
5 Correct 336 ms 987400 KB Output is correct
6 Correct 311 ms 987408 KB Output is correct
7 Correct 462 ms 992780 KB Output is correct
8 Correct 727 ms 992780 KB Output is correct
9 Correct 533 ms 992736 KB Output is correct
10 Correct 655 ms 992852 KB Output is correct
11 Correct 574 ms 992768 KB Output is correct
12 Correct 586 ms 992784 KB Output is correct
13 Correct 538 ms 992872 KB Output is correct
14 Correct 847 ms 993016 KB Output is correct
15 Correct 637 ms 992780 KB Output is correct
16 Correct 774 ms 993052 KB Output is correct
17 Correct 699 ms 992972 KB Output is correct
18 Correct 697 ms 992844 KB Output is correct
19 Correct 561 ms 993164 KB Output is correct
20 Correct 824 ms 993164 KB Output is correct
21 Correct 638 ms 992964 KB Output is correct
22 Correct 804 ms 993088 KB Output is correct
23 Correct 692 ms 993224 KB Output is correct
24 Correct 685 ms 993044 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 992756 KB Output is correct
2 Correct 688 ms 992756 KB Output is correct
3 Correct 523 ms 992744 KB Output is correct
4 Correct 659 ms 992760 KB Output is correct
5 Correct 580 ms 992724 KB Output is correct
6 Correct 667 ms 992768 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 992756 KB Output is correct
2 Correct 688 ms 992756 KB Output is correct
3 Correct 523 ms 992744 KB Output is correct
4 Correct 659 ms 992760 KB Output is correct
5 Correct 580 ms 992724 KB Output is correct
6 Correct 667 ms 992768 KB Output is correct
7 Incorrect 644 ms 992668 KB Output isn't correct
8 Halted 0 ms 0 KB -