| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 490194 |
2021-11-26T07:44:25 Z |
8e7 |
New Home (APIO18_new_home) |
C++17 |
|
420 ms |
38892 KB |
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <assert.h>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
void debug(){cout << endl;};
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b ...);};
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
};
#define ll long long
#define maxn 300005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<29;
struct segtree{ //PURQ segtree
int seg[4*maxn];
void init(int cur, int l, int r) {
if (r <= l) return;
if (r - l == 1) {
seg[cur] = inf;
return;
}
int m = (l + r) / 2;
init(cur*2, l, m), init(cur*2+1, m, r);
seg[cur] = inf;
}
void modify(int cur, int l, int r, int ind, int val) {
if (r <= l) return;
if (r - l == 1) {
seg[cur] = val;
return;
}
int m = (l + r) / 2;
if (ind < m)modify(cur*2, l, m, ind, val);
else modify(cur*2+1, m, r, ind, val);
seg[cur] = min(seg[cur*2], seg[cur*2+1]);
}
int query(int cur, int l, int r, int ql, int qr) {
if (r <= l || ql >= r || qr <= l) return inf;
if (ql <= l && qr >= r) return seg[cur];
int m = (l + r) / 2;
return min(query(cur*2, l, m, ql, qr), query(cur*2+1, m, r, ql, qr));
}
} sl, sr;
struct obj{
int x, t, a, b;
obj(){x = t = a = b = 0;}
obj(int xx, int tt, int aa, int bb){x = xx, t = tt, a = aa, b = bb;}
} st[maxn];
struct query{
int pos, ti, id;
query(){pos = ti = id = 0;}
query(int x, int y, int z){pos = x, ti = y, id = z;}
};
int nxt[maxn], rcol[maxn];
int ans[maxn];
vector<pii> range;
vector<int> pose; //positions set
vector<query> que;
void compress(vector<int> &v) {
sort(v.begin(), v.end());
v.resize(int(unique(v.begin(), v.end()) - v.begin()));
}
int main() {
io
int n, k, q;
cin >> n >> k >> q;
for (int i = 0;i < n;i++) {
cin >> st[i].x >> st[i].t >> st[i].a >> st[i].b;
}
que.resize(q);
for (int i = 0;i < q;i++) {
cin >> que[i].pos >> que[i].ti;
que[i].id = i;
}
sort(st, st + n, [&](obj x, obj y){return x.x < y.x;});
for (int i = 1;i <= k;i++) rcol[i] = inf;
for (int i = n - 1;i >= 0;i--) {
nxt[i] = rcol[st[i].t];
rcol[st[i].t] = st[i].x;
}
int rig = 0;
for (int i = 1;i <= k;i++) rig = max(rig, rcol[i]);
for (int i = 0;i < n;i++) {
if (rig == inf) continue;
range.push_back({(st[i].x + rig), rig - st[i].x});
//debug(st[i].x, rig);
pose.push_back(st[i].x + rig);
rig = max(rig, nxt[i]);
}
compress(pose);
int siz = pose.size();
sl.init(1, 0, siz), sr.init(1, 0, siz);
auto lb = [&] (int x) {
return lower_bound(pose.begin(), pose.end(), x) - pose.begin();
};
for (int i = 0;i < siz;i++) {
int ind = lb(range[i].ff);
//debug(range[i].ff, range[i].ss, ind, siz);
sl.modify(1, 0, siz, ind, range[i].ss - range[i].ff);
sr.modify(1, 0, siz, ind, range[i].ss + range[i].ff);
}
for (auto qq:que) {
int ind = lb(2*qq.pos);
//debug(qq.id, ind, qq.pos);
//debug(sl.query(1, 0, siz, 0, ind), sr.query(1, 0, siz, ind, siz));
ans[qq.id] = min(sl.query(1, 0, siz, 0, ind) + 2*qq.pos, sr.query(1, 0, siz, ind, siz) - 2*qq.pos);
}
for (int i = 0;i < q;i++) {
ans[i] /= 2;
cout << (ans[i] > 100000000 ? -1 : ans[i]) << "\n";
}
}
/*
4 2 4
3 1 1 10
9 2 1 4
7 2 1 7
4 1 8 10
1 1
5 1
2 1
3 1
1 1 1
100000000 1 1 1
1 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5016 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5016 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
201 ms |
27384 KB |
Output is correct |
| 2 |
Incorrect |
420 ms |
38892 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
347 ms |
34360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5016 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5016 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
