oj.uz

Submission #814637

# Submission time Handle Problem Language Result Execution time Memory
814637 2023-08-08T08:41:29 Z 박상훈(#10120) Posters on the wall (CPSPC17_posters) C++17
100 / 100
 1609 ms 914720 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

constexpr int INF1 = 1e9 + 100;
ll X1[50050], Y1[50050], X2[50050], Y2[50050];
ll X3[50050], Y3[50050], X4[50050], Y4[50050];

ll ans[50050];

vector<ll> X, Y;

inline int getidx(const vector<ll> &a, ll x){return lower_bound(a.begin(), a.end(), x) - a.begin();}

struct PST1{
	
	struct Node{
		ll x, lazy;
		int l, r, t;
		Node(){}
		Node(ll _x, ll _la, int _l, int _r, int _t): x(_x), lazy(_la), l(_l), r(_r), t(_t) {}
	};

	Node tree[20002000];
	int root[200200], X[200200];
	int sz, szT, szR;

	void init(int n){
		sz = n;
		tree[0] = Node(0, 0, 0, 0, 0);
		root[0] = 0;
		X[0] = 0;

		szT = szR = 1;
	}

	int cp(int x, int t){
		tree[szT++] = tree[x];
		tree[szT-1].t = t;
		return szT-1;
	}

	void propagate(int i, int l, int r){
		if (l!=r){
			if (tree[tree[i].l].t != tree[i].t) tree[i].l = cp(tree[i].l, tree[i].t);
			if (tree[tree[i].r].t != tree[i].t) tree[i].r = cp(tree[i].r, tree[i].t);
		}

		if (tree[i].lazy==0) return;
		tree[i].x += tree[i].lazy * (Y[r+1] - Y[l]);

		if (l!=r){
			tree[tree[i].l].lazy += tree[i].lazy;
			tree[tree[i].r].lazy += tree[i].lazy;
		}

		tree[i].lazy = 0;
	}

	void update(int i, int l, int r, int s, int e, ll x){
		propagate(i, l, r);
		if (r<s || e<l) return;

		if (s<=l && r<=e){
			tree[i].lazy += x;
			propagate(i, l, r);
			return;
		}

		int m = (l+r)>>1;
		update(tree[i].l, l, m, s, e, x);
		update(tree[i].r, m+1, r, s, e, x);
		tree[i].x = tree[tree[i].l].x + tree[tree[i].r].x;
	}

	ll query(int i, int l, int r, int s, int e){
		if (r<s || e<l) return 0;
		propagate(i, l, r);

		if (s<=l && r<=e){
			return tree[i].x;
		} 

		int m = (l+r)>>1;
		return query(tree[i].l, l, m, s, e) + query(tree[i].r, m+1, r, s, e);
	}

	int add(){
		root[szR] = cp(root[szR-1], szR);
		szR++;
		return root[szR-1];
	}

	void update(int t, int s, int e, ll x){
		X[szR] = t;
		update(add(), 1, sz, s, e, x);
	}

	ll query(int t, int s, int e){
		t = upper_bound(X+1, X+szR, t) - X - 1;
		return query(root[t], 1, sz, s, e);
	}

}tree1;

pair<ll, ll> operator + (const pair<ll, ll> &a, const pair<ll, ll> &b){return {a.first + b.first, a.second + b.second};}

struct PST2{

	struct Node{
		ll ofs, cnt;
		ll lazyofs;
		int lazycnt, l, r, t;
		Node(){}
		Node(ll _ofs, ll _cnt, ll _lofs, int _lcnt, int _l, int _r, int _t): ofs(_ofs), cnt(_cnt), lazyofs(_lofs), lazycnt(_lcnt), l(_l), r(_r), t(_t) {}
	};

	Node tree[20002000];
	int root[200200], X[200200];
	int sz, szT, szR;

	void init(int n){
		sz = n;
		tree[0] = Node(0, 0, 0, -1, 0, 0, 0);
		root[0] = 0;
		X[0] = -INF1;

		szT = szR = 1;
	}

	int cp(int x, int t){
		tree[szT++] = tree[x];
		tree[szT-1].t = t;
		return szT-1;
	}

	void propagate(int i, int l, int r){
		if (l!=r){
			if (tree[tree[i].l].t != tree[i].t) tree[i].l = cp(tree[i].l, tree[i].t);
			if (tree[tree[i].r].t != tree[i].t) tree[i].r = cp(tree[i].r, tree[i].t);
		}

		if (tree[i].lazycnt==-1) return;
		if (tree[i].lazycnt==0) tree[i].ofs = 0, tree[i].cnt = 0;
		else tree[i].ofs = tree[i].lazyofs * (Y[r+1]-Y[l]), tree[i].cnt = Y[r+1] - Y[l];

		if (l!=r){
			tree[tree[i].l].lazycnt = tree[i].lazycnt;
			tree[tree[i].l].lazyofs = tree[i].lazyofs;
			tree[tree[i].r].lazycnt = tree[i].lazycnt;
			tree[tree[i].r].lazyofs = tree[i].lazyofs;
		}

		tree[i].lazyofs = 0;
		tree[i].lazycnt = -1;
	}

	void update(int i, int l, int r, int s, int e, ll ofs, int typ){
		propagate(i, l, r);
		if (r<s || e<l) return;

		if (s<=l && r<=e){
			tree[i].lazyofs = ofs;
			tree[i].lazycnt = typ;
			propagate(i, l, r);
			return;
		}

		int m = (l+r)>>1;
		update(tree[i].l, l, m, s, e, ofs, typ);
		update(tree[i].r, m+1, r, s, e, ofs, typ);
		tree[i].ofs = tree[tree[i].l].ofs + tree[tree[i].r].ofs;
		tree[i].cnt = tree[tree[i].l].cnt + tree[tree[i].r].cnt;
	}

	pair<ll, ll> query(int i, int l, int r, int s, int e){
		if (r<s || e<l) return {0, 0};
		propagate(i, l, r);

		if (s<=l && r<=e){
			return {tree[i].ofs, tree[i].cnt};
		} 

		int m = (l+r)>>1;
		return query(tree[i].l, l, m, s, e) + query(tree[i].r, m+1, r, s, e);
	}

	int add(){
		root[szR] = cp(root[szR-1], szR);
		szR++;
		return root[szR-1];
	}

	void update(int t, int s, int e, ll ofs, int typ){
		X[szR] = t;
		update(add(), 1, sz, s, e, ofs, typ);
	}

	pair<ll, ll> query(int t, int s, int e){
		t = upper_bound(X+1, X+szR, t) - X - 1;
		return query(root[t], 1, sz, s, e);
	}

}tree2;


int main(){
	int r, c, n, q, MOD;
	scanf("%d %d %d %d %d", &r, &c, &n, &q, &MOD);

	X.push_back(-INF1);
	X.push_back(INF1);
	Y.push_back(-INF1);
	Y.push_back(INF1);

	for (int i=1;i<=n;i++){
		scanf("%lld %lld %lld %lld", X1+i, Y1+i, X2+i, Y2+i);
		if (X1[i] > X2[i]) swap(X1[i], X2[i]);
		if (Y1[i] > Y2[i]) swap(Y1[i], Y2[i]);

		X.push_back(X1[i]);
		X.push_back(X2[i]);
		Y.push_back(Y1[i]);
		Y.push_back(Y2[i]);
	}

	// for (int i=1;i<=q;i++){
	// 	int v;
	// 	scanf("%lld %lld %lld %lld %d", X3+i, Y3+i, X4+i, Y4+i, &v);
	// 	X3[i] %= MOD;
	// 	X4[i] %= MOD;
	// 	Y3[i] %= MOD;
	// 	Y4[i] %= MOD;
	// 	if (X3[i] > X4[i]) swap(X3[i], X4[i]);
	// 	if (Y3[i] > Y4[i]) swap(Y3[i], Y4[i]);
	// }

	// auto rans = naive(n, q);
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());

	sort(Y.begin(), Y.end());
	Y.erase(unique(Y.begin(), Y.end()), Y.end());

	vector<array<ll, 3>> E;

	for (int i=1;i<=n;i++){
		X1[i] = getidx(X, X1[i]);
		X2[i] = getidx(X, X2[i]);
		Y1[i] = getidx(Y, Y1[i]);
		Y2[i] = getidx(Y, Y2[i]);

		if (X1[i]==X2[i]) continue;

		E.push_back({X[X1[i]], 2, i});
		E.push_back({X[X2[i]], 1, i});
	}

	// for (int i=1;i<=q;i++){

	// 	E.push_back({X3[i], 3, i});
	// 	E.push_back({X4[i], 4, i});
	// }

	sort(E.begin(), E.end());
	int sz = (int)Y.size()-2;
	assert(sz >= 1);
	tree1.init(sz);
	tree2.init(sz);

	for (auto &[x, op, i]:E){
		if (op==2){
			tree2.update(x, Y1[i], Y2[i]-1, -X[X1[i]], 1);
		}

		else if (op==1){ // 삭제 먼저
			tree2.update(x, Y1[i], Y2[i]-1, 0, 0);
			tree1.update(x, Y1[i], Y2[i]-1, X[X2[i]] - X[X1[i]]);
		}

		// else if (op==3 || op==4){
			// int l = upper_bound(Y.begin(), Y.end(), Y3[i]) - Y.begin() - 1;
			// int r = lower_bound(Y.begin(), Y.end(), Y4[i]) - Y.begin();

			// ll S = tree1.query(x, l, r-1);
			// ll tmpl = tree1.query(x, l, l) / (Y[l+1] - Y[l]);
			// ll tmpr = tree1.query(x, r-1, r-1) / (Y[r] - Y[r-1]);
			// S += tmpl * (-Y3[i] + Y[l]) + tmpr * (-Y[r] + Y4[i]);

			// auto [ofs, cnt] = tree2.query(x, l, r-1);
			// auto [ofsl, cntl] = tree2.query(x, l, l);
			// auto [ofsr, cntr] = tree2.query(x, r-1, r-1);

			// ofsl /= (Y[l+1] - Y[l]), cntl /= (Y[l+1] - Y[l]);
			// ofsr /= (Y[r] - Y[r-1]), cntr /= (Y[r] - Y[r-1]);

			// ofs += ofsl * (-Y3[i] + Y[l]), cnt += cntl * (-Y3[i] + Y[l]);
			// ofs += ofsr * (-Y[r] + Y4[i]), cnt += cntr * (-Y[r] + Y4[i]);

			// if (op==3) S += cnt * X3[i] + ofs;
			// else S += cnt * X4[i] + ofs;

			// if (op==3) S = -S;
			// ans[i] += S;
		// }
	}

	ll pans = 0;
	for (int i=1;i<=q;i++){
		int v;
		scanf("%lld %lld %lld %lld %d", X3+i, Y3+i, X4+i, Y4+i, &v);

		pans %= MOD;
		X3[i] = (X3[i] + pans * v) % MOD;
		X4[i] = (X4[i] + pans * v) % MOD;
		Y3[i] = (Y3[i] + pans * v) % MOD;
		Y4[i] = (Y4[i] + pans * v) % MOD;
		if (X3[i] > X4[i]) swap(X3[i], X4[i]);
		if (Y3[i] > Y4[i]) swap(Y3[i], Y4[i]);
		
		{
		int op = 3;
		int x = X3[i];
		int l = upper_bound(Y.begin(), Y.end(), Y3[i]) - Y.begin() - 1;
		int r = lower_bound(Y.begin(), Y.end(), Y4[i]) - Y.begin();

		ll S = tree1.query(x, l, r-1);
		ll tmpl = tree1.query(x, l, l) / (Y[l+1] - Y[l]);
		ll tmpr = tree1.query(x, r-1, r-1) / (Y[r] - Y[r-1]);
		S += tmpl * (-Y3[i] + Y[l]) + tmpr * (-Y[r] + Y4[i]);

		auto [ofs, cnt] = tree2.query(x, l, r-1);
		auto [ofsl, cntl] = tree2.query(x, l, l);
		auto [ofsr, cntr] = tree2.query(x, r-1, r-1);

		ofsl /= (Y[l+1] - Y[l]), cntl /= (Y[l+1] - Y[l]);
		ofsr /= (Y[r] - Y[r-1]), cntr /= (Y[r] - Y[r-1]);

		ofs += ofsl * (-Y3[i] + Y[l]), cnt += cntl * (-Y3[i] + Y[l]);
		ofs += ofsr * (-Y[r] + Y4[i]), cnt += cntr * (-Y[r] + Y4[i]);

		if (op==3) S += cnt * X3[i] + ofs;
		else S += cnt * X4[i] + ofs;

		if (op==3) S = -S;
		ans[i] += S;
		}


		{
		int op = 4;
		int x = X4[i];
		int l = upper_bound(Y.begin(), Y.end(), Y3[i]) - Y.begin() - 1;
		int r = lower_bound(Y.begin(), Y.end(), Y4[i]) - Y.begin();

		ll S = tree1.query(x, l, r-1);
		ll tmpl = tree1.query(x, l, l) / (Y[l+1] - Y[l]);
		ll tmpr = tree1.query(x, r-1, r-1) / (Y[r] - Y[r-1]);
		S += tmpl * (-Y3[i] + Y[l]) + tmpr * (-Y[r] + Y4[i]);

		auto [ofs, cnt] = tree2.query(x, l, r-1);
		auto [ofsl, cntl] = tree2.query(x, l, l);
		auto [ofsr, cntr] = tree2.query(x, r-1, r-1);

		ofsl /= (Y[l+1] - Y[l]), cntl /= (Y[l+1] - Y[l]);
		ofsr /= (Y[r] - Y[r-1]), cntr /= (Y[r] - Y[r-1]);

		ofs += ofsl * (-Y3[i] + Y[l]), cnt += cntl * (-Y3[i] + Y[l]);
		ofs += ofsr * (-Y[r] + Y4[i]), cnt += cntr * (-Y[r] + Y4[i]);

		if (op==3) S += cnt * X3[i] + ofs;
		else S += cnt * X4[i] + ofs;

		if (op==3) S = -S;
		ans[i] += S;
		}

		pans = ans[i];
	}

	for (int i=1;i<=q;i++) printf("%lld\n", ans[i]);

}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:210:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  210 |  scanf("%d %d %d %d %d", &r, &c, &n, &q, &MOD);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:218:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  218 |   scanf("%lld %lld %lld %lld", X1+i, Y1+i, X2+i, Y2+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:312:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  312 |   scanf("%lld %lld %lld %lld %d", X3+i, Y3+i, X4+i, Y4+i, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3540 KB Output is correct
2 Correct 4 ms 3796 KB Output is correct
3 Correct 4 ms 3796 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3540 KB Output is correct
2 Correct 4 ms 3796 KB Output is correct
3 Correct 4 ms 3796 KB Output is correct
4 Correct 84 ms 58416 KB Output is correct
5 Correct 68 ms 52508 KB Output is correct
6 Correct 84 ms 56884 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3540 KB Output is correct
2 Correct 4 ms 3796 KB Output is correct
3 Correct 4 ms 3796 KB Output is correct
4 Correct 84 ms 58416 KB Output is correct
5 Correct 68 ms 52508 KB Output is correct
6 Correct 84 ms 56884 KB Output is correct
7 Correct 585 ms 352696 KB Output is correct
8 Correct 1417 ms 895836 KB Output is correct
9 Correct 870 ms 758236 KB Output is correct
10 Correct 1364 ms 888072 KB Output is correct
11 Correct 1047 ms 742116 KB Output is correct
12 Correct 1290 ms 845308 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3540 KB Output is correct
2 Correct 4 ms 3796 KB Output is correct
3 Correct 4 ms 3796 KB Output is correct
4 Correct 84 ms 58416 KB Output is correct
5 Correct 68 ms 52508 KB Output is correct
6 Correct 84 ms 56884 KB Output is correct
7 Correct 446 ms 339668 KB Output is correct
8 Correct 1609 ms 884712 KB Output is correct
9 Correct 834 ms 746712 KB Output is correct
10 Correct 1235 ms 875852 KB Output is correct
11 Correct 956 ms 737496 KB Output is correct
12 Correct 1177 ms 807940 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3540 KB Output is correct
2 Correct 4 ms 3796 KB Output is correct
3 Correct 4 ms 3796 KB Output is correct
4 Correct 84 ms 58416 KB Output is correct
5 Correct 68 ms 52508 KB Output is correct
6 Correct 84 ms 56884 KB Output is correct
7 Correct 585 ms 352696 KB Output is correct
8 Correct 1417 ms 895836 KB Output is correct
9 Correct 870 ms 758236 KB Output is correct
10 Correct 1364 ms 888072 KB Output is correct
11 Correct 1047 ms 742116 KB Output is correct
12 Correct 1290 ms 845308 KB Output is correct
13 Correct 446 ms 339668 KB Output is correct
14 Correct 1609 ms 884712 KB Output is correct
15 Correct 834 ms 746712 KB Output is correct
16 Correct 1235 ms 875852 KB Output is correct
17 Correct 956 ms 737496 KB Output is correct
18 Correct 1177 ms 807940 KB Output is correct
19 Correct 537 ms 488840 KB Output is correct
20 Correct 1406 ms 908256 KB Output is correct
21 Correct 812 ms 744276 KB Output is correct
22 Correct 1284 ms 898668 KB Output is correct
23 Correct 1014 ms 747972 KB Output is correct
24 Correct 1186 ms 829844 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 325524 KB Output is correct
2 Correct 1371 ms 866512 KB Output is correct
3 Correct 880 ms 783020 KB Output is correct
4 Correct 1287 ms 864432 KB Output is correct
5 Correct 1046 ms 732732 KB Output is correct
6 Correct 1250 ms 850912 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 325524 KB Output is correct
2 Correct 1371 ms 866512 KB Output is correct
3 Correct 880 ms 783020 KB Output is correct
4 Correct 1287 ms 864432 KB Output is correct
5 Correct 1046 ms 732732 KB Output is correct
6 Correct 1250 ms 850912 KB Output is correct
7 Correct 574 ms 488944 KB Output is correct
8 Correct 1431 ms 914720 KB Output is correct
9 Correct 837 ms 746952 KB Output is correct
10 Correct 1361 ms 905300 KB Output is correct
11 Correct 1002 ms 756104 KB Output is correct
12 Correct 1291 ms 835348 KB Output is correct