oj.uz

Submission #161024

# Submission time Handle Problem Language Result Execution time Memory
161024 2019-10-31T08:48:29 Z Minnakhmetov New Home (APIO18_new_home) C++14
57 / 100
 5000 ms 539056 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];
unordered_map<ll, 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(ll x, ll y) {
    x = (x << 31) | y;
    if (mp.count(x))
        return mp[x];
    int id = mp.size();
    mp[x] = 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 305 ms 305660 KB Output is correct
2 Correct 298 ms 305784 KB Output is correct
3 Correct 304 ms 305768 KB Output is correct
4 Correct 301 ms 305656 KB Output is correct
5 Correct 314 ms 305928 KB Output is correct
6 Correct 287 ms 306020 KB Output is correct
7 Correct 308 ms 305912 KB Output is correct
8 Correct 289 ms 306132 KB Output is correct
9 Correct 288 ms 306084 KB Output is correct
10 Correct 293 ms 306172 KB Output is correct
11 Correct 287 ms 306040 KB Output is correct
12 Correct 294 ms 306012 KB Output is correct
13 Correct 296 ms 305912 KB Output is correct
14 Correct 288 ms 305896 KB Output is correct
15 Correct 286 ms 305912 KB Output is correct
16 Correct 292 ms 306092 KB Output is correct
17 Correct 287 ms 305968 KB Output is correct
18 Correct 284 ms 305912 KB Output is correct
19 Correct 289 ms 306040 KB Output is correct
20 Correct 288 ms 305912 KB Output is correct
21 Correct 298 ms 305804 KB Output is correct
22 Correct 286 ms 306044 KB Output is correct
23 Correct 291 ms 306168 KB Output is correct
24 Correct 293 ms 306008 KB Output is correct
25 Correct 309 ms 306168 KB Output is correct
26 Correct 313 ms 306040 KB Output is correct
27 Correct 321 ms 305968 KB Output is correct
28 Correct 314 ms 305936 KB Output is correct
29 Correct 313 ms 305976 KB Output is correct
30 Correct 284 ms 305772 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 305660 KB Output is correct
2 Correct 298 ms 305784 KB Output is correct
3 Correct 304 ms 305768 KB Output is correct
4 Correct 301 ms 305656 KB Output is correct
5 Correct 314 ms 305928 KB Output is correct
6 Correct 287 ms 306020 KB Output is correct
7 Correct 308 ms 305912 KB Output is correct
8 Correct 289 ms 306132 KB Output is correct
9 Correct 288 ms 306084 KB Output is correct
10 Correct 293 ms 306172 KB Output is correct
11 Correct 287 ms 306040 KB Output is correct
12 Correct 294 ms 306012 KB Output is correct
13 Correct 296 ms 305912 KB Output is correct
14 Correct 288 ms 305896 KB Output is correct
15 Correct 286 ms 305912 KB Output is correct
16 Correct 292 ms 306092 KB Output is correct
17 Correct 287 ms 305968 KB Output is correct
18 Correct 284 ms 305912 KB Output is correct
19 Correct 289 ms 306040 KB Output is correct
20 Correct 288 ms 305912 KB Output is correct
21 Correct 298 ms 305804 KB Output is correct
22 Correct 286 ms 306044 KB Output is correct
23 Correct 291 ms 306168 KB Output is correct
24 Correct 293 ms 306008 KB Output is correct
25 Correct 309 ms 306168 KB Output is correct
26 Correct 313 ms 306040 KB Output is correct
27 Correct 321 ms 305968 KB Output is correct
28 Correct 314 ms 305936 KB Output is correct
29 Correct 313 ms 305976 KB Output is correct
30 Correct 284 ms 305772 KB Output is correct
31 Correct 1569 ms 389412 KB Output is correct
32 Correct 462 ms 319068 KB Output is correct
33 Correct 1483 ms 386372 KB Output is correct
34 Correct 1422 ms 386108 KB Output is correct
35 Correct 1529 ms 389732 KB Output is correct
36 Correct 1548 ms 389464 KB Output is correct
37 Correct 1175 ms 378736 KB Output is correct
38 Correct 1138 ms 376460 KB Output is correct
39 Correct 965 ms 363744 KB Output is correct
40 Correct 1022 ms 366304 KB Output is correct
41 Correct 1104 ms 360836 KB Output is correct
42 Correct 1099 ms 361904 KB Output is correct
43 Correct 434 ms 318556 KB Output is correct
44 Correct 1153 ms 359932 KB Output is correct
45 Correct 1038 ms 355252 KB Output is correct
46 Correct 911 ms 346620 KB Output is correct
47 Correct 722 ms 341588 KB Output is correct
48 Correct 726 ms 342112 KB Output is correct
49 Correct 796 ms 348964 KB Output is correct
50 Correct 859 ms 357528 KB Output is correct
51 Correct 798 ms 346532 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3640 ms 467800 KB Output is correct
2 Correct 4661 ms 490792 KB Output is correct
3 Correct 2574 ms 487820 KB Output is correct
4 Correct 3668 ms 469688 KB Output is correct
5 Correct 4606 ms 463992 KB Output is correct
6 Correct 4765 ms 487980 KB Output is correct
7 Correct 2409 ms 485476 KB Output is correct
8 Correct 3127 ms 481544 KB Output is correct
9 Correct 3472 ms 472288 KB Output is correct
10 Correct 3897 ms 497984 KB Output is correct
11 Correct 3264 ms 492724 KB Output is correct
12 Correct 3325 ms 496192 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 305660 KB Output is correct
2 Correct 298 ms 305784 KB Output is correct
3 Correct 304 ms 305768 KB Output is correct
4 Correct 301 ms 305656 KB Output is correct
5 Correct 314 ms 305928 KB Output is correct
6 Correct 287 ms 306020 KB Output is correct
7 Correct 308 ms 305912 KB Output is correct
8 Correct 289 ms 306132 KB Output is correct
9 Correct 288 ms 306084 KB Output is correct
10 Correct 293 ms 306172 KB Output is correct
11 Correct 287 ms 306040 KB Output is correct
12 Correct 294 ms 306012 KB Output is correct
13 Correct 296 ms 305912 KB Output is correct
14 Correct 288 ms 305896 KB Output is correct
15 Correct 286 ms 305912 KB Output is correct
16 Correct 292 ms 306092 KB Output is correct
17 Correct 287 ms 305968 KB Output is correct
18 Correct 284 ms 305912 KB Output is correct
19 Correct 289 ms 306040 KB Output is correct
20 Correct 288 ms 305912 KB Output is correct
21 Correct 298 ms 305804 KB Output is correct
22 Correct 286 ms 306044 KB Output is correct
23 Correct 291 ms 306168 KB Output is correct
24 Correct 293 ms 306008 KB Output is correct
25 Correct 309 ms 306168 KB Output is correct
26 Correct 313 ms 306040 KB Output is correct
27 Correct 321 ms 305968 KB Output is correct
28 Correct 314 ms 305936 KB Output is correct
29 Correct 313 ms 305976 KB Output is correct
30 Correct 284 ms 305772 KB Output is correct
31 Correct 1569 ms 389412 KB Output is correct
32 Correct 462 ms 319068 KB Output is correct
33 Correct 1483 ms 386372 KB Output is correct
34 Correct 1422 ms 386108 KB Output is correct
35 Correct 1529 ms 389732 KB Output is correct
36 Correct 1548 ms 389464 KB Output is correct
37 Correct 1175 ms 378736 KB Output is correct
38 Correct 1138 ms 376460 KB Output is correct
39 Correct 965 ms 363744 KB Output is correct
40 Correct 1022 ms 366304 KB Output is correct
41 Correct 1104 ms 360836 KB Output is correct
42 Correct 1099 ms 361904 KB Output is correct
43 Correct 434 ms 318556 KB Output is correct
44 Correct 1153 ms 359932 KB Output is correct
45 Correct 1038 ms 355252 KB Output is correct
46 Correct 911 ms 346620 KB Output is correct
47 Correct 722 ms 341588 KB Output is correct
48 Correct 726 ms 342112 KB Output is correct
49 Correct 796 ms 348964 KB Output is correct
50 Correct 859 ms 357528 KB Output is correct
51 Correct 798 ms 346532 KB Output is correct
52 Correct 992 ms 369380 KB Output is correct
53 Correct 999 ms 357512 KB Output is correct
54 Correct 1274 ms 374376 KB Output is correct
55 Correct 1000 ms 367100 KB Output is correct
56 Correct 983 ms 368148 KB Output is correct
57 Correct 1012 ms 364372 KB Output is correct
58 Correct 1068 ms 365636 KB Output is correct
59 Correct 1008 ms 367156 KB Output is correct
60 Correct 1106 ms 364512 KB Output is correct
61 Correct 454 ms 331420 KB Output is correct
62 Correct 1140 ms 372436 KB Output is correct
63 Correct 1087 ms 371344 KB Output is correct
64 Correct 1151 ms 372324 KB Output is correct
65 Correct 1171 ms 374544 KB Output is correct
66 Correct 1122 ms 366092 KB Output is correct
67 Correct 551 ms 332908 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 305660 KB Output is correct
2 Correct 298 ms 305784 KB Output is correct
3 Correct 304 ms 305768 KB Output is correct
4 Correct 301 ms 305656 KB Output is correct
5 Correct 314 ms 305928 KB Output is correct
6 Correct 287 ms 306020 KB Output is correct
7 Correct 308 ms 305912 KB Output is correct
8 Correct 289 ms 306132 KB Output is correct
9 Correct 288 ms 306084 KB Output is correct
10 Correct 293 ms 306172 KB Output is correct
11 Correct 287 ms 306040 KB Output is correct
12 Correct 294 ms 306012 KB Output is correct
13 Correct 296 ms 305912 KB Output is correct
14 Correct 288 ms 305896 KB Output is correct
15 Correct 286 ms 305912 KB Output is correct
16 Correct 292 ms 306092 KB Output is correct
17 Correct 287 ms 305968 KB Output is correct
18 Correct 284 ms 305912 KB Output is correct
19 Correct 289 ms 306040 KB Output is correct
20 Correct 288 ms 305912 KB Output is correct
21 Correct 298 ms 305804 KB Output is correct
22 Correct 286 ms 306044 KB Output is correct
23 Correct 291 ms 306168 KB Output is correct
24 Correct 293 ms 306008 KB Output is correct
25 Correct 309 ms 306168 KB Output is correct
26 Correct 313 ms 306040 KB Output is correct
27 Correct 321 ms 305968 KB Output is correct
28 Correct 314 ms 305936 KB Output is correct
29 Correct 313 ms 305976 KB Output is correct
30 Correct 284 ms 305772 KB Output is correct
31 Correct 1569 ms 389412 KB Output is correct
32 Correct 462 ms 319068 KB Output is correct
33 Correct 1483 ms 386372 KB Output is correct
34 Correct 1422 ms 386108 KB Output is correct
35 Correct 1529 ms 389732 KB Output is correct
36 Correct 1548 ms 389464 KB Output is correct
37 Correct 1175 ms 378736 KB Output is correct
38 Correct 1138 ms 376460 KB Output is correct
39 Correct 965 ms 363744 KB Output is correct
40 Correct 1022 ms 366304 KB Output is correct
41 Correct 1104 ms 360836 KB Output is correct
42 Correct 1099 ms 361904 KB Output is correct
43 Correct 434 ms 318556 KB Output is correct
44 Correct 1153 ms 359932 KB Output is correct
45 Correct 1038 ms 355252 KB Output is correct
46 Correct 911 ms 346620 KB Output is correct
47 Correct 722 ms 341588 KB Output is correct
48 Correct 726 ms 342112 KB Output is correct
49 Correct 796 ms 348964 KB Output is correct
50 Correct 859 ms 357528 KB Output is correct
51 Correct 798 ms 346532 KB Output is correct
52 Correct 3640 ms 467800 KB Output is correct
53 Correct 4661 ms 490792 KB Output is correct
54 Correct 2574 ms 487820 KB Output is correct
55 Correct 3668 ms 469688 KB Output is correct
56 Correct 4606 ms 463992 KB Output is correct
57 Correct 4765 ms 487980 KB Output is correct
58 Correct 2409 ms 485476 KB Output is correct
59 Correct 3127 ms 481544 KB Output is correct
60 Correct 3472 ms 472288 KB Output is correct
61 Correct 3897 ms 497984 KB Output is correct
62 Correct 3264 ms 492724 KB Output is correct
63 Correct 3325 ms 496192 KB Output is correct
64 Execution timed out 5119 ms 539056 KB Time limit exceeded
65 Halted 0 ms 0 KB -