oj.uz

Submission #814880

# Submission time Handle Problem Language Result Execution time Memory
814880 2023-08-08T10:53:55 Z qwerasdfzxcl Posters on the wall (CPSPC17_posters) C++17
100 / 100
 1752 ms 914648 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[14001400];
	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 5 ms 3788 KB Output is correct
3 Correct 4 ms 3924 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 5 ms 3788 KB Output is correct
3 Correct 4 ms 3924 KB Output is correct
4 Correct 78 ms 58628 KB Output is correct
5 Correct 67 ms 52564 KB Output is correct
6 Correct 67 ms 57116 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 5 ms 3788 KB Output is correct
3 Correct 4 ms 3924 KB Output is correct
4 Correct 78 ms 58628 KB Output is correct
5 Correct 67 ms 52564 KB Output is correct
6 Correct 67 ms 57116 KB Output is correct
7 Correct 425 ms 354904 KB Output is correct
8 Correct 1439 ms 898532 KB Output is correct
9 Correct 824 ms 760912 KB Output is correct
10 Correct 1282 ms 890964 KB Output is correct
11 Correct 1006 ms 744828 KB Output is correct
12 Correct 1259 ms 848052 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 5 ms 3788 KB Output is correct
3 Correct 4 ms 3924 KB Output is correct
4 Correct 78 ms 58628 KB Output is correct
5 Correct 67 ms 52564 KB Output is correct
6 Correct 67 ms 57116 KB Output is correct
7 Correct 442 ms 342468 KB Output is correct
8 Correct 1641 ms 888128 KB Output is correct
9 Correct 847 ms 750148 KB Output is correct
10 Correct 1330 ms 879048 KB Output is correct
11 Correct 976 ms 740604 KB Output is correct
12 Correct 1172 ms 811200 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 5 ms 3788 KB Output is correct
3 Correct 4 ms 3924 KB Output is correct
4 Correct 78 ms 58628 KB Output is correct
5 Correct 67 ms 52564 KB Output is correct
6 Correct 67 ms 57116 KB Output is correct
7 Correct 425 ms 354904 KB Output is correct
8 Correct 1439 ms 898532 KB Output is correct
9 Correct 824 ms 760912 KB Output is correct
10 Correct 1282 ms 890964 KB Output is correct
11 Correct 1006 ms 744828 KB Output is correct
12 Correct 1259 ms 848052 KB Output is correct
13 Correct 442 ms 342468 KB Output is correct
14 Correct 1641 ms 888128 KB Output is correct
15 Correct 847 ms 750148 KB Output is correct
16 Correct 1330 ms 879048 KB Output is correct
17 Correct 976 ms 740604 KB Output is correct
18 Correct 1172 ms 811200 KB Output is correct
19 Correct 541 ms 492264 KB Output is correct
20 Correct 1391 ms 912232 KB Output is correct
21 Correct 835 ms 748128 KB Output is correct
22 Correct 1283 ms 902612 KB Output is correct
23 Correct 965 ms 751840 KB Output is correct
24 Correct 1212 ms 833656 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 327892 KB Output is correct
2 Correct 1435 ms 869052 KB Output is correct
3 Correct 883 ms 785580 KB Output is correct
4 Correct 1301 ms 867076 KB Output is correct
5 Correct 1004 ms 735320 KB Output is correct
6 Correct 1339 ms 853472 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 327892 KB Output is correct
2 Correct 1435 ms 869052 KB Output is correct
3 Correct 883 ms 785580 KB Output is correct
4 Correct 1301 ms 867076 KB Output is correct
5 Correct 1004 ms 735320 KB Output is correct
6 Correct 1339 ms 853472 KB Output is correct
7 Correct 770 ms 493032 KB Output is correct
8 Correct 1611 ms 914648 KB Output is correct
9 Correct 935 ms 748648 KB Output is correct
10 Correct 1752 ms 906520 KB Output is correct
11 Correct 1117 ms 756164 KB Output is correct
12 Correct 1332 ms 835312 KB Output is correct