Submission #636551

#TimeUsernameProblemLanguageResultExecution timeMemory
636551vovamrSunčanje (COCI18_suncanje)C++17
0 / 130
4062 ms262144 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define fi first #define se second #define ll long long #define ld long double #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define pb push_back #define mpp make_pair #define ve vector using namespace std; using namespace __gnu_pbds; template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; const ll inf = 1e18; const int iinf = 1e9; typedef pair<ll, ll> pll; typedef pair<int, int> pii; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); } template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); } struct fenw { int n; ve<ve<int>> que; ve<ve<int>> fe; fenw(int s) : n(s + 10) { que.resize(n); fe.resize(n); } inline void pupd(int x, int y) { x += 3; for (; x < n; x += x & -x) que[x].pb(y); } inline void pget(int x, int y) { if(x<0||y<0){return;} x += 3; for (; x; x -= x & -x) que[x].pb(y); } inline void pget(int x0, int x1, int y0, int y1) { pget(x1, y1); pget(x0 - 1, y1); pget(x1, y0 - 1); pget(x0 - 1, y0 - 1); } inline void prep() { for (int i = 0; i < n; ++i) { sort(all(que[i])); que[i].erase(unique(all(que[i])), que[i].end()); fe[i].resize(sz(que[i]) + 10); } } inline void upd(int x, int y, int d) { x += 3; for (; x < n; x += x & -x) { int i = lower_bound(all(que[x]), y) - que[x].begin() + 3; for (; i < sz(fe[i]); i += i & -i) fe[x][i] += d; } } inline int get(int x, int y) { if (x < 0 || y < 0) return 0; x += 3; int ans = 0; for (; x; x -= x & -x) { int i = lower_bound(all(que[x]), y) - que[x].begin() + 3; for (; i; i -= i & -i) ans += fe[x][i]; } return ans; } inline int get(int x0, int x1, int y0, int y1) { if (x0 > x1 || y0 > y1) return 0; return get(x1, y1) - get(x0 - 1, y1) - get(x1, y0 - 1) + get(x0 - 1, y0 - 1); } }; inline void solve() { int n; cin >> n; ve<array<int,4>> a(n); for (auto &[a, b, c, d] : a) cin >> a >> b >> c >> d; ve<int> alx, aly; for (int i = 0; i < n; ++i) { auto &[x, y, dx, dy] = a[i]; int x0 = x, x1 = x + dx - 1; int y0 = y, y1 = y + dy - 1; alx.pb(x0), alx.pb(x1); aly.pb(y0), aly.pb(y1); } sort(all(alx)), sort(all(aly)); alx.erase(unique(all(alx)), alx.end()); aly.erase(unique(all(aly)), aly.end()); int m = sz(alx), my = sz(aly); for (int i = 0; i < n; ++i) { auto &[x, y, dx, dy] = a[i]; int x0 = x, x1 = x + dx - 1; int y0 = y, y1 = y + dy - 1; x0 = lower_bound(all(alx), x0) - alx.begin(); x1 = lower_bound(all(alx), x1) - alx.begin(); y0 = lower_bound(all(aly), y0) - aly.begin(); y1 = lower_bound(all(aly), y1) - aly.begin(); a[i] = {x0, y0, x1, y1}; } fenw right_down(m); fenw left_down(m); fenw right_up(m); fenw left_up(m); reverse(all(a)); for (auto &[x0, y0, x1, y1] : a) { right_down.pupd(x1, y1); left_down.pupd(x1, y0); right_up.pupd(x0, y1); left_up.pupd(x0, y0); right_down.pget(x0 - 1, my - 1); right_down.pget(m - 1, y0 - 1); left_up.pget(0, m - 1, y1 + 1, my - 1); left_up.pget(x1 + 1, m - 1, 0, my - 1); right_down.pget(x0 - 1, y0 - 1); left_up.pget(x1 + 1, m - 1, y1 + 1, my - 1); right_up.pget(x1 + 1, m - 1, 0, y0 - 1); left_down.pget(0, x0 - 1, y1 + 1, my - 1); } right_down.prep(); left_down.prep(); right_up.prep(); left_up.prep(); ve<int> res(n); int ptr = n - 1, cnt = 0; for (auto &[x0, y0, x1, y1] : a) { right_down.upd(x1, y1, +1); left_down.upd(x1, y0, +1); right_up.upd(x0, y1, +1); left_up.upd(x0, y0, +1); int ans = 0; ans += right_down.get(x0 - 1, my - 1); ans += right_down.get(m - 1, y0 - 1); ans += left_up.get(0, m - 1, y1 + 1, my - 1); ans += left_up.get(x1 + 1, m - 1, 0, my - 1); ans -= right_down.get(x0 - 1, y0 - 1); ans -= left_up.get(x1 + 1, m - 1, y1 + 1, my - 1); ans -= right_up.get(x1 + 1, m - 1, 0, y0 - 1); ans -= left_down.get(0, x0 - 1, y1 + 1, my - 1); res[ptr--] = (ans == cnt); ++cnt; } for (auto &i : res) cout << (i ? "DA" : "NE") << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int q = 1; // cin >> q; while (q--) solve(); cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl; } /** 5 1 1 4 2 6 1 1 1 2 2 2 3 3 4 3 2 4 0 1 2 */
#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...
#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...