oj.uz

Submission #814632

# Submission time Handle Problem Language Result Execution time Memory
814632 2023-08-08T08:39:34 Z 박상훈(#10120) Posters on the wall (CPSPC17_posters) C++17
90 / 100
 1458 ms 908284 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);
		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 4 ms 3540 KB Output is correct
2 Correct 4 ms 3796 KB Output is correct
3 Correct 4 ms 3880 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3540 KB Output is correct
2 Correct 4 ms 3796 KB Output is correct
3 Correct 4 ms 3880 KB Output is correct
4 Correct 71 ms 58380 KB Output is correct
5 Correct 74 ms 52392 KB Output is correct
6 Correct 75 ms 56864 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3540 KB Output is correct
2 Correct 4 ms 3796 KB Output is correct
3 Correct 4 ms 3880 KB Output is correct
4 Correct 71 ms 58380 KB Output is correct
5 Correct 74 ms 52392 KB Output is correct
6 Correct 75 ms 56864 KB Output is correct
7 Correct 405 ms 352728 KB Output is correct
8 Correct 1426 ms 895796 KB Output is correct
9 Correct 842 ms 758188 KB Output is correct
10 Correct 1246 ms 888172 KB Output is correct
11 Correct 981 ms 742056 KB Output is correct
12 Correct 1264 ms 845300 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3540 KB Output is correct
2 Correct 4 ms 3796 KB Output is correct
3 Correct 4 ms 3880 KB Output is correct
4 Correct 71 ms 58380 KB Output is correct
5 Correct 74 ms 52392 KB Output is correct
6 Correct 75 ms 56864 KB Output is correct
7 Correct 419 ms 339744 KB Output is correct
8 Correct 1458 ms 884744 KB Output is correct
9 Correct 859 ms 746764 KB Output is correct
10 Correct 1342 ms 875824 KB Output is correct
11 Correct 1039 ms 737288 KB Output is correct
12 Correct 1244 ms 807936 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3540 KB Output is correct
2 Correct 4 ms 3796 KB Output is correct
3 Correct 4 ms 3880 KB Output is correct
4 Correct 71 ms 58380 KB Output is correct
5 Correct 74 ms 52392 KB Output is correct
6 Correct 75 ms 56864 KB Output is correct
7 Correct 405 ms 352728 KB Output is correct
8 Correct 1426 ms 895796 KB Output is correct
9 Correct 842 ms 758188 KB Output is correct
10 Correct 1246 ms 888172 KB Output is correct
11 Correct 981 ms 742056 KB Output is correct
12 Correct 1264 ms 845300 KB Output is correct
13 Correct 419 ms 339744 KB Output is correct
14 Correct 1458 ms 884744 KB Output is correct
15 Correct 859 ms 746764 KB Output is correct
16 Correct 1342 ms 875824 KB Output is correct
17 Correct 1039 ms 737288 KB Output is correct
18 Correct 1244 ms 807936 KB Output is correct
19 Correct 618 ms 488860 KB Output is correct
20 Correct 1416 ms 908284 KB Output is correct
21 Correct 815 ms 744248 KB Output is correct
22 Correct 1265 ms 898724 KB Output is correct
23 Correct 960 ms 748024 KB Output is correct
24 Correct 1192 ms 829852 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 325564 KB Output is correct
2 Correct 1353 ms 869164 KB Output is correct
3 Correct 1143 ms 785536 KB Output is correct
4 Correct 1241 ms 867032 KB Output is correct
5 Correct 961 ms 735460 KB Output is correct
6 Correct 1190 ms 853484 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 325564 KB Output is correct
2 Correct 1353 ms 869164 KB Output is correct
3 Correct 1143 ms 785536 KB Output is correct
4 Correct 1241 ms 867032 KB Output is correct
5 Correct 961 ms 735460 KB Output is correct
6 Correct 1190 ms 853484 KB Output is correct
7 Incorrect 782 ms 562344 KB Output isn't correct
8 Halted 0 ms 0 KB -