제출 #1128574

#제출 시각아이디문제언어결과실행 시간메모리
1128574TrendBattlesPlahte (COCI17_plahte)C++17
0 / 160
338 ms49464 KiB
#include <bits/stdc++.h> using namespace std; using lli = int64_t; #define INFILE "present.inp" #define OUTFILE "present.out" struct Rectangle { int a, b, c, d; Rectangle(int _a = 0, int _b = 0, int _c = 0, int _d = 0): a(_a), b(_b), c(_c), d(_d) {} }; struct Compressed_Data { vector <int> comp_value; Compressed_Data() {} void add(int x) { comp_value.push_back(x); } void build() { sort(comp_value.begin(), comp_value.end()); comp_value.erase(unique(comp_value.begin(), comp_value.end()), comp_value.end()); } int get_pos(int x) { int id = lower_bound(comp_value.begin(), comp_value.end(), x) - comp_value.begin(); return id >= (int) comp_value.size() or comp_value[id] != x ? -1 : id; } int get_size() const { return (int) comp_value.size(); } void debug() { cerr << "DEBUG\n"; for (int x : comp_value) cerr << x << ' '; cerr << '\n'; } }; const int inf_32 = 0x3f3f3f3f; struct SegmentTree { vector <int> node, lazy; int N; SegmentTree(int N): N(N), node(N << 2, inf_32), lazy(N << 2, inf_32) { } void Apply(int v, int id); void Push(int v); void update_range(int v, int tl, int tr, int l, int r, int id); void update_range(int l, int r, int id); int get_value(int pos); }; int main() { ios::sync_with_stdio(0); cin.tie(0); if (fopen(INFILE, "r")) { freopen(INFILE, "r", stdin); freopen(OUTFILE, "w", stdout); } int N, Q; cin >> N >> Q; vector <Rectangle> rect(N); Compressed_Data X_pos, Y_pos; for (Rectangle& R : rect) { cin >> R.a >> R.b >> R.c >> R.d; X_pos.add(R.a); X_pos.add(R.c); Y_pos.add(R.b); Y_pos.add(R.d); } vector <int> present_X(Q), present_Y(Q), color(Q); for (int i = 0; i < Q; ++i) { cin >> present_X[i] >> present_Y[i] >> color[i]; X_pos.add(present_X[i]); Y_pos.add(present_Y[i]); } X_pos.build(); Y_pos.build(); for (Rectangle& R : rect) { R.a = X_pos.get_pos(R.a); R.c = X_pos.get_pos(R.c); R.b = Y_pos.get_pos(R.b); R.d = Y_pos.get_pos(R.d); } for (int i = 0; i < Q; ++i) { present_X[i] = X_pos.get_pos(present_X[i]); present_Y[i] = Y_pos.get_pos(present_Y[i]); } const int M = X_pos.get_size(); vector <vector <int>> open_line(M), presents(M), close_line(M); for (int i = 0; i < N; ++i) { Rectangle& R = rect[i]; open_line[R.a].push_back(i); close_line[R.c].push_back(i); } for (int i = 0; i < Q; ++i) { presents[present_X[i]].push_back(i); } SegmentTree tree(Y_pos.get_size()); vector <set <int>> color_set(N); vector <vector <int>> graph(N); for (int _ = 0; _ < M; ++_) { //cerr << "NOW: " << X_pos.comp_value[_] << '\n'; for (int x : open_line[_]) { Rectangle& R = rect[x]; //cerr << "OPEN " << x << '\n'; int p = tree.get_value(R.c); if (p >= 0 and p < N) { graph[p].push_back(x); } tree.update_range(R.b, R.d, x); } for (int id : presents[_]) { int p = tree.get_value(present_Y[id]); //cerr << "CHECK " << id << ' ' << p << '\n'; if (p >= 0 and p < N) { color_set[p].insert(color[id]); } } for (int x : close_line[_]) { //cerr << "CLOSE " << x << '\n'; Rectangle& R = rect[x]; tree.update_range(R.b, R.d, x + N); } } vector <int> visited(N), finale(N); auto DFS = [&] (auto DFS, int u) -> void { if (visited[u]) return; visited[u] = true; for (int v : graph[u]) { DFS(DFS, v); if ((int) color_set[u].size() < color_set[v].size()) color_set[u].swap(color_set[v]); for (int x : color_set[v]) color_set[u].insert(x); color_set[v].clear(); } finale[u] = (int) color_set[u].size(); }; for (int i = 0; i < N; ++i) { DFS(DFS, i); cout << finale[i] << '\n'; } return 0; } void SegmentTree::Apply(int v, int id) { node[v] = lazy[v] = id; } void SegmentTree::Push(int v) { if (lazy[v] >= inf_32 / 2) return; for (int child : {v << 1, v << 1 | 1}) { Apply(child, lazy[v]); } lazy[v] = inf_32; } void SegmentTree::update_range(int v, int tl, int tr, int l, int r, int id) { if (l > r) return; if (l == tl and r == tr) { Apply(v, id); return; } int tm = (tl + tr) >> 1; Push(v); update_range(v << 1, tl, tm, l, min(r, tm), id); update_range(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r, id); } void SegmentTree::update_range(int l, int r, int id) { update_range(1, 0, N - 1, l, r, id); } int SegmentTree::get_value(int pos) { int v = 1, l = 0, r = N - 1; while (l < r) { Push(v); int mid = (l + r) >> 1; if (pos <= mid) { v <<= 1; r = mid; } else { v = v << 1 | 1; l = mid + 1; } } return node[v]; } /* 10 10 18 20 27 25 33 29 34 30 41 39 47 50 7 5 17 19 31 26 32 28 8 8 16 17 43 48 46 49 9 11 11 15 20 22 22 24 36 32 38 36 32 28 6 17 8 9 18 20 2 16 8 10 35 30 7 48 32 8 27 28 7 16 8 8 50 28 9 41 50 4 */

컴파일 시 표준 에러 (stderr) 메시지

plahte.cpp: In function 'int main()':
plahte.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen(INFILE, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
plahte.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(OUTFILE, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...