oj.uz

Submission #161023

# Submission time Handle Problem Language Result Execution time Memory
161023 2019-10-31T08:47:08 Z Minnakhmetov New Home (APIO18_new_home) C++14
47 / 100
 5000 ms 478688 KB 
#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
 
using namespace std;
 
struct E {
    int p, t, x, y;
};
 
struct U {
    int l, r;
    pair<int, int> p;
};
 
const int N = 3e5 + 5, INF = 1e9, MAX = 1e8, H = 5e6;
int n, q, k, cq, cc;
int ans[N];
pair<int, int> lt[N], tmp[N];
map<pair<int, int>, int> mp;
 
vector<int> vx, v[2][H];
multiset<int> occ[N];
vector<pair<int, int>> t[2][N * 4];
vector<U> updates[2];

int getId(int x, int y) {
    auto p = make_pair(x, y);
    if (mp.count(p))
        return mp[p];
    int id = mp.size();
    mp[p] = id;
    return id;
}

void upd(int type, int l, int r, pair<int, int> p, int v, int L, int R) {
    if (l > r)
        return;
    if (L == l && R == r) {
        t[type][v].push_back(p);
    }
    else {
        int m = (L + R) >> 1;
        upd(type, l, min(m, r), p, v * 2, L, m);
        upd(type, max(m + 1, l), r, p, v * 2 + 1, m + 1, R);
    }
}
 
void startSeg(int type, int x, int y) {
    int id = getId(x, y);
    v[type][id].push_back(cq);
}
 
void endSeg(int type, int x, int y) {
    int id = getId(x, y);
    updates[type].push_back({v[type][id].back(), cq - 1, {x, y}});
    v[type][id].pop_back();
}
 
void updBeg(int x, bool add) {
    if (add)
        startSeg(0, 0, x);
    else
        endSeg(0, 0, x);
}
 
void updBetween(int x, int y, bool add) {
    if (x == y)
        return;
    int m = (x + y) / 2;
    if ((x + y) % 2)
        m++;
 
    // cout << "BET " << x << " " << y << " " << add << "\n";
 
    int m1 = lower_bound(all(vx), m) - vx.begin();
    if (add) {
        startSeg(0, m1, y);
        startSeg(1, cc - m1, INF - x);
    }
    else {
        endSeg(0, m1, y);
        endSeg(1, cc - m1, INF - x);
    }
}
 
void updEnd(int x, bool add) {
    if (add)
        startSeg(1, 0, INF - x);
    else
        endSeg(1, 0, INF - x);
}
 
void calcAns(int v, int L, int R) {
    if (L == R) {
        tmp[0] = lt[L];
    }
    else {
        int m = (L + R) >> 1;
        calcAns(v * 2, L, m);
        calcAns(v * 2 + 1, m + 1, R);
        
        int x = L, y = m + 1, z = 0;
        while (x <= m || y <= R) {
            if (x <= m && (y == R + 1 || lt[x].first < lt[y].first))
                tmp[z] = lt[x++];
            else 
                tmp[z] = lt[y++];
            z++;
        }
        for (int i = L; i <= R; i++)
            lt[i] = tmp[i - L];
    }
 
    int i = 0, mx = -INF;
    for (int j = 0; j <= R - L; j++) {
        while (i < t[0][v].size() && t[0][v][i].first <= tmp[j].first) {
            mx = max(mx, t[0][v][i].second);
            i++;
        }
        ans[tmp[j].second] = max(ans[tmp[j].second], mx - vx[tmp[j].first]);
    }    
 
    reverse(tmp, tmp + R - L + 1);
 
    for (int j = 0; j <= R - L; j++)
        tmp[j].first = cc - 1 - tmp[j].first;
 
    // for (int j = 0; j <= R - L; j++) {
    //     cout << tmp[j].first << " " << tmp[j].second << "\n";
    // }
 
    // for (auto p : t[1][v]) {
    //     cout << p.first << " " << p.second << "\n";
    // }
 
    // cout << ans[0] << "\n";
 
    i = 0, mx = -INF;
    for (int j = 0; j <= R - L; j++) {
        while (i < t[1][v].size() && t[1][v][i].first <= tmp[j].first) {
            mx = max(mx, t[1][v][i].second);
            i++;
        }
        ans[tmp[j].second] = max(ans[tmp[j].second], mx - INF + vx[cc - 1 - tmp[j].first]);
    }
}
 
