oj.uz

답안 #814033

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
814033 2023-08-08T05:09:01 Z 박상훈(#10120) Posters on the wall (CPSPC17_posters) C++17
10 / 100
 3500 ms 13568 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 cnt[505][505];
void naive(int n, int q){
	for (int i=1;i<=n;i++){
		for (int j=X1[i];j<X2[i];j++){
			for (int k=Y1[i];k<Y2[i];k++){
				cnt[j][k]++;
			}
		}
	}

	for (int i=1;i<=q;i++){
		for (int j=X3[i];j<X4[i];j++){
			for (int k=Y3[i];k<Y4[i];k++){
				ans[i] += cnt[j][k];
			}
		}

		printf("%lld\n", ans[i]);
	}
}

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]);
	}

	naive(n, q);
	return 0;
	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({X1[i], 2, i});
		E.push_back({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){
			ll S = tree1.query(1, 1, sz, Y3[i], Y4[i]-1);
			auto [ofs, cnt] = tree2.query(1, 1, sz, Y3[i], Y4[i]-1);
			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:144:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |  scanf("%d %d %d %d %d", &r, &c, &n, &q, &MOD);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |   scanf("%lld %lld %lld %lld", X1+i, Y1+i, X2+i, Y2+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:164:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |   scanf("%lld %lld %lld %lld %d", X3+i, Y3+i, X4+i, Y4+i, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1236 KB Output is correct
2 Correct 6 ms 1352 KB Output is correct
3 Correct 6 ms 1364 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1236 KB Output is correct
2 Correct 6 ms 1352 KB Output is correct
3 Correct 6 ms 1364 KB Output is correct
4 Execution timed out 3577 ms 10924 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1236 KB Output is correct
2 Correct 6 ms 1352 KB Output is correct
3 Correct 6 ms 1364 KB Output is correct
4 Execution timed out 3577 ms 10924 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1236 KB Output is correct
2 Correct 6 ms 1352 KB Output is correct
3 Correct 6 ms 1364 KB Output is correct
4 Execution timed out 3577 ms 10924 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1236 KB Output is correct
2 Correct 6 ms 1352 KB Output is correct
3 Correct 6 ms 1364 KB Output is correct
4 Execution timed out 3577 ms 10924 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 44 ms 13568 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 44 ms 13568 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -