oj.uz

Submission #814549

# Submission time Handle Problem Language Result Execution time Memory
814549 2023-08-08T08:18:39 Z 박상훈(#10120) Posters on the wall (CPSPC17_posters) C++17
80 / 100
 702 ms 339940 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 (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 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:168:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |  scanf("%d %d %d %d %d", &r, &c, &n, &q, &MOD);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:176:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |   scanf("%lld %lld %lld %lld", X1+i, Y1+i, X2+i, Y2+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:188:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |   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 2 ms 1492 KB Output is correct
2 Correct 3 ms 1672 KB Output is correct
3 Correct 3 ms 1620 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 3 ms 1672 KB Output is correct
3 Correct 3 ms 1620 KB Output is correct
4 Correct 37 ms 22244 KB Output is correct
5 Correct 32 ms 19876 KB Output is correct
6 Correct 33 ms 21940 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 3 ms 1672 KB Output is correct
3 Correct 3 ms 1620 KB Output is correct
4 Correct 37 ms 22244 KB Output is correct
5 Correct 32 ms 19876 KB Output is correct
6 Correct 33 ms 21940 KB Output is correct
7 Correct 266 ms 113476 KB Output is correct
8 Correct 622 ms 335200 KB Output is correct
9 Correct 472 ms 271696 KB Output is correct
10 Correct 639 ms 335036 KB Output is correct
11 Correct 467 ms 281124 KB Output is correct
12 Correct 573 ms 315856 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 3 ms 1672 KB Output is correct
3 Correct 3 ms 1620 KB Output is correct
4 Correct 37 ms 22244 KB Output is correct
5 Correct 32 ms 19876 KB Output is correct
6 Correct 33 ms 21940 KB Output is correct
7 Correct 264 ms 109860 KB Output is correct
8 Correct 620 ms 331424 KB Output is correct
9 Correct 452 ms 267684 KB Output is correct
10 Correct 576 ms 330596 KB Output is correct
11 Correct 469 ms 279372 KB Output is correct
12 Correct 554 ms 300000 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 3 ms 1672 KB Output is correct
3 Correct 3 ms 1620 KB Output is correct
4 Correct 37 ms 22244 KB Output is correct
5 Correct 32 ms 19876 KB Output is correct
6 Correct 33 ms 21940 KB Output is correct
7 Correct 266 ms 113476 KB Output is correct
8 Correct 622 ms 335200 KB Output is correct
9 Correct 472 ms 271696 KB Output is correct
10 Correct 639 ms 335036 KB Output is correct
11 Correct 467 ms 281124 KB Output is correct
12 Correct 573 ms 315856 KB Output is correct
13 Correct 264 ms 109860 KB Output is correct
14 Correct 620 ms 331424 KB Output is correct
15 Correct 452 ms 267684 KB Output is correct
16 Correct 576 ms 330596 KB Output is correct
17 Correct 469 ms 279372 KB Output is correct
18 Correct 554 ms 300000 KB Output is correct
19 Correct 351 ms 156732 KB Output is correct
20 Correct 678 ms 339940 KB Output is correct
21 Correct 458 ms 266600 KB Output is correct
22 Correct 702 ms 339208 KB Output is correct
23 Correct 501 ms 283152 KB Output is correct
24 Correct 646 ms 307720 KB Output is correct

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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