oj.uz

답안 #813937

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
813937 2023-08-08T04:40:33 Z 이동현(#10122) Posters on the wall (CPSPC17_posters) C++17
0 / 100
 390 ms 1048576 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)23000000;
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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 390 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 390 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 390 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 390 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 390 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 324 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 324 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -