oj.uz

Submission #813926

# Submission time Handle Problem Language Result Execution time Memory
813926 2023-08-08T04:38:02 Z 이동현(#10122) Posters on the wall (CPSPC17_posters) C++17
70 / 100
 878 ms 964756 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)1e7, INF = (int)1e9 + 10;
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 157 ms 469980 KB Output is correct
2 Correct 181 ms 470052 KB Output is correct
3 Correct 154 ms 469924 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 469980 KB Output is correct
2 Correct 181 ms 470052 KB Output is correct
3 Correct 154 ms 469924 KB Output is correct
4 Correct 168 ms 470780 KB Output is correct
5 Correct 164 ms 470728 KB Output is correct
6 Correct 165 ms 470780 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 469980 KB Output is correct
2 Correct 181 ms 470052 KB Output is correct
3 Correct 154 ms 469924 KB Output is correct
4 Correct 168 ms 470780 KB Output is correct
5 Correct 164 ms 470728 KB Output is correct
6 Correct 165 ms 470780 KB Output is correct
7 Correct 282 ms 476068 KB Output is correct
8 Correct 589 ms 476188 KB Output is correct
9 Correct 383 ms 476072 KB Output is correct
10 Correct 491 ms 476088 KB Output is correct
11 Correct 437 ms 476128 KB Output is correct
12 Correct 435 ms 476144 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 469980 KB Output is correct
2 Correct 181 ms 470052 KB Output is correct
3 Correct 154 ms 469924 KB Output is correct
4 Correct 168 ms 470780 KB Output is correct
5 Correct 164 ms 470728 KB Output is correct
6 Correct 165 ms 470780 KB Output is correct
7 Correct 387 ms 476228 KB Output is correct
8 Runtime error 878 ms 964756 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 469980 KB Output is correct
2 Correct 181 ms 470052 KB Output is correct
3 Correct 154 ms 469924 KB Output is correct
4 Correct 168 ms 470780 KB Output is correct
5 Correct 164 ms 470728 KB Output is correct
6 Correct 165 ms 470780 KB Output is correct
7 Correct 282 ms 476068 KB Output is correct
8 Correct 589 ms 476188 KB Output is correct
9 Correct 383 ms 476072 KB Output is correct
10 Correct 491 ms 476088 KB Output is correct
11 Correct 437 ms 476128 KB Output is correct
12 Correct 435 ms 476144 KB Output is correct
13 Correct 387 ms 476228 KB Output is correct
14 Runtime error 878 ms 964756 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 477352 KB Output is correct
2 Correct 524 ms 478624 KB Output is correct
3 Correct 368 ms 478588 KB Output is correct
4 Correct 504 ms 478692 KB Output is correct
5 Correct 403 ms 478672 KB Output is correct
6 Correct 451 ms 478636 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 477352 KB Output is correct
2 Correct 524 ms 478624 KB Output is correct
3 Correct 368 ms 478588 KB Output is correct
4 Correct 504 ms 478692 KB Output is correct
5 Correct 403 ms 478672 KB Output is correct
6 Correct 451 ms 478636 KB Output is correct
7 Incorrect 501 ms 479964 KB Output isn't correct
8 Halted 0 ms 0 KB -