| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 513542 |
2022-01-17T08:09:14 Z |
blue |
New Home (APIO18_new_home) |
C++17 |
|
5000 ms |
390976 KB |
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
using vi = vector<int>;
#define sz(x) int(x.size())
const int mx = 300'000;
int n, k, q;
vi x(1+mx), t(1+mx), a(1+mx), b(1+mx);
vi l(1+mx), y(1+mx);
int get_time(int i)
{
if(i <= n) return a[i];
else if(i <= n+q) return y[i-n];
else return b[i-n-q];
}
bool cmp(int i, int j)
{
int ti = get_time(i), tj = get_time(j);
if(ti != tj) return ti < tj;
else return i < j;
}
const int ss = (1<<20);
const int INF = 2'0000'0000;
vi qlocs;
struct segtree
{
vi l = vi(ss, 0);
vi r = vi(ss, 0);
// vi xpy = vi(ss, -INF);
// vi xmy = vi(ss, -INF);
multiset<int>* xpy = new multiset<int>[ss];
multiset<int>* xmy = new multiset<int>[ss];
void build(int i, int L, int R)
{
l[i] = L;
r[i] = R;
if(L == R) return;
build(2*i, L, (L+R)/2);
build(2*i+1, (L+R)/2+1, R);
}
void deploy_xpy(int i, int L, int R, int V)
{
if(R < qlocs[l[i]] || qlocs[r[i]] < L) return;
else if(L <= qlocs[l[i]] && qlocs[r[i]] <= R)
xpy[i].insert(V);
else
{
deploy_xpy(2*i, L, R, V);
deploy_xpy(2*i+1, L, R, V);
}
}
void withdraw_xpy(int i, int L, int R, int V)
{
if(R < qlocs[l[i]] || qlocs[r[i]] < L) return;
else if(L <= qlocs[l[i]] && qlocs[r[i]] <= R)
xpy[i].erase(xpy[i].find(V));
else
{
withdraw_xpy(2*i, L, R, V);
withdraw_xpy(2*i+1, L, R, V);
}
}
void deploy_xmy(int i, int L, int R, int V)
{
if(R < qlocs[l[i]] || qlocs[r[i]] < L) return;
else if(L <= qlocs[l[i]] && qlocs[r[i]] <= R)
xmy[i].insert(V);
else
{
deploy_xmy(2*i, L, R, V);
deploy_xmy(2*i+1, L, R, V);
}
}
void withdraw_xmy(int i, int L, int R, int V)
{
if(R < qlocs[l[i]] || qlocs[r[i]] < L) return;
else if(L <= qlocs[l[i]] && qlocs[r[i]] <= R)
xmy[i].erase(xmy[i].find(V));
else
{
withdraw_xmy(2*i, L, R, V);
withdraw_xmy(2*i+1, L, R, V);
}
}
int solve(int i, int X)
{
int ans = -1;
if(X < qlocs[l[i]] || qlocs[r[i]] < X) return ans;
if(qlocs[l[i]] <= X && X <= qlocs[r[i]])
{
if(!xpy[i].empty())
ans = max(ans, *xpy[i].rbegin() - X);
if(!xmy[i].empty())
ans = max(ans, X - *xmy[i].begin());
}
if(l[i] != r[i]) ans = max(ans, max(solve(2*i, X), solve(2*i+1, X)));
return ans;
}
};
segtree S;
void insert_pair(int u, int v)
{
int m = (u+v + 1'000'000'000'000LL)/2LL - 500'000'000'000LL;
S.deploy_xmy(1, u, m-1, u);
S.deploy_xpy(1, m, v-1, v);
}
void erase_pair(int u, int v)
{
int m = (u+v + 1'000'000'000'000LL)/2LL - 500'000'000'000LL;
S.withdraw_xmy(1, u, m-1, u);
S.withdraw_xpy(1, m, v-1, v);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k >> q;
for(int i = 1; i <= n; i++) cin >> x[i] >> t[i] >> a[i] >> b[i];
for(int j = 1; j <= q; j++) cin >> l[j] >> y[j];
vi obj;
for(int i = 1; i <= n; i++)
{
obj.push_back(i);
obj.push_back(n+q+i);
}
for(int j = 1; j <= q; j++)
obj.push_back(n+j);
sort(obj.begin(), obj.end(), cmp);
vi ans(1+q, -1);
set<int> qlocs_set;
for(int j = 1; j <= q; j++) qlocs_set.insert(l[j]);
qlocs = vi(1, 0);
for(int g: qlocs_set) qlocs.push_back(g);
int Z = sz(qlocs_set);
// segtree S;
S.build(1, 1, Z);
multiset<int> locs[1+k];
for(int typ = 1; typ <= k; typ++)
{
locs[typ].insert(0 - 2*INF);
locs[typ].insert(INF + 2*INF);
insert_pair(-2*INF, 3*INF);
}
vi occ(1+k, 0);
int occ_ct = 0;
for(int o: obj)
{
// cerr << "o = " << o << " : " << "time = " << get_time(o) << '\n';
if(o <= n)
{
int shop = o;
if(occ[t[shop]] == 0) occ_ct++;
occ[t[shop]]++;
auto it = locs[t[shop]].lower_bound(x[shop]);
int next_loc = *it;
it--;
int prev_loc = *it;
erase_pair(prev_loc, next_loc);
locs[t[shop]].insert(x[shop]);
insert_pair(prev_loc, x[shop]);
insert_pair(x[shop], next_loc);
}
else if(o <= n+q)
{
int qr = o-n;
// cerr << "performing query " << qr << '\n';
if(occ_ct == k) ans[qr] = S.solve(1, l[qr]);
else ans[qr] = -1;
// ans[qr] = S.get(l[qr]);
}
else
{
int shop = o-n-q;
occ[t[shop]]--;
if(occ[t[shop]] == 0) occ_ct--;
locs[t[shop]].erase(locs[t[shop]].find(x[shop]));
auto it = locs[t[shop]].lower_bound(x[shop]);
int next_loc = *it;
it--;
int prev_loc = *it;
erase_pair(prev_loc, x[shop]);
erase_pair(x[shop], next_loc);
insert_pair(prev_loc, next_loc);
}
}
for(int j = 1; j <= q; j++) cout << ans[j] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
113996 KB |
Output is correct |
| 2 |
Correct |
51 ms |
114068 KB |
Output is correct |
| 3 |
Correct |
48 ms |
114068 KB |
Output is correct |
| 4 |
Correct |
48 ms |
113996 KB |
Output is correct |
| 5 |
Incorrect |
48 ms |
114080 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
113996 KB |
Output is correct |
| 2 |
Correct |
51 ms |
114068 KB |
Output is correct |
| 3 |
Correct |
48 ms |
114068 KB |
Output is correct |
| 4 |
Correct |
48 ms |
113996 KB |
Output is correct |
| 5 |
Incorrect |
48 ms |
114080 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5047 ms |
390976 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5020 ms |
303552 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
113996 KB |
Output is correct |
| 2 |
Correct |
51 ms |
114068 KB |
Output is correct |
| 3 |
Correct |
48 ms |
114068 KB |
Output is correct |
| 4 |
Correct |
48 ms |
113996 KB |
Output is correct |
| 5 |
Incorrect |
48 ms |
114080 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
113996 KB |
Output is correct |
| 2 |
Correct |
51 ms |
114068 KB |
Output is correct |
| 3 |
Correct |
48 ms |
114068 KB |
Output is correct |
| 4 |
Correct |
48 ms |
113996 KB |
Output is correct |
| 5 |
Incorrect |
48 ms |
114080 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