void calcUpdates(vector<E> &evs) { 
    for (E &e : evs) {
        if (e.t == 2)
            vx.push_back(e.x);
    }
 
    sort(all(vx));
    vx.erase(unique(all(vx)), vx.end());
 
    cc = vx.size();
 
    cq = 0;
 
    for (E &e : evs) {
        // cout << e.p << " " << e.t << " " << e.x << " " << e.y << "\n";
        if (e.t == 0) {
            auto it = occ[e.y].upper_bound(e.x);
            if (!occ[e.y].empty()) {
                if (it != occ[e.y].begin() && it != occ[e.y].end()) {
                    updBetween(*prev(it), *it, false);
                }
                if (it == occ[e.y].begin()) {
                    updBeg(*it, false);
                }
                if (it == occ[e.y].end()) {
                    updEnd(*prev(it), false);
                }
            }
 
            it = occ[e.y].insert(e.x);
 
            if (it == occ[e.y].begin()) 
                updBeg(e.x, true);
            else
                updBetween(*prev(it), e.x, true);
 
            if (next(it) != occ[e.y].end())
                updBetween(e.x, *next(it), true);
            else
                updEnd(e.x, true);
 
        }
        else if (e.t == 1) {
            auto it = occ[e.y].find(e.x);
 
            if (it == occ[e.y].begin()) 
                updBeg(*it, false);
            else
                updBetween(*prev(it), *it, false);
 
            if (next(it) != occ[e.y].end())
                updBetween(*it, *next(it), false);
            else
                updEnd(e.x, false);
 
            if (it != occ[e.y].begin() && next(it) != occ[e.y].end())
                updBetween(*prev(it), *next(it), true);
            if (it == occ[e.y].begin() && occ[e.y].size() > 1)
                updBeg(*next(it), true);
 
            if (next(it) == occ[e.y].end() &&
                occ[e.y].size() > 1)
                updEnd(*prev(it), true);
 
            occ[e.y].erase(it);
        }
        else {
            lt[cq++] = {lower_bound(all(vx), e.x) - vx.begin(), e.y};
        }
    }
 
    for (int i = 0; i < 2; i++) {
        sort(all(updates[i]), [](const U &a, const U &b) {
            return a.p.first < b.p.first;
        });
    }
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    cin >> n >> k >> q;
 
    vector<E> evs;
 
    for (int i = 0; i < n; i++) {
        int x, t, a, b;
        cin >> x >> t >> a >> b;
        t--;
        evs.push_back({a, 0, x, t});
        evs.push_back({b + 1, 1, x, t});
    }
 
    for (int i = 0; i < k; i++) {
        evs.push_back({1, 0, INF, i});
        evs.push_back({MAX, 1, INF, i});
    }
 
    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        evs.push_back({y, 2, x, i});
    }
 
    sort(all(evs), [](const E &a, const E &b) {
        return a.p == b.p ? a.t < b.t : a.p < b.p;
    });
 
    calcUpdates(evs);
 
    for (int i = 0; i < 2; i++) {
        for (U &u : updates[i]) {
            upd(i, u.l, u.r, u.p, 1, 0, q - 1);
        }
    }
 
    calcAns(1, 0, q - 1);
 
    for (int i = 0; i < q; i++) {
        if (ans[i] < INF / 2) {
            cout << ans[i] << "\n";
        }
        else {
            cout << "-1\n";
        }
    }
 
    return 0;
}

