oj.uz

Submission #814614

# Submission time Handle Problem Language Result Execution time Memory
814614 2023-08-08T08:34:27 Z 박상훈(#10120) Posters on the wall (CPSPC17_posters) C++17
80 / 100
 1043 ms 910468 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], 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]);
	}

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

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

}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:207:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  207 |  scanf("%d %d %d %d %d", &r, &c, &n, &q, &MOD);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:215:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  215 |   scanf("%lld %lld %lld %lld", X1+i, Y1+i, X2+i, Y2+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:227:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  227 |   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 3796 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 4 ms 3796 KB Output is correct
3 Correct 4 ms 3924 KB Output is correct
4 Correct 54 ms 58628 KB Output is correct
5 Correct 50 ms 52628 KB Output is correct
6 Correct 53 ms 57144 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 3796 KB Output is correct
3 Correct 4 ms 3924 KB Output is correct
4 Correct 54 ms 58628 KB Output is correct
5 Correct 50 ms 52628 KB Output is correct
6 Correct 53 ms 57144 KB Output is correct
7 Correct 451 ms 354852 KB Output is correct
8 Correct 1000 ms 897956 KB Output is correct
9 Correct 712 ms 760360 KB Output is correct
10 Correct 1043 ms 890244 KB Output is correct
11 Correct 697 ms 744248 KB Output is correct
12 Correct 961 ms 847624 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 3796 KB Output is correct
3 Correct 4 ms 3924 KB Output is correct
4 Correct 54 ms 58628 KB Output is correct
5 Correct 50 ms 52628 KB Output is correct
6 Correct 53 ms 57144 KB Output is correct
7 Correct 399 ms 341836 KB Output is correct
8 Correct 1040 ms 886940 KB Output is correct
9 Correct 745 ms 748864 KB Output is correct
10 Correct 968 ms 877932 KB Output is correct
11 Correct 733 ms 739452 KB Output is correct
12 Correct 883 ms 810096 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 3796 KB Output is correct
3 Correct 4 ms 3924 KB Output is correct
4 Correct 54 ms 58628 KB Output is correct
5 Correct 50 ms 52628 KB Output is correct
6 Correct 53 ms 57144 KB Output is correct
7 Correct 451 ms 354852 KB Output is correct
8 Correct 1000 ms 897956 KB Output is correct
9 Correct 712 ms 760360 KB Output is correct
10 Correct 1043 ms 890244 KB Output is correct
11 Correct 697 ms 744248 KB Output is correct
12 Correct 961 ms 847624 KB Output is correct
13 Correct 399 ms 341836 KB Output is correct
14 Correct 1040 ms 886940 KB Output is correct
15 Correct 745 ms 748864 KB Output is correct
16 Correct 968 ms 877932 KB Output is correct
17 Correct 733 ms 739452 KB Output is correct
18 Correct 883 ms 810096 KB Output is correct
19 Correct 555 ms 491092 KB Output is correct
20 Correct 1022 ms 910468 KB Output is correct
21 Correct 762 ms 746320 KB Output is correct
22 Correct 975 ms 900872 KB Output is correct
23 Correct 716 ms 750112 KB Output is correct
24 Correct 934 ms 832108 KB Output is correct

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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