oj.uz

답안 #330259

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
330259 2020-11-24T09:57:18 Z Eric_hoo Plahte (COCI17_plahte) C++14
160 / 160
 323 ms 64988 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;

typedef pair <int, int> pii;

int A[80010], B[80010], C[80010], D[80010], X[80010], Y[80010], P[80010], fa[80010];
int ans[80010], in[80010];
vector <int> col, all, has[80010];
vector <pii> op;
int L, N;
queue <int> q;

struct Segment_tree {
	int T[600000];
	void Build() {memset(T, 0, sizeof(T));}
	void pushdown(int now) {
		if (T[now] == -1) return ;
		T[now << 1] = T[now << 1 | 1] = T[now];
		T[now] = -1;
	}
	void Update(int now, int l, int r, int L, int R, int x) {
		if (l == L && r == R) {
			T[now] = x;
			return ;
		}
		pushdown(now);
		int mid = l + r >> 1;
		if (R <= mid) Update(now << 1, l, mid, L, R, x);
		else if (L > mid) Update(now << 1 | 1, mid + 1, r, L, R, x);
		else Update(now << 1, l, mid, L, mid, x), Update(now << 1 | 1, mid + 1, r, mid + 1, R, x);
	}
	int Query(int now, int l, int r, int pos) {
		if (T[now] != -1) return T[now];
		int mid = l + r >> 1;
		if (pos <= mid) return Query(now << 1, l, mid, pos);
		return Query(now << 1 | 1, mid + 1, r, pos);
	}
}seg;

struct Node {
	int sum;
	Node *lson, *rson;
	Node() {sum = 0, lson = rson = NULL;}
	void pushup() {sum = (lson ? lson->sum : 0) + (rson ? rson->sum : 0);}
}*T[80010], pool[2000000], *CUR = pool;

void Update(Node *&T, int l, int r, int pos) {
	if (!T) T = CUR++;
	if (l == r) {
		T->sum = 1;
		return ;
	}
	int mid = l + r >> 1;
	if (pos <= mid) Update(T->lson, l, mid, pos);
	else Update(T->rson, mid + 1, r, pos);
	T->pushup();
}

Node *Merge(Node *L, Node *R, int l, int r) {
	if (!L || !R) return L ? L : R;
	if (l == r) {
		L->sum |= R->sum;
		return L;
	}
	int mid = l + r >> 1;
	L->lson = Merge(L->lson, R->lson, l, mid);
	L->rson = Merge(L->rson, R->rson, mid + 1, r);
	L->pushup();
	return L;
}

int main() {
	int n, m; scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]);
		all.push_back(B[i]), all.push_back(D[i] + 1);
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &X[i], &Y[i], &P[i]);
		col.push_back(P[i]);
		all.push_back(Y[i]);
	}
	sort(all.begin(), all.end()), all.resize(unique(all.begin(), all.end()) - all.begin());
	for (int i = 1; i <= n; i++) {
		B[i] = lower_bound(all.begin(), all.end(), B[i]) - all.begin() + 1;
		D[i] = lower_bound(all.begin(), all.end(), D[i] + 1) - all.begin();
	}
	for (int i = 1; i <= m; i++) {
		Y[i] = lower_bound(all.begin(), all.end(), Y[i]) - all.begin() + 1;
	}
	N = all.size();
	sort(col.begin(), col.end()), col.resize(unique(col.begin(), col.end()) - col.begin());
	L = col.size();
	for (int i = 1; i <= m; i++) {
		P[i] = lower_bound(col.begin(), col.end(), P[i]) - col.begin() + 1;
	}
	for (int i = 1; i <= n; i++) {
		op.push_back(mp(A[i], -i)), op.push_back(mp(C[i], i + m));
	}
	for (int i = 1; i <= m; i++) {
		op.push_back(mp(X[i], i));
	}
	sort(op.begin(), op.end());
	seg.Build();
	for (int i = 0; i < op.size(); i++) {
		int id = op[i].se < 0 ? -op[i].se : op[i].se > m ? op[i].se - m : op[i].se;
		if (op[i].se > m) seg.Update(1, 1, N, B[id], D[id], fa[id]);
		else if (op[i].se > 0) has[seg.Query(1, 1, N, Y[id])].push_back(P[id]);
		else fa[id] = seg.Query(1, 1, N, B[id]), seg.Update(1, 1, N, B[id], D[id], id);
	}
	for (int i = 1; i <= n; i++) {
		in[fa[i]]++;
	}
	for (int i = 1; i <= n; i++) {
		if (!in[i]) q.push(i);
	}
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (int i = 0; i < has[x].size(); i++) {
			int c = has[x][i];
			Update(T[x], 1, L, c);
		}
		ans[x] = T[x] ? T[x]->sum : 0;
		if (!fa[x]) continue;
		int p = fa[x];
		in[p]--, T[p] = Merge(T[p], T[x], 1, L);
		if (!in[p]) q.push(p);
	}
	for (int i = 1; i <= n; i++) {
		printf("%d\n", ans[i]);
	}
	return 0;
}

Compilation message

plahte.cpp: In member function 'void Segment_tree::Update(int, int, int, int, int, int)':
plahte.cpp:30:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |   int mid = l + r >> 1;
      |             ~~^~~
plahte.cpp: In member function 'int Segment_tree::Query(int, int, int, int)':
plahte.cpp:37:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   int mid = l + r >> 1;
      |             ~~^~~
plahte.cpp: In function 'void Update(Node*&, int, int, int)':
plahte.cpp:56:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |  int mid = l + r >> 1;
      |            ~~^~~
plahte.cpp: In function 'Node* Merge(Node*, Node*, int, int)':
plahte.cpp:68:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |  int mid = l + r >> 1;
      |            ~~^~~
plahte.cpp: In function 'int main()':
plahte.cpp:108:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |  for (int i = 0; i < op.size(); i++) {
      |                  ~~^~~~~~~~~~~
plahte.cpp:122:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |   for (int i = 0; i < has[x].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~
plahte.cpp:76:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |  int n, m; scanf("%d%d", &n, &m);
      |            ~~~~~^~~~~~~~~~~~~~~~
plahte.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |   scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |   scanf("%d%d%d", &X[i], &Y[i], &P[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 55820 KB Output is correct
2 Correct 109 ms 56032 KB Output is correct
3 Correct 26 ms 51564 KB Output is correct

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 56660 KB Output is correct
2 Correct 124 ms 56544 KB Output is correct
3 Correct 26 ms 51524 KB Output is correct

Subtask #3
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 186 ms 60124 KB Output is correct
2 Correct 195 ms 60124 KB Output is correct
3 Correct 26 ms 51564 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 323 ms 64600 KB Output is correct
2 Correct 316 ms 64740 KB Output is correct
3 Correct 27 ms 51564 KB Output is correct

Subtask #5
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 315 ms 64604 KB Output is correct
2 Correct 317 ms 64988 KB Output is correct
3 Correct 28 ms 51692 KB Output is correct