제출 #375983

#제출 시각아이디문제언어결과실행 시간메모리
375983usachevd0새 집 (APIO18_new_home)C++14
80 / 100
5111 ms257084 KiB
#pragma gcc optimize("O3") #pragma gcc optimize("Ofast") #pragma gcc target("avx2") #include <iostream> #include <vector> #include <set> #include <map> #include <fstream> #include <iomanip> #include <cstring> #include <algorithm> #include <numeric> #include <random> #include <time.h> using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back #define all(a) (a).begin(), (a).end() using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; using pil = pair<int, ll>; using pli = pair<ll, int>; using pll = pair<ll, ll>; using ld = long double; template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; } template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; } void debug_out() { cerr << endl; } template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); } template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; } #ifdef DEBUG #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n) #else #define debug(...) 1337 #define mdebug(...) 1337 #endif template<typename T> ostream& operator << (ostream& stream, const vector<T> &a) { for (auto& x : a) stream << x << ' '; return stream; } template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2> &a) { stream << a.fi << ' ' << a.se; return stream; } const int INF32 = 0x3f3f3f3f; const int N = 3e5 + 5; bool task3, task34; int rx[2 * N], X; int n, Q, types; struct shop_t { int x, tp, t1, t2; } s[N]; struct query_t { int x, t, idx; } qr[N]; int ans[N]; struct event_t { int t, tp, idx; bool operator < (const event_t& oth) const { if (t != oth.t) return t < oth.t; return tp < oth.tp; } } ev[3 * N]; int events; map<int, int> type_on[N]; int tp_cnt[N]; namespace treap { mt19937 rng(time(0)); struct Node { int x, y; Node *l, *r; Node() {} Node(int _x): x(_x), y(rng()), l(0), r(0) {} }; Node* merge(Node* a, Node* b) { if (!a) return b; if (!b) return a; if (a->y > b->y) { a->r = merge(a->r, b); return a; } else { b->l = merge(a, b->l); return b; } } pair<Node*, Node*> split(Node *t, int x) { if (!t) return {0, 0}; if (t->x < x) { auto p = split(t->r, x); t->r = p.fi; return {t, p.se}; } else { auto p = split(t->l, x); t->l = p.se; return {p.fi, t}; } } void add(Node *&t, int x) { auto p = split(t, x); t = merge(p.fi, merge(new Node(x), p.se)); } void rem(Node *&t, int x) { if (!t) return; if (t->x == x) { t = merge(t->l, t->r); } else if (t->x < x) { rem(t->r, x); } else { rem(t->l, x); } } int gmin(Node *t) { if (!t) return INF32; for (; t->l; t = t->l); return t->x; } int gmax(Node *t) { if (!t) return INF32; for (; t->r; t = t->r); return t->x; } } namespace sgt { const int logN = 20; const int N = 1 << logN; treap::Node* S[2 * N]; int min3[2 * N], max3[2 * N]; void init() { memset(S, 0, sizeof S); memset(min3, 0x3f, sizeof min3); for (int i = 0; i < 2 * N; ++i) max3[i] = -INF32; } void mdf(int v, int vl, int vr, int l, int r, int x, bool rem = false) { if (l > r || vr < l || r < vl) return; if (l <= vl && vr <= r) { if (!rem) { if (!task34) { treap::add(S[v], x); } else { chkmin(min3[v], x); chkmax(max3[v], x); } } else { if (!task34) treap::rem(S[v], x); } return; } int vm = (vl + vr) >> 1; mdf(v << 1, vl, vm, l, r, x, rem); mdf(v << 1 | 1, vm + 1, vr, l, r, x, rem); } pii gt(int pos) { int min_x = INF32, max_x = -INF32; int v = 1, vl = 0, vr = X - 1; while (true) { if (!task34) { if (S[v]) { chkmin(min_x, treap::gmin(S[v])); chkmax(max_x, treap::gmax(S[v])); } } else { chkmin(min_x, min3[v]); chkmax(max_x, max3[v]); } if (vl == vr) break; int vm = (vl + vr) >> 1; if (pos <= vm) { v <<= 1; vr = vm; } else { v <<= 1; ++v; vl = vm + 1; } } return {min_x, max_x}; } } signed main() { #ifdef DEBUG freopen("in", "r", stdin); #endif ios::sync_with_stdio(0); cin.tie(0); sgt::init(); cin >> n >> types >> Q; task3 = task34 = true; for (int i = 0; i < n; ++i) { cin >> s[i].x >> s[i].tp >> s[i].t1 >> s[i].t2; task34 &= s[i].t1 == 1; task3 &= s[i].t2 == 100000000; --s[i].tp; rx[X++] = s[i].x; ev[events++] = {s[i].t1, 0, i}; ev[events++] = {s[i].t2, 2, i}; } task3 &= task34; for (int j = 0; j < Q; ++j) { cin >> qr[j].x >> qr[j].t; qr[j].idx = j; rx[X++] = qr[j].x; ev[events++] = {qr[j].t, 1, j}; } sort(rx, rx + X); X = unique(rx, rx + X) - rx; // for (int x = 0; x < X; ++x) // cx[rx[x]] = x; auto mdf = [&](int xl, int xr, int val, bool rem) { if (val == -INF32 || val == INF32) return; int il = lower_bound(rx, rx + X, xl) - rx; int ir = upper_bound(rx, rx + X, xr) - rx - 1; if (il > ir) return; sgt::mdf(1, 0, X - 1, il, ir, val, rem); }; auto mdf2 = [&](int x1, int x2, bool rem) { int xm = (x1 + x2) / 2; mdf(x1, xm, x1, rem); mdf(xm + 1, x2, x2, rem); }; for (int tp = 0; tp < types; ++tp) { type_on[tp].insert({INF32, 1}); type_on[tp].insert({-INF32, 1}); } if (task34) { for (int i = 0; i < n; ++i) { auto &a = s[i]; if (!type_on[a.tp].count(a.x)) type_on[a.tp].insert({a.x, 1}); else ++type_on[a.tp][a.x]; } for (int tp = 0; tp < types; ++tp) { auto &S = type_on[tp]; auto x = S.begin(); auto y = next(x); while (y != S.end()) { mdf2(x->fi, y->fi, false); x = y; y = next(y); } } } sort(ev, ev + events); int active_tp = 0; for (int ei = 0; ei < events; ++ei) { auto &e = ev[ei]; if (e.tp == 0) { int i = e.idx; auto &a = s[i]; if (++tp_cnt[a.tp] == 1) ++active_tp; if (task34) continue; auto &S = type_on[a.tp]; if (S.find(a.x) != S.end()) ++S[a.x]; else { S.insert({a.x, 1}); auto it = S.find(a.x); int x1 = prev(it)->fi; int x2 = next(it)->fi; mdf2(x1, x2, true); mdf2(x1, a.x, false); mdf2(a.x, x2, false); } } else if (e.tp == 2) { if (task34 && task3) break; int i = e.idx; auto &a = s[i]; if (--tp_cnt[a.tp] == 0) --active_tp; auto &S = type_on[a.tp]; if (--S[a.x] == 0) { auto it = S.find(a.x); int x1 = prev(it)->fi; int x2 = next(it)->fi; S.erase(it); mdf2(x1, a.x, true); mdf2(a.x, x2, true); mdf2(x1, x2, false); } } else { int j = e.idx; auto &q = qr[j]; if (active_tp < types) ans[j] = INF32; else { auto res = sgt::gt(lower_bound(rx, rx + X, q.x) - rx); ans[j] = max(labs(q.x - res.fi), labs(q.x - res.se)); } } } for (int j = 0; j < Q; ++j) cout << (ans[j] >= INF32 ? -1 : ans[j]) << '\n'; return 0; }

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

new_home.cpp:1: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    1 | #pragma gcc optimize("O3")
      | 
new_home.cpp:2: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    2 | #pragma gcc optimize("Ofast")
      | 
new_home.cpp:3: warning: ignoring #pragma gcc target [-Wunknown-pragmas]
    3 | #pragma gcc target("avx2")
      |
#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...