Compilation message

new_home.cpp: In function 'void calcAns(int, int, int)':
new_home.cpp:118:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (i < t[0][v].size() && t[0][v][i].first <= tmp[j].first) {
                ~~^~~~~~~~~~~~~~~~
new_home.cpp:142:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (i < t[1][v].size() && t[1][v][i].first <= tmp[j].first) {
                ~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 305752 KB Output is correct
2 Correct 288 ms 305656 KB Output is correct
3 Correct 313 ms 305912 KB Output is correct
4 Correct 293 ms 305656 KB Output is correct
5 Correct 284 ms 305768 KB Output is correct
6 Correct 288 ms 306108 KB Output is correct
7 Correct 287 ms 305912 KB Output is correct
8 Correct 288 ms 306012 KB Output is correct
9 Correct 286 ms 306040 KB Output is correct
10 Correct 290 ms 306140 KB Output is correct
11 Correct 290 ms 306040 KB Output is correct
12 Correct 287 ms 306184 KB Output is correct
13 Correct 302 ms 305912 KB Output is correct
14 Correct 287 ms 305876 KB Output is correct
15 Correct 290 ms 306040 KB Output is correct
16 Correct 287 ms 306036 KB Output is correct
17 Correct 306 ms 305964 KB Output is correct
18 Correct 300 ms 306160 KB Output is correct
19 Correct 320 ms 306040 KB Output is correct
20 Correct 322 ms 306080 KB Output is correct
21 Correct 319 ms 305912 KB Output is correct
22 Correct 317 ms 306088 KB Output is correct
23 Correct 320 ms 306036 KB Output is correct
24 Correct 319 ms 306208 KB Output is correct
25 Correct 312 ms 306024 KB Output is correct
26 Correct 296 ms 305912 KB Output is correct
27 Correct 288 ms 306040 KB Output is correct
28 Correct 320 ms 305976 KB Output is correct
29 Correct 320 ms 305912 KB Output is correct
30 Correct 291 ms 305948 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 305752 KB Output is correct
2 Correct 288 ms 305656 KB Output is correct
3 Correct 313 ms 305912 KB Output is correct
4 Correct 293 ms 305656 KB Output is correct
5 Correct 284 ms 305768 KB Output is correct
6 Correct 288 ms 306108 KB Output is correct
7 Correct 287 ms 305912 KB Output is correct
8 Correct 288 ms 306012 KB Output is correct
9 Correct 286 ms 306040 KB Output is correct
10 Correct 290 ms 306140 KB Output is correct
11 Correct 290 ms 306040 KB Output is correct
12 Correct 287 ms 306184 KB Output is correct
13 Correct 302 ms 305912 KB Output is correct
14 Correct 287 ms 305876 KB Output is correct
15 Correct 290 ms 306040 KB Output is correct
16 Correct 287 ms 306036 KB Output is correct
17 Correct 306 ms 305964 KB Output is correct
18 Correct 300 ms 306160 KB Output is correct
19 Correct 320 ms 306040 KB Output is correct
20 Correct 322 ms 306080 KB Output is correct
21 Correct 319 ms 305912 KB Output is correct
22 Correct 317 ms 306088 KB Output is correct
23 Correct 320 ms 306036 KB Output is correct
24 Correct 319 ms 306208 KB Output is correct
25 Correct 312 ms 306024 KB Output is correct
26 Correct 296 ms 305912 KB Output is correct
27 Correct 288 ms 306040 KB Output is correct
28 Correct 320 ms 305976 KB Output is correct
29 Correct 320 ms 305912 KB Output is correct
30 Correct 291 ms 305948 KB Output is correct
31 Correct 2196 ms 396108 KB Output is correct
32 Correct 454 ms 318764 KB Output is correct
33 Correct 1932 ms 393220 KB Output is correct
34 Correct 2007 ms 393280 KB Output is correct
35 Correct 2049 ms 397008 KB Output is correct
36 Correct 1921 ms 395464 KB Output is correct
37 Correct 1447 ms 385440 KB Output is correct
38 Correct 1417 ms 382308 KB Output is correct
39 Correct 1098 ms 369808 KB Output is correct
40 Correct 1147 ms 372076 KB Output is correct
41 Correct 1336 ms 365636 KB Output is correct
42 Correct 1343 ms 366528 KB Output is correct
43 Correct 410 ms 318132 KB Output is correct
44 Correct 1351 ms 364756 KB Output is correct
45 Correct 1268 ms 360160 KB Output is correct
46 Correct 1136 ms 351516 KB Output is correct
47 Correct 789 ms 346892 KB Output is correct
48 Correct 748 ms 345620 KB Output is correct
49 Correct 876 ms 353116 KB Output is correct
50 Correct 1091 ms 361824 KB Output is correct
51 Correct 1012 ms 351004 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5094 ms 478688 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5092 ms 473320 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 305752 KB Output is correct
2 Correct 288 ms 305656 KB Output is correct
3 Correct 313 ms 305912 KB Output is correct
4 Correct 293 ms 305656 KB Output is correct
5 Correct 284 ms 305768 KB Output is correct
6 Correct 288 ms 306108 KB Output is correct
7 Correct 287 ms 305912 KB Output is correct
8 Correct 288 ms 306012 KB Output is correct
9 Correct 286 ms 306040 KB Output is correct
10 Correct 290 ms 306140 KB Output is correct
11 Correct 290 ms 306040 KB Output is correct
12 Correct 287 ms 306184 KB Output is correct
13 Correct 302 ms 305912 KB Output is correct
14 Correct 287 ms 305876 KB Output is correct
15 Correct 290 ms 306040 KB Output is correct
16 Correct 287 ms 306036 KB Output is correct
17 Correct 306 ms 305964 KB Output is correct
18 Correct 300 ms 306160 KB Output is correct
19 Correct 320 ms 306040 KB Output is correct
20 Correct 322 ms 306080 KB Output is correct
21 Correct 319 ms 305912 KB Output is correct
22 Correct 317 ms 306088 KB Output is correct
23 Correct 320 ms 306036 KB Output is correct
24 Correct 319 ms 306208 KB Output is correct
25 Correct 312 ms 306024 KB Output is correct
26 Correct 296 ms 305912 KB Output is correct
27 Correct 288 ms 306040 KB Output is correct
28 Correct 320 ms 305976 KB Output is correct
29 Correct 320 ms 305912 KB Output is correct
30 Correct 291 ms 305948 KB Output is correct
31 Correct 2196 ms 396108 KB Output is correct
32 Correct 454 ms 318764 KB Output is correct
33 Correct 1932 ms 393220 KB Output is correct
34 Correct 2007 ms 393280 KB Output is correct
35 Correct 2049 ms 397008 KB Output is correct
36 Correct 1921 ms 395464 KB Output is correct
37 Correct 1447 ms 385440 KB Output is correct
38 Correct 1417 ms 382308 KB Output is correct
39 Correct 1098 ms 369808 KB Output is correct
40 Correct 1147 ms 372076 KB Output is correct
41 Correct 1336 ms 365636 KB Output is correct
42 Correct 1343 ms 366528 KB Output is correct
43 Correct 410 ms 318132 KB Output is correct
44 Correct 1351 ms 364756 KB Output is correct
45 Correct 1268 ms 360160 KB Output is correct
46 Correct 1136 ms 351516 KB Output is correct
47 Correct 789 ms 346892 KB Output is correct
48 Correct 748 ms 345620 KB Output is correct
49 Correct 876 ms 353116 KB Output is correct
50 Correct 1091 ms 361824 KB Output is correct
51 Correct 1012 ms 351004 KB Output is correct
52 Correct 1054 ms 370020 KB Output is correct
53 Correct 1006 ms 357968 KB Output is correct
54 Correct 1445 ms 378112 KB Output is correct
55 Correct 1174 ms 370768 KB Output is correct
56 Correct 1123 ms 370912 KB Output is correct
57 Correct 1303 ms 367208 KB Output is correct
58 Correct 1334 ms 369164 KB Output is correct
59 Correct 1203 ms 369816 KB Output is correct
60 Correct 1305 ms 367536 KB Output is correct
61 Correct 457 ms 330456 KB Output is correct
62 Correct 1010 ms 373076 KB Output is correct
63 Correct 1256 ms 373884 KB Output is correct
64 Correct 1346 ms 375660 KB Output is correct
65 Correct 1459 ms 377084 KB Output is correct
66 Correct 1385 ms 369504 KB Output is correct
67 Correct 614 ms 332944 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 305752 KB Output is correct
2 Correct 288 ms 305656 KB Output is correct
3 Correct 313 ms 305912 KB Output is correct
4 Correct 293 ms 305656 KB Output is correct
5 Correct 284 ms 305768 KB Output is correct
6 Correct 288 ms 306108 KB Output is correct
7 Correct 287 ms 305912 KB Output is correct
8 Correct 288 ms 306012 KB Output is correct
9 Correct 286 ms 306040 KB Output is correct
10 Correct 290 ms 306140 KB Output is correct
11 Correct 290 ms 306040 KB Output is correct
12 Correct 287 ms 306184 KB Output is correct
13 Correct 302 ms 305912 KB Output is correct
14 Correct 287 ms 305876 KB Output is correct
15 Correct 290 ms 306040 KB Output is correct
16 Correct 287 ms 306036 KB Output is correct
17 Correct 306 ms 305964 KB Output is correct
18 Correct 300 ms 306160 KB Output is correct
19 Correct 320 ms 306040 KB Output is correct
20 Correct 322 ms 306080 KB Output is correct
21 Correct 319 ms 305912 KB Output is correct
22 Correct 317 ms 306088 KB Output is correct
23 Correct 320 ms 306036 KB Output is correct
24 Correct 319 ms 306208 KB Output is correct
25 Correct 312 ms 306024 KB Output is correct
26 Correct 296 ms 305912 KB Output is correct
27 Correct 288 ms 306040 KB Output is correct
28 Correct 320 ms 305976 KB Output is correct
29 Correct 320 ms 305912 KB Output is correct
30 Correct 291 ms 305948 KB Output is correct
31 Correct 2196 ms 396108 KB Output is correct
32 Correct 454 ms 318764 KB Output is correct
33 Correct 1932 ms 393220 KB Output is correct
34 Correct 2007 ms 393280 KB Output is correct
35 Correct 2049 ms 397008 KB Output is correct
36 Correct 1921 ms 395464 KB Output is correct
37 Correct 1447 ms 385440 KB Output is correct
38 Correct 1417 ms 382308 KB Output is correct
39 Correct 1098 ms 369808 KB Output is correct
40 Correct 1147 ms 372076 KB Output is correct
41 Correct 1336 ms 365636 KB Output is correct
42 Correct 1343 ms 366528 KB Output is correct
43 Correct 410 ms 318132 KB Output is correct
44 Correct 1351 ms 364756 KB Output is correct
45 Correct 1268 ms 360160 KB Output is correct
46 Correct 1136 ms 351516 KB Output is correct
47 Correct 789 ms 346892 KB Output is correct
48 Correct 748 ms 345620 KB Output is correct
49 Correct 876 ms 353116 KB Output is correct
50 Correct 1091 ms 361824 KB Output is correct
51 Correct 1012 ms 351004 KB Output is correct
52 Execution timed out 5094 ms 478688 KB Time limit exceeded
53 Halted 0 ms 0 KB -