oj.uz

Submission #814467

# Submission time Handle Problem Language Result Execution time Memory
814467 2023-08-08T07:41:29 Z 박상훈(#10120) Posters on the wall (CPSPC17_posters) C++17
80 / 100
 398 ms 25132 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 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]);

		// X.push_back(X3[i]);
		// X.push_back(X4[i]);
		// Y.push_back(Y3[i]);
		// Y.push_back(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++){
		// X3[i] = getidx(X, X3[i]);
		// X4[i] = getidx(X, X4[i]);
		// Y3[i] = getidx(Y, Y3[i]);
		// Y4[i] = getidx(Y, Y4[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(1, 1, 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(1, 1, sz, 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(1, 1, sz, l, r-1);
			ll tmpl = tree1.query(1, 1, sz, l, l) / (Y[l+1] - Y[l]);
			ll tmpr = tree1.query(1, 1, sz, 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:124:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |  scanf("%d %d %d %d %d", &r, &c, &n, &q, &MOD);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |   scanf("%lld %lld %lld %lld", X1+i, Y1+i, X2+i, Y2+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:144:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |   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 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 24 ms 2296 KB Output is correct
5 Correct 23 ms 2108 KB Output is correct
6 Correct 23 ms 2428 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 24 ms 2296 KB Output is correct
5 Correct 23 ms 2108 KB Output is correct
6 Correct 23 ms 2428 KB Output is correct
7 Correct 215 ms 18548 KB Output is correct
8 Correct 389 ms 24868 KB Output is correct
9 Correct 303 ms 18472 KB Output is correct
10 Correct 395 ms 24780 KB Output is correct
11 Correct 300 ms 18584 KB Output is correct
12 Correct 369 ms 24744 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 24 ms 2296 KB Output is correct
5 Correct 23 ms 2108 KB Output is correct
6 Correct 23 ms 2428 KB Output is correct
7 Correct 235 ms 18704 KB Output is correct
8 Correct 377 ms 24864 KB Output is correct
9 Correct 311 ms 18580 KB Output is correct
10 Correct 364 ms 24876 KB Output is correct
11 Correct 301 ms 18744 KB Output is correct
12 Correct 349 ms 24984 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 24 ms 2296 KB Output is correct
5 Correct 23 ms 2108 KB Output is correct
6 Correct 23 ms 2428 KB Output is correct
7 Correct 215 ms 18548 KB Output is correct
8 Correct 389 ms 24868 KB Output is correct
9 Correct 303 ms 18472 KB Output is correct
10 Correct 395 ms 24780 KB Output is correct
11 Correct 300 ms 18584 KB Output is correct
12 Correct 369 ms 24744 KB Output is correct
13 Correct 235 ms 18704 KB Output is correct
14 Correct 377 ms 24864 KB Output is correct
15 Correct 311 ms 18580 KB Output is correct
16 Correct 364 ms 24876 KB Output is correct
17 Correct 301 ms 18744 KB Output is correct
18 Correct 349 ms 24984 KB Output is correct
19 Correct 267 ms 25120 KB Output is correct
20 Correct 398 ms 25120 KB Output is correct
21 Correct 291 ms 18724 KB Output is correct
22 Correct 389 ms 25132 KB Output is correct
23 Correct 305 ms 18852 KB Output is correct
24 Correct 366 ms 25096 KB Output is correct

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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