oj.uz

Submission #814618

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

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

	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 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 3 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 53 ms 58532 KB Output is correct
5 Correct 49 ms 52628 KB Output is correct
6 Correct 55 ms 57140 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 53 ms 58532 KB Output is correct
5 Correct 49 ms 52628 KB Output is correct
6 Correct 55 ms 57140 KB Output is correct
7 Correct 393 ms 355132 KB Output is correct
8 Correct 927 ms 898136 KB Output is correct
9 Correct 711 ms 760640 KB Output is correct
10 Correct 911 ms 890440 KB Output is correct
11 Correct 722 ms 744400 KB Output is correct
12 Correct 882 ms 847732 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 53 ms 58532 KB Output is correct
5 Correct 49 ms 52628 KB Output is correct
6 Correct 55 ms 57140 KB Output is correct
7 Correct 401 ms 342108 KB Output is correct
8 Correct 963 ms 887316 KB Output is correct
9 Correct 706 ms 749148 KB Output is correct
10 Correct 895 ms 878256 KB Output is correct
11 Correct 695 ms 739636 KB Output is correct
12 Correct 845 ms 810344 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 53 ms 58532 KB Output is correct
5 Correct 49 ms 52628 KB Output is correct
6 Correct 55 ms 57140 KB Output is correct
7 Correct 393 ms 355132 KB Output is correct
8 Correct 927 ms 898136 KB Output is correct
9 Correct 711 ms 760640 KB Output is correct
10 Correct 911 ms 890440 KB Output is correct
11 Correct 722 ms 744400 KB Output is correct
12 Correct 882 ms 847732 KB Output is correct
13 Correct 401 ms 342108 KB Output is correct
14 Correct 963 ms 887316 KB Output is correct
15 Correct 706 ms 749148 KB Output is correct
16 Correct 895 ms 878256 KB Output is correct
17 Correct 695 ms 739636 KB Output is correct
18 Correct 845 ms 810344 KB Output is correct
19 Correct 556 ms 491256 KB Output is correct
20 Correct 990 ms 910772 KB Output is correct
21 Correct 695 ms 746572 KB Output is correct
22 Correct 926 ms 900976 KB Output is correct
23 Correct 682 ms 750304 KB Output is correct
24 Correct 889 ms 832216 KB Output is correct

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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