oj.uz

Submission #814887

# Submission time Handle Problem Language Result Execution time Memory
814887 2023-08-08T10:55:28 Z qwerasdfzxcl Posters on the wall (CPSPC17_posters) C++17
100 / 100
 1516 ms 910664 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[12001200];
	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]);
	}

	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});
	}

	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]]);
		}
	}

	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:268:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  268 |   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 3668 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 4 ms 3540 KB Output is correct
2 Correct 4 ms 3668 KB Output is correct
3 Correct 4 ms 3796 KB Output is correct
4 Correct 81 ms 58308 KB Output is correct
5 Correct 68 ms 52372 KB Output is correct
6 Correct 70 ms 57028 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 3668 KB Output is correct
3 Correct 4 ms 3796 KB Output is correct
4 Correct 81 ms 58308 KB Output is correct
5 Correct 68 ms 52372 KB Output is correct
6 Correct 70 ms 57028 KB Output is correct
7 Correct 474 ms 352680 KB Output is correct
8 Correct 1516 ms 896056 KB Output is correct
9 Correct 862 ms 758560 KB Output is correct
10 Correct 1276 ms 888396 KB Output is correct
11 Correct 995 ms 742352 KB Output is correct
12 Correct 1401 ms 845600 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 3668 KB Output is correct
3 Correct 4 ms 3796 KB Output is correct
4 Correct 81 ms 58308 KB Output is correct
5 Correct 68 ms 52372 KB Output is correct
6 Correct 70 ms 57028 KB Output is correct
7 Correct 435 ms 339664 KB Output is correct
8 Correct 1452 ms 884764 KB Output is correct
9 Correct 933 ms 746764 KB Output is correct
10 Correct 1403 ms 875772 KB Output is correct
11 Correct 1055 ms 737380 KB Output is correct
12 Correct 1166 ms 807904 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 3668 KB Output is correct
3 Correct 4 ms 3796 KB Output is correct
4 Correct 81 ms 58308 KB Output is correct
5 Correct 68 ms 52372 KB Output is correct
6 Correct 70 ms 57028 KB Output is correct
7 Correct 474 ms 352680 KB Output is correct
8 Correct 1516 ms 896056 KB Output is correct
9 Correct 862 ms 758560 KB Output is correct
10 Correct 1276 ms 888396 KB Output is correct
11 Correct 995 ms 742352 KB Output is correct
12 Correct 1401 ms 845600 KB Output is correct
13 Correct 435 ms 339664 KB Output is correct
14 Correct 1452 ms 884764 KB Output is correct
15 Correct 933 ms 746764 KB Output is correct
16 Correct 1403 ms 875772 KB Output is correct
17 Correct 1055 ms 737380 KB Output is correct
18 Correct 1166 ms 807904 KB Output is correct
19 Correct 550 ms 489096 KB Output is correct
20 Correct 1462 ms 908584 KB Output is correct
21 Correct 840 ms 744560 KB Output is correct
22 Correct 1297 ms 898984 KB Output is correct
23 Correct 1010 ms 748252 KB Output is correct
24 Correct 1213 ms 830236 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 325456 KB Output is correct
2 Correct 1414 ms 866480 KB Output is correct
3 Correct 948 ms 782912 KB Output is correct
4 Correct 1371 ms 864448 KB Output is correct
5 Correct 1012 ms 732680 KB Output is correct
6 Correct 1278 ms 850896 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 325456 KB Output is correct
2 Correct 1414 ms 866480 KB Output is correct
3 Correct 948 ms 782912 KB Output is correct
4 Correct 1371 ms 864448 KB Output is correct
5 Correct 1012 ms 732680 KB Output is correct
6 Correct 1278 ms 850896 KB Output is correct
7 Correct 557 ms 488864 KB Output is correct
8 Correct 1506 ms 910664 KB Output is correct
9 Correct 882 ms 744652 KB Output is correct
10 Correct 1516 ms 902360 KB Output is correct
11 Correct 1210 ms 752164 KB Output is correct
12 Correct 1271 ms 831280 KB Output is correct