oj.uz

답안 #161032

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
161032 2019-10-31T09:31:37 Z Minnakhmetov 새 집 (APIO18_new_home) C++14
57 / 100
 5000 ms 435976 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;
int n, q, k, cq, cc;
int ans[N];
pair<int, int> lt[N], tmp[N];
unordered_map<int, vector<int>> mp[2][N];
bool ok[N];
 
vector<int> vx;
multiset<int> occ[N];
vector<pair<int, int>> t[2][N * 4];
vector<U> updates[2];
 
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);
    }
}

bool dummy(int y) {
    return abs(y) == INF || abs(INF - y) == INF;
}
 
void startSeg(int type, int x, int y) {
    if (dummy(y))
        return;
    mp[type][x][y].push_back(cq);
}
 
void endSeg(int type, int x, int y) {
    if (dummy(y))
        return;
    auto &v = mp[type][x][y];
    if (v.size() == 1)
        updates[type].push_back({v.back(), cq - 1, {x, y}});
    v.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;

    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;

    int types_on = 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);

            updBetween(*prev(it), *it, false);
            
            if (occ[e.y].size() == 2)
                types_on++;
 
            it = occ[e.y].insert(e.x);

            updBetween(*prev(it), e.x, true);
            updBetween(e.x, *next(it), true);
 
        }
        else if (e.t == 1) {
            auto it = occ[e.y].find(e.x);

            updBetween(*prev(it), *it, false);
            updBetween(*it, *next(it), false);
            updBetween(*prev(it), *next(it), true);

            occ[e.y].erase(it);

            if (occ[e.y].size() == 2)
                types_on--;
        }
        else {
            ok[e.y] = (types_on == k);
            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 < q; i++) {
        int x, y;
        cin >> x >> y;
        evs.push_back({y, 2, x, i});
    }

    for (int i = 0; i < k; i++) {
        occ[i].insert(-INF);
        occ[i].insert(INF);
    }
 
    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 (ok[i]) {
            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:132: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

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 103672 KB Output is correct
2 Correct 100 ms 103676 KB Output is correct
3 Correct 98 ms 103800 KB Output is correct
4 Correct 122 ms 103684 KB Output is correct
5 Correct 104 ms 103796 KB Output is correct
6 Correct 104 ms 104184 KB Output is correct
7 Correct 100 ms 103864 KB Output is correct
8 Correct 102 ms 104056 KB Output is correct
9 Correct 151 ms 104056 KB Output is correct
10 Correct 102 ms 104056 KB Output is correct
11 Correct 103 ms 104200 KB Output is correct
12 Correct 108 ms 104088 KB Output is correct
13 Correct 99 ms 103880 KB Output is correct
14 Correct 100 ms 103928 KB Output is correct
15 Correct 104 ms 104056 KB Output is correct
16 Correct 99 ms 104056 KB Output is correct
17 Correct 102 ms 104060 KB Output is correct
18 Correct 101 ms 104056 KB Output is correct
19 Correct 101 ms 104056 KB Output is correct
20 Correct 102 ms 104056 KB Output is correct
21 Correct 99 ms 103800 KB Output is correct
22 Correct 101 ms 104036 KB Output is correct
23 Correct 100 ms 104056 KB Output is correct
24 Correct 102 ms 104056 KB Output is correct
25 Correct 108 ms 104276 KB Output is correct
26 Correct 101 ms 104056 KB Output is correct
27 Correct 99 ms 103928 KB Output is correct
28 Correct 103 ms 104144 KB Output is correct
29 Correct 105 ms 103928 KB Output is correct
30 Correct 99 ms 103812 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 103672 KB Output is correct
2 Correct 100 ms 103676 KB Output is correct
3 Correct 98 ms 103800 KB Output is correct
4 Correct 122 ms 103684 KB Output is correct
5 Correct 104 ms 103796 KB Output is correct
6 Correct 104 ms 104184 KB Output is correct
7 Correct 100 ms 103864 KB Output is correct
8 Correct 102 ms 104056 KB Output is correct
9 Correct 151 ms 104056 KB Output is correct
10 Correct 102 ms 104056 KB Output is correct
11 Correct 103 ms 104200 KB Output is correct
12 Correct 108 ms 104088 KB Output is correct
13 Correct 99 ms 103880 KB Output is correct
14 Correct 100 ms 103928 KB Output is correct
15 Correct 104 ms 104056 KB Output is correct
16 Correct 99 ms 104056 KB Output is correct
17 Correct 102 ms 104060 KB Output is correct
18 Correct 101 ms 104056 KB Output is correct
19 Correct 101 ms 104056 KB Output is correct
20 Correct 102 ms 104056 KB Output is correct
21 Correct 99 ms 103800 KB Output is correct
22 Correct 101 ms 104036 KB Output is correct
23 Correct 100 ms 104056 KB Output is correct
24 Correct 102 ms 104056 KB Output is correct
25 Correct 108 ms 104276 KB Output is correct
26 Correct 101 ms 104056 KB Output is correct
27 Correct 99 ms 103928 KB Output is correct
28 Correct 103 ms 104144 KB Output is correct
29 Correct 105 ms 103928 KB Output is correct
30 Correct 99 ms 103812 KB Output is correct
31 Correct 1463 ms 194780 KB Output is correct
32 Correct 239 ms 110408 KB Output is correct
33 Correct 1312 ms 192216 KB Output is correct
34 Correct 1279 ms 191660 KB Output is correct
35 Correct 1476 ms 195368 KB Output is correct
36 Correct 1350 ms 194512 KB Output is correct
37 Correct 953 ms 184252 KB Output is correct
38 Correct 952 ms 181244 KB Output is correct
39 Correct 719 ms 168656 KB Output is correct
40 Correct 784 ms 171084 KB Output is correct
41 Correct 904 ms 162912 KB Output is correct
42 Correct 982 ms 163812 KB Output is correct
43 Correct 206 ms 113264 KB Output is correct
44 Correct 982 ms 161784 KB Output is correct
45 Correct 914 ms 157252 KB Output is correct
46 Correct 745 ms 148704 KB Output is correct
47 Correct 518 ms 143040 KB Output is correct
48 Correct 498 ms 142640 KB Output is correct
49 Correct 655 ms 150112 KB Output is correct
50 Correct 681 ms 157716 KB Output is correct
51 Correct 605 ms 148268 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3459 ms 277684 KB Output is correct
2 Correct 4523 ms 308972 KB Output is correct
3 Correct 2017 ms 254544 KB Output is correct
4 Correct 3104 ms 272740 KB Output is correct
5 Correct 3515 ms 279092 KB Output is correct
6 Correct 4105 ms 300364 KB Output is correct
7 Correct 1838 ms 253756 KB Output is correct
8 Correct 2797 ms 269272 KB Output is correct
9 Correct 3578 ms 293968 KB Output is correct
10 Correct 3636 ms 321996 KB Output is correct
11 Correct 2355 ms 312824 KB Output is correct
12 Correct 3121 ms 317596 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5041 ms 435976 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 103672 KB Output is correct
2 Correct 100 ms 103676 KB Output is correct
3 Correct 98 ms 103800 KB Output is correct
4 Correct 122 ms 103684 KB Output is correct
5 Correct 104 ms 103796 KB Output is correct
6 Correct 104 ms 104184 KB Output is correct
7 Correct 100 ms 103864 KB Output is correct
8 Correct 102 ms 104056 KB Output is correct
9 Correct 151 ms 104056 KB Output is correct
10 Correct 102 ms 104056 KB Output is correct
11 Correct 103 ms 104200 KB Output is correct
12 Correct 108 ms 104088 KB Output is correct
13 Correct 99 ms 103880 KB Output is correct
14 Correct 100 ms 103928 KB Output is correct
15 Correct 104 ms 104056 KB Output is correct
16 Correct 99 ms 104056 KB Output is correct
17 Correct 102 ms 104060 KB Output is correct
18 Correct 101 ms 104056 KB Output is correct
19 Correct 101 ms 104056 KB Output is correct
20 Correct 102 ms 104056 KB Output is correct
21 Correct 99 ms 103800 KB Output is correct
22 Correct 101 ms 104036 KB Output is correct
23 Correct 100 ms 104056 KB Output is correct
24 Correct 102 ms 104056 KB Output is correct
25 Correct 108 ms 104276 KB Output is correct
26 Correct 101 ms 104056 KB Output is correct
27 Correct 99 ms 103928 KB Output is correct
28 Correct 103 ms 104144 KB Output is correct
29 Correct 105 ms 103928 KB Output is correct
30 Correct 99 ms 103812 KB Output is correct
31 Correct 1463 ms 194780 KB Output is correct
32 Correct 239 ms 110408 KB Output is correct
33 Correct 1312 ms 192216 KB Output is correct
34 Correct 1279 ms 191660 KB Output is correct
35 Correct 1476 ms 195368 KB Output is correct
36 Correct 1350 ms 194512 KB Output is correct
37 Correct 953 ms 184252 KB Output is correct
38 Correct 952 ms 181244 KB Output is correct
39 Correct 719 ms 168656 KB Output is correct
40 Correct 784 ms 171084 KB Output is correct
41 Correct 904 ms 162912 KB Output is correct
42 Correct 982 ms 163812 KB Output is correct
43 Correct 206 ms 113264 KB Output is correct
44 Correct 982 ms 161784 KB Output is correct
45 Correct 914 ms 157252 KB Output is correct
46 Correct 745 ms 148704 KB Output is correct
47 Correct 518 ms 143040 KB Output is correct
48 Correct 498 ms 142640 KB Output is correct
49 Correct 655 ms 150112 KB Output is correct
50 Correct 681 ms 157716 KB Output is correct
51 Correct 605 ms 148268 KB Output is correct
52 Correct 589 ms 148376 KB Output is correct
53 Correct 579 ms 146208 KB Output is correct
54 Correct 969 ms 167884 KB Output is correct
55 Correct 840 ms 161208 KB Output is correct
56 Correct 732 ms 158944 KB Output is correct
57 Correct 880 ms 160828 KB Output is correct
58 Correct 910 ms 159516 KB Output is correct
59 Correct 790 ms 157152 KB Output is correct
60 Correct 924 ms 161212 KB Output is correct
61 Correct 224 ms 117856 KB Output is correct
62 Correct 628 ms 150676 KB Output is correct
63 Correct 838 ms 161600 KB Output is correct
64 Correct 979 ms 165984 KB Output is correct
65 Correct 981 ms 170844 KB Output is correct
66 Correct 925 ms 165088 KB Output is correct
67 Correct 238 ms 110184 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 103672 KB Output is correct
2 Correct 100 ms 103676 KB Output is correct
3 Correct 98 ms 103800 KB Output is correct
4 Correct 122 ms 103684 KB Output is correct
5 Correct 104 ms 103796 KB Output is correct
6 Correct 104 ms 104184 KB Output is correct
7 Correct 100 ms 103864 KB Output is correct
8 Correct 102 ms 104056 KB Output is correct
9 Correct 151 ms 104056 KB Output is correct
10 Correct 102 ms 104056 KB Output is correct
11 Correct 103 ms 104200 KB Output is correct
12 Correct 108 ms 104088 KB Output is correct
13 Correct 99 ms 103880 KB Output is correct
14 Correct 100 ms 103928 KB Output is correct
15 Correct 104 ms 104056 KB Output is correct
16 Correct 99 ms 104056 KB Output is correct
17 Correct 102 ms 104060 KB Output is correct
18 Correct 101 ms 104056 KB Output is correct
19 Correct 101 ms 104056 KB Output is correct
20 Correct 102 ms 104056 KB Output is correct
21 Correct 99 ms 103800 KB Output is correct
22 Correct 101 ms 104036 KB Output is correct
23 Correct 100 ms 104056 KB Output is correct
24 Correct 102 ms 104056 KB Output is correct
25 Correct 108 ms 104276 KB Output is correct
26 Correct 101 ms 104056 KB Output is correct
27 Correct 99 ms 103928 KB Output is correct
28 Correct 103 ms 104144 KB Output is correct
29 Correct 105 ms 103928 KB Output is correct
30 Correct 99 ms 103812 KB Output is correct
31 Correct 1463 ms 194780 KB Output is correct
32 Correct 239 ms 110408 KB Output is correct
33 Correct 1312 ms 192216 KB Output is correct
34 Correct 1279 ms 191660 KB Output is correct
35 Correct 1476 ms 195368 KB Output is correct
36 Correct 1350 ms 194512 KB Output is correct
37 Correct 953 ms 184252 KB Output is correct
38 Correct 952 ms 181244 KB Output is correct
39 Correct 719 ms 168656 KB Output is correct
40 Correct 784 ms 171084 KB Output is correct
41 Correct 904 ms 162912 KB Output is correct
42 Correct 982 ms 163812 KB Output is correct
43 Correct 206 ms 113264 KB Output is correct
44 Correct 982 ms 161784 KB Output is correct
45 Correct 914 ms 157252 KB Output is correct
46 Correct 745 ms 148704 KB Output is correct
47 Correct 518 ms 143040 KB Output is correct
48 Correct 498 ms 142640 KB Output is correct
49 Correct 655 ms 150112 KB Output is correct
50 Correct 681 ms 157716 KB Output is correct
51 Correct 605 ms 148268 KB Output is correct
52 Correct 3459 ms 277684 KB Output is correct
53 Correct 4523 ms 308972 KB Output is correct
54 Correct 2017 ms 254544 KB Output is correct
55 Correct 3104 ms 272740 KB Output is correct
56 Correct 3515 ms 279092 KB Output is correct
57 Correct 4105 ms 300364 KB Output is correct
58 Correct 1838 ms 253756 KB Output is correct
59 Correct 2797 ms 269272 KB Output is correct
60 Correct 3578 ms 293968 KB Output is correct
61 Correct 3636 ms 321996 KB Output is correct
62 Correct 2355 ms 312824 KB Output is correct
63 Correct 3121 ms 317596 KB Output is correct
64 Execution timed out 5041 ms 435976 KB Time limit exceeded
65 Halted 0 ms 0 KB -