| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 330259 |
2020-11-24T09:57:18 Z |
Eric_hoo |
Plahte (COCI17_plahte) |
C++14 |
|
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]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
