| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 107434 |
2019-04-24T09:56:41 Z |
lyc |
New Home (APIO18_new_home) |
C++14 |
|
2581 ms |
108936 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)
const int MAXN = 3e5+10;
const int MAXK = 3e5+10;
const int MAXQ = 3e5+10;
const int MX_X = 1e8+10;
const int MX_Y = 1e8+10;
// Input Data
struct Store {
int i, x, t, a, b;
} stores[MAXN];
struct Query {
int i, l, y, ans;
} queries[MAXQ];
//
struct StoreEvent {
int x, y, type;
// type: 0 (open), 1 (close) };
};
vector<StoreEvent> events[MAXK];
struct OpenStore {
int cnt, negRay, posRay;
OpenStore(): cnt(1) {}
};
struct Ray {
int h, xh, xi, a, b;
Ray(int x1, int x2, int m, int y) {
a = y; b = -1;
h = (x2-x1)/2;
if (m > 0) xi = x1;
else xi = x2;
xh = xi + h*m;
}
void close(int y) { b = y-1; }
};
struct Seg {
int s, e, m, v[2];
Seg *l, *r;
Seg(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), l(nullptr), r(nullptr) {
v[0] = v[1] = -MX_X * 2;
if (s != e) {
l = new Seg(s, m);
r = new Seg(m+1, e);
}
}
void update(int x, int y, int val, int t) {
//cout << "UPDATE " << x << " " << y << " of " << s << " " << e << endl;
if (y < x) return;
if (s == x and e == y) v[t] = max(v[t], val);
else if (y <= m) l->update(x, y, val, t);
else if (x > m) r->update(x, y, val, t);
else l->update(x, m, val, t), r->update(m+1, y, val, t);
}
int query(int x, int t) {
if (s == e) return v[t];
else if (x <= m) return max(v[t], l->query(x, t));
else return max(v[t], r->query(x, t));
}
} *root;
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int n, k, q; cin >> n >> k >> q;
FOR(i,0,n-1){
stores[i].i = i;
cin >> stores[i].x >> stores[i].t >> stores[i].a >> stores[i].b;
}
vector<int> times;
FOR(i,0,q-1){
queries[i].i = i;
queries[i].ans = -1;
cin >> queries[i].l >> queries[i].y;
times.push_back(queries[i].y);
}
times.push_back(0);
times.push_back(MX_Y);
// Discretize time
sort(ALL(times));
times.resize(unique(ALL(times))-times.begin());
FOR(i,0,n-1){
if (stores[i].a >= stores[i].b) continue;
stores[i].a = lower_bound(ALL(times), stores[i].a) - times.begin(); // earliest ok
stores[i].b = upper_bound(ALL(times), stores[i].b) - times.begin() - 1; // last ok
}
FOR(i,0,q-1){
queries[i].y = lower_bound(ALL(times), queries[i].y) - times.begin(); // find its index
}
// Construct and sort all the store events by time for each type
FOR(i,0,n-1){
events[stores[i].t].push_back({stores[i].x, stores[i].a, 0});
events[stores[i].t].push_back({stores[i].x, stores[i].b+1, 1});
}
FOR(i,1,k){
sort(ALL(events[i]), [](const StoreEvent &a, const StoreEvent &b) {
if (a.y == b.y) return a.type > b.type; // closing first
return a.y < b.y;
});
}
//cout << "maybe" << endl;
//FOR(i,1,k){
// for (StoreEvent e : events[i]) {
// cout << e.x << " " << e.y << " :: " << e.type << endl;
// }
// cout << endl;
//}
// Build the max function for each type, preserving each ray's time interval
vector<Ray> negRays, posRays; // stores all the rays
FOR(i,1,k){
map<int, OpenStore> openStores;
openStores[-MX_X] = OpenStore();
openStores[2*MX_X]= OpenStore();
openStores[-MX_X].posRay = (int)posRays.size();
posRays.push_back( Ray(-MX_X, 2*MX_X, 1, 0) );
openStores[2*MX_X].negRay = (int)negRays.size();
negRays.push_back( Ray(-MX_X, 2*MX_X, -1, 0) );
//cout << "OK " << i << " :: " << negRays.size() << " " << posRays.size() << endl;
for (StoreEvent e : events[i]) {
auto it = openStores.lower_bound(e.x);
//cout << "PROCESS " << e.x << " " << e.y << " type " << e.type << endl;
//cout << "At time " << e.y << endl;
//cout << '\t';
//for (auto x : openStores) { cout << x.fi << " "; } cout << endl;
if (e.type == 0) { // opening event
if (it->fi == e.x) {
// store already exist. just increment counter
++it->sc.cnt;
} else {
assert(it != openStores.begin()); auto prv = prev(it);
assert(it != openStores.end()); auto nxt = it;
// no stores open here yet. create one
openStores[e.x] = OpenStore();
openStores[e.x].negRay = (int)negRays.size();
negRays.push_back( Ray(prv->fi, e.x, -1, e.y) );
openStores[e.x].posRay = (int)posRays.size();
posRays.push_back( Ray(e.x, nxt->fi, 1, e.y) );
negRays[nxt->sc.negRay].close(e.y);
//cout << "CLOSE " << e.y << " NEG " << nxt->sc.negRay << endl;
nxt->sc.negRay = (int)negRays.size();
negRays.push_back( Ray(e.x, nxt->fi, -1, e.y) );
posRays[prv->sc.posRay].close(e.y);
//cout << "CLOSE " << e.y << " POS " << prv->sc.posRay << endl;
prv->sc.posRay = (int)posRays.size();
posRays.push_back( Ray(prv->fi, e.x, 1, e.y) );
}
} else {
assert(it->fi == e.x); // a store should exist
if (it->sc.cnt > 1) {
// won't delete any rays
--it->sc.cnt;
} else {
assert(it != openStores.begin()); auto prv = prev(it);
assert(next(it) != openStores.end()); auto nxt = next(it);
// get rid of the store here
negRays[it->sc.negRay].close(e.y);
posRays[it->sc.posRay].close(e.y);
//cout << "CLOSE " << e.y << " HERE NEG " << it->sc.negRay << endl;
//cout << "CLOSE " << e.y << " HERE POS " << it->sc.posRay << endl;
openStores.erase(it);
negRays[nxt->sc.negRay].close(e.y);
//cout << "CLOSE " << e.y << " NEG " << nxt->sc.negRay << endl;
nxt->sc.negRay = (int)negRays.size();
negRays.push_back( Ray(prv->fi, nxt->fi, -1, e.y) );
posRays[prv->sc.posRay].close(e.y);
//cout << "CLOSE " << e.y << " POS " << prv->sc.posRay << endl;
prv->sc.posRay = (int)posRays.size();
posRays.push_back( Ray(prv->fi, nxt->fi, 1, e.y) );
}
}
}
//cout << "CLOSE " << times.size()-1 << " POS " << openStores[-MX_X].posRay << endl;
//cout << "CLOSE " << times.size()-1 << " NEG " << openStores[2*MX_X].negRay << endl;
posRays[openStores[-MX_X].posRay].close((int)times.size()-1);
negRays[openStores[2*MX_X].negRay].close((int)times.size()-1);
//cout << openStores.size() << endl;
//cout << "SHOULD CLOSE UP TO " << negRays.size() << " " << posRays.size() << endl;
}
// Now process the queries
root = new Seg(0, (int)times.size()-1);
sort(ALL(negRays), [](const Ray &a, const Ray &b) { return a.xh < b.xh; });
sort(queries, queries+q, [](const Query &a, const Query &b) { return a.l < b.l; });
//for (Ray r : negRays) {
// cout << "neg ray " << r.xh << " " << r.xi << " from time " << r.a << " to " << r.b << endl;
//}
//for (Ray r : posRays) {
// cout << "pos ray " << r.xh << " " << r.xi << " from time " << r.a << " to " << r.b << endl;
//}
auto it = negRays.begin();
FOR(i,0,q-1){
while (it != negRays.end() && it->xh <= queries[i].l) {
if (it->a <= it->b) {
//cout << "UPDATE TIME " << it->a << " - " << it->b << " by " << it->xi << endl;
root->update(it->a, it->b, it->xi, 0);
}
++it;
}
//cout << "QUERY " << queries[i].y << " RAY " << root->query(queries[i].y, 0) << endl;
queries[i].ans = root->query(queries[i].y, 0) - queries[i].l;
}
sort(ALL(posRays), [](const Ray &a, const Ray &b) { return a.xh > b.xh; });
sort(queries, queries+q, [](const Query &a, const Query &b) { return a.l > b.l; });
it = posRays.begin();
FOR(i,0,q-1){
while (it != posRays.end() && it->xh >= queries[i].l) {
root->update(it->a, it->b, -it->xi, 1);
++it;
}
queries[i].ans = max(queries[i].ans, queries[i].l + root->query(queries[i].y, 1));
}
sort(queries, queries+q, [](const Query &a, const Query &b) { return a.i < b.i; });
FOR(i,0,q-1){
cout << (queries[i].ans < MX_X ? queries[i].ans : -1) << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 2 |
Runtime error |
22 ms |
14720 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 2 |
Runtime error |
22 ms |
14720 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1880 ms |
98540 KB |
Output is correct |
| 2 |
Correct |
2105 ms |
91976 KB |
Output is correct |
| 3 |
Correct |
1992 ms |
107304 KB |
Output is correct |
| 4 |
Correct |
1954 ms |
100204 KB |
Output is correct |
| 5 |
Correct |
2581 ms |
91184 KB |
Output is correct |
| 6 |
Correct |
2321 ms |
92036 KB |
Output is correct |
| 7 |
Correct |
1827 ms |
106980 KB |
Output is correct |
| 8 |
Correct |
1880 ms |
99128 KB |
Output is correct |
| 9 |
Correct |
1870 ms |
96772 KB |
Output is correct |
| 10 |
Correct |
1914 ms |
93752 KB |
Output is correct |
| 11 |
Correct |
1455 ms |
91164 KB |
Output is correct |
| 12 |
Correct |
1532 ms |
93588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
606 ms |
108936 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 2 |
Runtime error |
22 ms |
14720 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 2 |
Runtime error |
22 ms |
14720 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
