oj.uz

Submission #813953

# Submission time Handle Problem Language Result Execution time Memory
813953 2023-08-08T04:44:43 Z 이동현(#10122) Posters on the wall (CPSPC17_posters) C++17
90 / 100
 897 ms 1016596 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';
	}

	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 330 ms 1010136 KB Output is correct
2 Correct 310 ms 1010140 KB Output is correct
3 Correct 311 ms 1010056 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 1010136 KB Output is correct
2 Correct 310 ms 1010140 KB Output is correct
3 Correct 311 ms 1010056 KB Output is correct
4 Correct 320 ms 1010784 KB Output is correct
5 Correct 320 ms 1010796 KB Output is correct
6 Correct 324 ms 1010824 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 1010136 KB Output is correct
2 Correct 310 ms 1010140 KB Output is correct
3 Correct 311 ms 1010056 KB Output is correct
4 Correct 320 ms 1010784 KB Output is correct
5 Correct 320 ms 1010796 KB Output is correct
6 Correct 324 ms 1010824 KB Output is correct
7 Correct 417 ms 1016236 KB Output is correct
8 Correct 713 ms 1016200 KB Output is correct
9 Correct 516 ms 1016204 KB Output is correct
10 Correct 694 ms 1016380 KB Output is correct
11 Correct 576 ms 1016244 KB Output is correct
12 Correct 593 ms 1016364 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 1010136 KB Output is correct
2 Correct 310 ms 1010140 KB Output is correct
3 Correct 311 ms 1010056 KB Output is correct
4 Correct 320 ms 1010784 KB Output is correct
5 Correct 320 ms 1010796 KB Output is correct
6 Correct 324 ms 1010824 KB Output is correct
7 Correct 558 ms 1016348 KB Output is correct
8 Correct 897 ms 1016352 KB Output is correct
9 Correct 678 ms 1016232 KB Output is correct
10 Correct 860 ms 1016436 KB Output is correct
11 Correct 739 ms 1016376 KB Output is correct
12 Correct 703 ms 1016400 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 1010136 KB Output is correct
2 Correct 310 ms 1010140 KB Output is correct
3 Correct 311 ms 1010056 KB Output is correct
4 Correct 320 ms 1010784 KB Output is correct
5 Correct 320 ms 1010796 KB Output is correct
6 Correct 324 ms 1010824 KB Output is correct
7 Correct 417 ms 1016236 KB Output is correct
8 Correct 713 ms 1016200 KB Output is correct
9 Correct 516 ms 1016204 KB Output is correct
10 Correct 694 ms 1016380 KB Output is correct
11 Correct 576 ms 1016244 KB Output is correct
12 Correct 593 ms 1016364 KB Output is correct
13 Correct 558 ms 1016348 KB Output is correct
14 Correct 897 ms 1016352 KB Output is correct
15 Correct 678 ms 1016232 KB Output is correct
16 Correct 860 ms 1016436 KB Output is correct
17 Correct 739 ms 1016376 KB Output is correct
18 Correct 703 ms 1016400 KB Output is correct
19 Correct 582 ms 1016596 KB Output is correct
20 Correct 891 ms 1016596 KB Output is correct
21 Correct 705 ms 1016336 KB Output is correct
22 Correct 860 ms 1016532 KB Output is correct
23 Correct 821 ms 1016584 KB Output is correct
24 Correct 780 ms 1016504 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 1016220 KB Output is correct
2 Correct 715 ms 1016152 KB Output is correct
3 Correct 586 ms 1016200 KB Output is correct
4 Correct 744 ms 1016156 KB Output is correct
5 Correct 613 ms 1016228 KB Output is correct
6 Correct 673 ms 1016232 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 1016220 KB Output is correct
2 Correct 715 ms 1016152 KB Output is correct
3 Correct 586 ms 1016200 KB Output is correct
4 Correct 744 ms 1016156 KB Output is correct
5 Correct 613 ms 1016228 KB Output is correct
6 Correct 673 ms 1016232 KB Output is correct
7 Incorrect 676 ms 1016176 KB Output isn't correct
8 Halted 0 ms 0 KB -