oj.uz

Submission #814605

# Submission time Handle Problem Language Result Execution time Memory
814605 2023-08-08T08:31:03 Z 박상훈(#10120) Posters on the wall (CPSPC17_posters) C++17
80 / 100
 1125 ms 914000 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];
	int sz, szT, szR;

	void init(int n){
		sz = n;
		tree[0] = Node(0, 0, 0, 0, 0);
		root[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 s, int e, ll x){
		update(add(), 1, sz, s, e, x);
	}

	ll query(int t, int s, int e){
		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];
	int sz, szT, szR;

	void init(int n){
		sz = n;
		tree[0] = Node(0, 0, 0, -1, 0, 0, 0);
		root[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].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 s, int e, ll ofs, int typ){
		update(add(), 1, sz, s, e, ofs, typ);
	}

	pair<ll, ll> query(int t, int s, int e){
		return query(root[t], 1, sz, s, e);
	}

}tree2;

// struct Node{
// 	ll ofs, cnt;
// 	Node(){}
// 	Node(ll _ofs, ll _cnt): ofs(_ofs), cnt(_cnt) {}

// 	Node operator + (const Node &N) const{
// 		return Node(ofs + N.ofs, cnt + N.cnt);
// 	}
// };

// struct Seg2{
// 	Node tree[800800], lazy[800800];

// 	void init(int i, int l, int r){
// 		tree[i] = Node(0, 0);
// 		lazy[i] = Node(0, -1);
// 		if (l==r) return;

// 		int m = (l+r)>>1;
// 		init(i<<1, l, m); init(i<<1|1, m+1, r);
// 	}

// 	void propagate(int i, int l, int r){
// 		if (lazy[i].cnt==-1) return;
// 		if (lazy[i].cnt==0) tree[i] = Node(0, 0);
// 		else tree[i] = Node(lazy[i].ofs * (Y[r+1] - Y[l]), Y[r+1] - Y[l]);

// 		if (l!=r){
// 			lazy[i<<1] = lazy[i];
// 			lazy[i<<1|1] = lazy[i];
// 		}

// 		lazy[i] = Node(0, -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){
// 			lazy[i] = Node(ofs, typ);
// 			propagate(i, l, r);
// 			return;
// 		}

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

// 	Node query(int i, int l, int r, int s, int e){
// 		propagate(i, l, r);
// 		if (r<s || e<l) return Node(0, 0);
// 		if (s<=l && r<=e) return tree[i];

// 		int m = (l+r)>>1;
// 		return query(i<<1, l, m, s, e) + query(i<<1|1, m+1, r, 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(Y1[i], Y2[i]-1, -X[X1[i]], 1);
		}

		else if (op==1){ // 삭제 먼저
			tree2.update(Y1[i], Y2[i]-1, 0, 0);
			tree1.update(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(tree1.szR-1, l, r-1);
			ll tmpl = tree1.query(tree1.szR-1, l, l) / (Y[l+1] - Y[l]);
			ll tmpr = tree1.query(tree1.szR-1, 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(tree2.szR-1, l, r-1);
			auto [ofsl, cntl] = tree2.query(tree2.szR-1, l, l);
			auto [ofsr, cntr] = tree2.query(tree2.szR-1, 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;
		}
	}

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

}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:263:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  263 |  scanf("%d %d %d %d %d", &r, &c, &n, &q, &MOD);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:271:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  271 |   scanf("%lld %lld %lld %lld", X1+i, Y1+i, X2+i, Y2+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:283:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  283 |   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 74 ms 58680 KB Output is correct
5 Correct 58 ms 52824 KB Output is correct
6 Correct 57 ms 57288 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 74 ms 58680 KB Output is correct
5 Correct 58 ms 52824 KB Output is correct
6 Correct 57 ms 57288 KB Output is correct
7 Correct 405 ms 356752 KB Output is correct
8 Correct 1080 ms 900236 KB Output is correct
9 Correct 766 ms 762632 KB Output is correct
10 Correct 952 ms 892492 KB Output is correct
11 Correct 723 ms 746584 KB Output is correct
12 Correct 898 ms 849772 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 74 ms 58680 KB Output is correct
5 Correct 58 ms 52824 KB Output is correct
6 Correct 57 ms 57288 KB Output is correct
7 Correct 455 ms 344208 KB Output is correct
8 Correct 1097 ms 889916 KB Output is correct
9 Correct 762 ms 751812 KB Output is correct
10 Correct 939 ms 880832 KB Output is correct
11 Correct 760 ms 742384 KB Output is correct
12 Correct 985 ms 812968 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 74 ms 58680 KB Output is correct
5 Correct 58 ms 52824 KB Output is correct
6 Correct 57 ms 57288 KB Output is correct
7 Correct 405 ms 356752 KB Output is correct
8 Correct 1080 ms 900236 KB Output is correct
9 Correct 766 ms 762632 KB Output is correct
10 Correct 952 ms 892492 KB Output is correct
11 Correct 723 ms 746584 KB Output is correct
12 Correct 898 ms 849772 KB Output is correct
13 Correct 455 ms 344208 KB Output is correct
14 Correct 1097 ms 889916 KB Output is correct
15 Correct 762 ms 751812 KB Output is correct
16 Correct 939 ms 880832 KB Output is correct
17 Correct 760 ms 742384 KB Output is correct
18 Correct 985 ms 812968 KB Output is correct
19 Correct 554 ms 493992 KB Output is correct
20 Correct 1125 ms 914000 KB Output is correct
21 Correct 812 ms 750004 KB Output is correct
22 Correct 1078 ms 904380 KB Output is correct
23 Correct 858 ms 753604 KB Output is correct
24 Correct 944 ms 835488 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 438 ms 364536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 438 ms 364536 KB Output isn't correct
2 Halted 0 ms 0 KB -