oj.uz

Submission #814521

# Submission time Handle Problem Language Result Execution time Memory
814521 2023-08-08T08:07:24 Z 박상훈(#10120) Posters on the wall (CPSPC17_posters) C++17
80 / 100
 682 ms 411256 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){
		propagate(i, l, r);
		if (r<s || e<l) return 0;
		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;

// struct Seg1{
// 	ll tree[800800], lazy[800800];

// 	void init(int i, int l, int r){
// 		tree[i] = lazy[i] = 0;
// 		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){
// 		tree[i] += lazy[i] * (Y[r+1] - Y[l]);

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

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

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

// 	ll query(int i, int l, int r, int s, int e){
// 		propagate(i, l, r);
// 		if (r<s || e<l) return 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);
// 	}
// }tree1;

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(1, 1, sz);

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

		else if (op==1){ // 삭제 먼저
			tree2.update(1, 1, sz, 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(1, 1, sz, l, r-1);
			auto [ofsl, cntl] = tree2.query(1, 1, sz, l, l);
			auto [ofsr, cntr] = tree2.query(1, 1, sz, 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: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:230:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  230 |   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 3 ms 1748 KB Output is correct
2 Correct 3 ms 1876 KB Output is correct
3 Correct 3 ms 1876 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1748 KB Output is correct
2 Correct 3 ms 1876 KB Output is correct
3 Correct 3 ms 1876 KB Output is correct
4 Correct 37 ms 26960 KB Output is correct
5 Correct 35 ms 24052 KB Output is correct
6 Correct 35 ms 26480 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1748 KB Output is correct
2 Correct 3 ms 1876 KB Output is correct
3 Correct 3 ms 1876 KB Output is correct
4 Correct 37 ms 26960 KB Output is correct
5 Correct 35 ms 24052 KB Output is correct
6 Correct 35 ms 26480 KB Output is correct
7 Correct 274 ms 114612 KB Output is correct
8 Correct 682 ms 404624 KB Output is correct
9 Correct 498 ms 330436 KB Output is correct
10 Correct 639 ms 407016 KB Output is correct
11 Correct 492 ms 348108 KB Output is correct
12 Correct 598 ms 374052 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1748 KB Output is correct
2 Correct 3 ms 1876 KB Output is correct
3 Correct 3 ms 1876 KB Output is correct
4 Correct 37 ms 26960 KB Output is correct
5 Correct 35 ms 24052 KB Output is correct
6 Correct 35 ms 26480 KB Output is correct
7 Correct 269 ms 111408 KB Output is correct
8 Correct 626 ms 399608 KB Output is correct
9 Correct 512 ms 324664 KB Output is correct
10 Correct 616 ms 401216 KB Output is correct
11 Correct 491 ms 345928 KB Output is correct
12 Correct 573 ms 351496 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1748 KB Output is correct
2 Correct 3 ms 1876 KB Output is correct
3 Correct 3 ms 1876 KB Output is correct
4 Correct 37 ms 26960 KB Output is correct
5 Correct 35 ms 24052 KB Output is correct
6 Correct 35 ms 26480 KB Output is correct
7 Correct 274 ms 114612 KB Output is correct
8 Correct 682 ms 404624 KB Output is correct
9 Correct 498 ms 330436 KB Output is correct
10 Correct 639 ms 407016 KB Output is correct
11 Correct 492 ms 348108 KB Output is correct
12 Correct 598 ms 374052 KB Output is correct
13 Correct 269 ms 111408 KB Output is correct
14 Correct 626 ms 399608 KB Output is correct
15 Correct 512 ms 324664 KB Output is correct
16 Correct 616 ms 401216 KB Output is correct
17 Correct 491 ms 345928 KB Output is correct
18 Correct 573 ms 351496 KB Output is correct
19 Correct 351 ms 158288 KB Output is correct
20 Correct 668 ms 409252 KB Output is correct
21 Correct 479 ms 323496 KB Output is correct
22 Correct 657 ms 411256 KB Output is correct
23 Correct 514 ms 350540 KB Output is correct
24 Correct 617 ms 359976 KB Output is correct

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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