이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 2e9
using namespace std;
#define pii pair<int, int>
namespace seg {
int n;
vector<int> seg;
void init_(int _n) {
n = _n;
seg.assign(2 * n + 1, INF);
}
inline int get(int L, int R) {
return (L + R) | (L != R);
}
void pull(int L, int R) {
int nd = get(L, R), mid = (L + R) / 2;
seg[nd] = min(seg[get(L, mid)], seg[get(mid + 1, R)]);
}
void modify(int L, int R, int id, int v) {
int nd = get(L, R), mid = (L + R) / 2;
if(L == R) seg[nd] = v;
else {
if(id <= mid) modify(L, mid, id, v);
else modify(mid + 1, R, id, v);
pull(L, R);
}
}
int query(int L, int R, int l, int r) {
int nd = get(L, R), mid = (L + R) / 2;
if(l > R || r < L) return INF;
else if(l <= L && r >= R) return seg[nd];
else return min(query(L, mid, l, r), query(mid + 1, R, l, r));
}
void change(int x, int v) {modify(1, n, x, v);}
int ask(int x) { return query(1, n, x, n); }
};
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_(n + q + 1);
}
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(x, INF);
else seg::change(x, 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);
}
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);
}
int query(int x) {
int L = -1, R = 1e9;
while(R - L > 1) {
int mid = (L + R) / 2;
int l = lower_bound(all(v), v[x] - mid) - v.begin();
int r = upper_bound(all(v), v[x] + mid) - v.begin() - 1;
int val = seg::ask(r + 1);
if(val < l) L = mid;
else R = mid;
}
if(R == 1e9) return -1;
else return R;
}
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(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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |