제출 #414362

#제출 시각아이디문제언어결과실행 시간메모리
414362hhhhaura새 집 (APIO18_new_home)C++14
0 / 100
5098 ms437336 KiB
#define wiwihorz #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma loop-opt(on) #define rep(i, a, b) for(int i = a; i <= b; i++) #define rrep(i, a, b) for(int i = b; i >= a; i--) #define all(x) x.begin(), x.end() #define INF 1e9 using namespace std; #define pii pair<int, int> namespace seg { const int P = 3e7; int p = 0, root = 0; vector<int> lch, rch, seg; int get_new() {return ++p;} void init_() { lch.assign(P, 0); rch.assign(P, 0); seg.assign(P, INF); root = get_new(); } void pull(int nd) { seg[nd] = min(seg[lch[nd]], seg[rch[nd]]); } void modify(int nd, int L, int R, int x, int v) { if(L == R) seg[nd] = v; else { int mid = (L + R) / 2; if(!lch[nd]) lch[nd] = get_new(); if(!rch[nd]) rch[nd] = get_new(); if(x <= mid) modify(lch[nd], L, mid, x, v); else modify(rch[nd], mid + 1, R, x, v); pull(nd); } } int query(int nd, int L, int R, int l, int r) { if(!nd) return INF; else if(l <= L && r >= R) return seg[nd]; else { int mid = (L + R) / 2; return min(query(lch[nd], L, mid, l, r), query(rch[nd], mid + 1, R, l, r)); } } /* int get_lb(int nd, int L, int R, int x, int cur) { int mid = (L + R) / 2; if(!nd) return abs(x - max(L, x)); else if(L == R) { int l = 2 * x - L; if(L == INF) return -1; else return L - x; } else { int mid = (L + R) / 2, l = 2 * x - mid - 1; if(min(cur, seg[rch[nd]]) < l || mid <= x) return get_lb(rch[nd], mid + 1, R, x, cur); else return get_lb(lch[nd], L, mid, x, min(cur, seg[rch[nd]])); } } */ int ask(int x) { return query(root, 1, INF, x, INF); } /* int answer(int x) { return get_lb(root, 1, INF, x, INF); } */ void change(int x, int v) { modify(root, 1, INF, x, v); } }; namespace solver { int n, k, q; struct query { int x, tp, id; bool operator<(query b) { if(x != b.x) return x < b.x; else return tp < b.tp; } }; vector<map<int, int>> s; vector<multiset<pii>> cur; vector<pii> ans, stores; vector<query> qq; vector<int> v; void init_(int _n, int _k, int _q) { n = _n, k = _k, q = _q; s.assign(k + 1, map<int, int>()); cur.assign(n + q + 2, multiset<pii>()); ans.assign(q + 1, {0, 0}); stores.assign(n + k + 1, {0, 0}); qq.clear(), v.clear(); seg::init_(); } void add_store(int id, int l, int tp, int a, int b) { stores[id] = {l, tp}; v.push_back(l); qq.push_back({a, 1, id}); qq.push_back({b + 1, 2, id}); } void add_query(int id, int l, int y) { ans[id].first = l; v.push_back(l); qq.push_back({y, 3, id}); } void update(int x) { auto it = cur[x].begin(); if(it == cur[x].end()) seg::change(v[x], INF); else seg::change(v[x], v[it -> first]); } void add(int id) { int tp = stores[id].second, l = stores[id].first; s[tp][l] ++; if(s[tp][l] > 1) return; int pre, nxt = 0; auto it1 = s[tp].upper_bound(l); auto it2 = s[tp].lower_bound(l); if(it2 == s[tp].begin()) pre = 0; else pre = prev(it2) -> first; if(it1 != s[tp].end()) { nxt = it1 -> first; cur[nxt].erase(cur[nxt].find({pre, tp})); cur[nxt].insert({l, tp}); update(nxt); } cur[l].insert({pre, tp}); update(l); } /* int query(int x) { return seg::answer(x); } */ int query(int x) { int L = -1, R = 1e9; while(R - L > 1) { int mid = (L + R) / 2; int val = seg::ask(x + mid + 1); if(val < x - mid) L = mid; else R = mid; } if(R == 1e9) return -1; else return R; } void remove(int id) { int tp = stores[id].second, l = stores[id].first; s[tp][l] --; if(s[tp][l] > 0) return; int pre, nxt; s[tp].erase(s[tp].find(l)); auto it1 = s[tp].upper_bound(l); auto it2 = s[tp].lower_bound(l); if(it2 == s[tp].begin()) pre = 0; else pre = prev(it2) -> first; if(it1 != s[tp].end()) { nxt = it1 -> first; cur[nxt].erase(cur[nxt].find({l, tp})); cur[nxt].insert({pre, tp}); update(nxt); } cur[l].erase({pre, tp}); update(l); } void solve() { rep(i, 1, k) add_store(n + i, INF, i, -INF, INF); v.push_back(-INF); sort(all(v)), v.resize(unique(all(v)) - v.begin()); rep(i, 1, n + k) stores[i].first = lower_bound(all(v), stores[i].first) - v.begin(); rep(i, 1, q) ans[i].first = lower_bound(all(v), ans[i].first) - v.begin(); sort(all(qq)); for(auto i : qq) { if(i.tp == 1) add(i.id); else if(i.tp == 2) remove(i.id); else ans[i.id].second = query(v[ans[i.id].first]); } rep(i, 1, q) cout << ans[i].second << "\n"; } }; using namespace solver; signed main() { ios::sync_with_stdio(false), cin.tie(0); int n, k, q; cin >> n >> k >> q; init_(n, k, q); rep(i ,1, n) { int x, t, a, b; cin >> x >> t >> a >> b; add_store(i, x, t, a, b); } rep(i, 1, q) { int l, y; cin >> l >> y; add_query(i, l, y); } solve(); return 0; }

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

new_home.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      |
#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...