oj.uz

답안 #829634

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
829634 2023-08-18T13:39:12 Z erdemkiraz 새 집 (APIO18_new_home) C++17
57 / 100
 5000 ms 192888 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair < int, int > ii;
 
const int N = 3e5 + 5;
const int OUT = 0, QUE = 1;
const int addPositive = 0, addNegative = 1;
 
int n, q, k, total;
int ans[N];
map < int, int > s[N];
 
int z, g;
 
int tree[2][N << 1];
 
int curX;
vector < pair < int, pair < int*, int > > > changes;
 
void update(int t, int l, int r, int x) {
    for(l += N, r += N; l <= r; l = (l + 1) >> 1, r = (r - 1) >> 1) {
        if((l & 1) and x > tree[t][l]) {
            changes.push_back({curX, {&tree[t][l], tree[t][l]}});
            tree[t][l] = x;
        }
        if((~r & 1) and x > tree[t][r]) {
            changes.push_back({curX, {&tree[t][r], tree[t][r]}});
            tree[t][r] = x;
        }
    }
}
 
int get(int t, int x) {
    int res = -1e9;
    x += N;
    while(x >= 1) {
        res = max(res, tree[t][x]);
        x >>= 1;
    }
    return res;
}
 
inline int read() {
    char c = getchar();
    int x = 0;
    while(c < '0' or c > '9')
        c = getchar();
    while('0' <= c and c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x;
}
 
vector < pair < ii, int > > M[N * 4];
int isany[N * 4];
 
void create(int x, int type, int l, int r, int x1, int x2, int v, int y) {
    if(x2 < l or r < x1)
        return;
    if(type == QUE)
        isany[x] = 1;
    if(x1 <= l and r <= x2) {
        // printf("type = %d l = %d r = %d\n", type, l, r);
        M[x].push_back({{type, v}, y});
        return;
    }
    int m = (l + r) >> 1;
    create(x + x, type, l, m, x1, x2, v, y);
    create(x + x + 1, type, m + 1, r, x1, x2, v, y);
}
 
vector < int > ques;
int rid(int x) {
    return lower_bound(ques.begin(), ques.end(), x) - ques.begin() + 1;
}
int lid(int x) {
    return upper_bound(ques.begin(), ques.end(), x) - ques.begin();
}
 
vector < int > ins;
int ri(int x) {
    return lower_bound(ins.begin(), ins.end(), x) - ins.begin() + 1;
}
int li(int x) {
    return upper_bound(ins.begin(), ins.end(), x) - ins.begin();
}
 
void solve(int x, int l, int r) {
    if(!isany[x])
        return;
 
    int delTotal = 0;
 
    curX = x;
 
    bool HARD_FAIL = 0;
 
    for(auto tmp : M[x]) {
        int type = tmp.first.first, x = tmp.first.second, t = tmp.second;
        if(type == OUT) {
            if(--s[t][x])
                continue;
            s[t].erase(x);
            // printf("deleting location = %d type = %d\n", x, t);
            auto it = s[t].begin();
            int nxt = (it=s[t].upper_bound(x)) == s[t].end() ? -1 : it->first;
                int bef = (it=s[t].lower_bound(x)) == s[t].begin() ? -1 : (--it)->first;
            if(bef == -1 and nxt == -1) {
                HARD_FAIL = 1;
            }
            else if(bef == -1) {
                update(addNegative, 1, lid((x + nxt) / 2), nxt);
            }
            else if(nxt == -1) {
                update(addPositive, rid((bef + x) / 2 + 1), z, -bef);
            }
            else {
                update(addPositive, rid((bef + x) / 2 + 1), lid((bef + nxt) / 2), -bef);
                update(addNegative, rid((bef + nxt) / 2 + 1), lid((x + nxt) / 2), nxt);
            }
        }
    }
 
    if(HARD_FAIL) {
        for(auto tmp : M[x]) {
            int type = tmp.first.first, x = tmp.first.second, t = tmp.second;
            if(type == OUT) {
                // printf("reverting x = %d t = %d\n", x, t);
                s[t][x]++;
            }
        }
 
        while(!changes.empty() and changes.back().first == x) {
            *changes.back().second.first = changes.back().second.second;
            changes.pop_back();
        }
        return;
    }
 
    if(l == r) {
        for(auto tmp : M[x]) {
            int type = tmp.first.first, x = tmp.first.second, t = tmp.second;
            if(type == QUE) {
                int a = get(0, rid(x));
                int b = get(1, rid(x));
                // printf("que x = %d i = %d a = %d b = %d\n", x, t, a, b);
                ans[t] = max(a + x, b - x);
            }
        }
    }
    else {
        int m = (l + r) >> 1;
        solve(x + x, l, m);
        solve(x + x + 1, m + 1, r);
    }
 
    for(auto tmp : M[x]) {
        int type = tmp.first.first, x = tmp.first.second, t = tmp.second;
        if(type == OUT) {
            // printf("reverting x = %d t = %d\n", x, t);
            s[t][x]++;
        }
    }
 
    while(!changes.empty() and changes.back().first == x) {
        *changes.back().second.first = changes.back().second.second;
        changes.pop_back();
    }
 
}
 
int x1[N], t1[N], a1[N], b1[N], x2[N], y2[N];
 
int main() {
 
    n = read();
    k = read();
    q = read();
 
    for(int i = 1; i <= n; i++) {
        int x, t, a, b;
        x = read();
        t = read();
        a = read();
        b = read();
        x1[i]=x,t1[i]=t,a1[i]=a,b1[i]=b;
    }
 
    for(int i = 1; i <= q; i++) {
        int x, y;
        x = read();
        y = read();
        x2[i] = x;
        y2[i] = y;
        ins.push_back(y);
        ques.push_back(x);
    }
 
    sort(ques.begin(), ques.end());
    ques.resize(unique(ques.begin(), ques.end()) - ques.begin());
    z = ques.size();
 
    ins.push_back(0);
    ins.push_back(1e8 + 1);
 
    sort(ins.begin(), ins.end());
    ins.resize(unique(ins.begin(), ins.end()) - ins.begin());
    g = ins.size();
 
    for(int i = 1; i <= n; i++) {
        int x=x1[i], t=t1[i], a=a1[i], b=b1[i];
        s[t][x]++;
        a = li(a - 1);
        b = ri(b + 1);
        if(a != 1) {
            create(1, OUT, 1, g, 1, a, x, t);
        }
        if(b != g) {
            create(1, OUT, 1, g, b, g, x, t);
        }
    }
 
    for(int i = 1; i <= q; i++) {
        int x=x2[i], y=y2[i];
        ans[i] = -1;
        create(1, QUE, 1, g, ri(y), ri(y), x, i);
    }
 
    memset(tree, -63, sizeof(tree));
 
    for(int i = 1; i <= k; i++) {
        vector < int > v;
        for(auto x : s[i])
            v.push_back(x.first);
        if(v.empty())
            break;
        total++;
        update(addNegative, 1, rid(v[0]), v[0]);
        for(int it = 0; it + 1 < v.size(); it++) {
            update(addPositive, rid(v[it]), lid((v[it] + v[it + 1]) / 2), -v[it]);
            update(addNegative, rid((v[it] + v[it + 1]) / 2 + 1), lid(v[it + 1]), v[it + 1]);
        }
        update(addPositive, rid(v.back()), z, -v.back());
    }
 
    changes.clear();
 
    if(total == k)
        solve(1, 1, g);
 
    for(int i = 1; i <= q; i++)
        printf("%d\n", ans[i]);
 
    return 0;
 
}

Compilation message

new_home.cpp: In function 'void solve(int, int, int)':
new_home.cpp:96:9: warning: unused variable 'delTotal' [-Wunused-variable]
   96 |     int delTotal = 0;
      |         ^~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:243:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  243 |         for(int it = 0; it + 1 < v.size(); it++) {
      |                         ~~~~~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47320 KB Output is correct
2 Correct 19 ms 47316 KB Output is correct
3 Correct 20 ms 47208 KB Output is correct
4 Correct 20 ms 47248 KB Output is correct
5 Correct 21 ms 47356 KB Output is correct
6 Correct 22 ms 47484 KB Output is correct
7 Correct 21 ms 47476 KB Output is correct
8 Correct 20 ms 47444 KB Output is correct
9 Correct 21 ms 47468 KB Output is correct
10 Correct 21 ms 47520 KB Output is correct
11 Correct 20 ms 47476 KB Output is correct
12 Correct 23 ms 47464 KB Output is correct
13 Correct 21 ms 47528 KB Output is correct
14 Correct 22 ms 47520 KB Output is correct
15 Correct 22 ms 47476 KB Output is correct
16 Correct 25 ms 47544 KB Output is correct
17 Correct 22 ms 47480 KB Output is correct
18 Correct 21 ms 47468 KB Output is correct
19 Correct 22 ms 47488 KB Output is correct
20 Correct 22 ms 47496 KB Output is correct
21 Correct 20 ms 47256 KB Output is correct
22 Correct 21 ms 47480 KB Output is correct
23 Correct 20 ms 47444 KB Output is correct
24 Correct 21 ms 47528 KB Output is correct
25 Correct 23 ms 47512 KB Output is correct
26 Correct 21 ms 47476 KB Output is correct
27 Correct 21 ms 47316 KB Output is correct
28 Correct 21 ms 47476 KB Output is correct
29 Correct 22 ms 47480 KB Output is correct
30 Correct 25 ms 47616 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47320 KB Output is correct
2 Correct 19 ms 47316 KB Output is correct
3 Correct 20 ms 47208 KB Output is correct
4 Correct 20 ms 47248 KB Output is correct
5 Correct 21 ms 47356 KB Output is correct
6 Correct 22 ms 47484 KB Output is correct
7 Correct 21 ms 47476 KB Output is correct
8 Correct 20 ms 47444 KB Output is correct
9 Correct 21 ms 47468 KB Output is correct
10 Correct 21 ms 47520 KB Output is correct
11 Correct 20 ms 47476 KB Output is correct
12 Correct 23 ms 47464 KB Output is correct
13 Correct 21 ms 47528 KB Output is correct
14 Correct 22 ms 47520 KB Output is correct
15 Correct 22 ms 47476 KB Output is correct
16 Correct 25 ms 47544 KB Output is correct
17 Correct 22 ms 47480 KB Output is correct
18 Correct 21 ms 47468 KB Output is correct
19 Correct 22 ms 47488 KB Output is correct
20 Correct 22 ms 47496 KB Output is correct
21 Correct 20 ms 47256 KB Output is correct
22 Correct 21 ms 47480 KB Output is correct
23 Correct 20 ms 47444 KB Output is correct
24 Correct 21 ms 47528 KB Output is correct
25 Correct 23 ms 47512 KB Output is correct
26 Correct 21 ms 47476 KB Output is correct
27 Correct 21 ms 47316 KB Output is correct
28 Correct 21 ms 47476 KB Output is correct
29 Correct 22 ms 47480 KB Output is correct
30 Correct 25 ms 47616 KB Output is correct
31 Correct 1025 ms 83208 KB Output is correct
32 Correct 57 ms 54060 KB Output is correct
33 Correct 1086 ms 83748 KB Output is correct
34 Correct 992 ms 83700 KB Output is correct
35 Correct 1054 ms 83308 KB Output is correct
36 Correct 1072 ms 83168 KB Output is correct
37 Correct 900 ms 84176 KB Output is correct
38 Correct 918 ms 78240 KB Output is correct
39 Correct 708 ms 78240 KB Output is correct
40 Correct 762 ms 78296 KB Output is correct
41 Correct 757 ms 83928 KB Output is correct
42 Correct 506 ms 83952 KB Output is correct
43 Correct 40 ms 53120 KB Output is correct
44 Correct 748 ms 84036 KB Output is correct
45 Correct 821 ms 84020 KB Output is correct
46 Correct 935 ms 78092 KB Output is correct
47 Correct 471 ms 77068 KB Output is correct
48 Correct 495 ms 76576 KB Output is correct
49 Correct 564 ms 83412 KB Output is correct
50 Correct 471 ms 84980 KB Output is correct
51 Correct 601 ms 77004 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 809 ms 136108 KB Output is correct
2 Correct 708 ms 111684 KB Output is correct
3 Correct 715 ms 111536 KB Output is correct
4 Correct 794 ms 136088 KB Output is correct
5 Correct 627 ms 94268 KB Output is correct
6 Correct 662 ms 111904 KB Output is correct
7 Correct 635 ms 111572 KB Output is correct
8 Correct 737 ms 136156 KB Output is correct
9 Correct 759 ms 136108 KB Output is correct
10 Correct 693 ms 136164 KB Output is correct
11 Correct 472 ms 135752 KB Output is correct
12 Correct 548 ms 136040 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4462 ms 180452 KB Output is correct
2 Correct 152 ms 74440 KB Output is correct
3 Execution timed out 5020 ms 192888 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47320 KB Output is correct
2 Correct 19 ms 47316 KB Output is correct
3 Correct 20 ms 47208 KB Output is correct
4 Correct 20 ms 47248 KB Output is correct
5 Correct 21 ms 47356 KB Output is correct
6 Correct 22 ms 47484 KB Output is correct
7 Correct 21 ms 47476 KB Output is correct
8 Correct 20 ms 47444 KB Output is correct
9 Correct 21 ms 47468 KB Output is correct
10 Correct 21 ms 47520 KB Output is correct
11 Correct 20 ms 47476 KB Output is correct
12 Correct 23 ms 47464 KB Output is correct
13 Correct 21 ms 47528 KB Output is correct
14 Correct 22 ms 47520 KB Output is correct
15 Correct 22 ms 47476 KB Output is correct
16 Correct 25 ms 47544 KB Output is correct
17 Correct 22 ms 47480 KB Output is correct
18 Correct 21 ms 47468 KB Output is correct
19 Correct 22 ms 47488 KB Output is correct
20 Correct 22 ms 47496 KB Output is correct
21 Correct 20 ms 47256 KB Output is correct
22 Correct 21 ms 47480 KB Output is correct
23 Correct 20 ms 47444 KB Output is correct
24 Correct 21 ms 47528 KB Output is correct
25 Correct 23 ms 47512 KB Output is correct
26 Correct 21 ms 47476 KB Output is correct
27 Correct 21 ms 47316 KB Output is correct
28 Correct 21 ms 47476 KB Output is correct
29 Correct 22 ms 47480 KB Output is correct
30 Correct 25 ms 47616 KB Output is correct
31 Correct 1025 ms 83208 KB Output is correct
32 Correct 57 ms 54060 KB Output is correct
33 Correct 1086 ms 83748 KB Output is correct
34 Correct 992 ms 83700 KB Output is correct
35 Correct 1054 ms 83308 KB Output is correct
36 Correct 1072 ms 83168 KB Output is correct
37 Correct 900 ms 84176 KB Output is correct
38 Correct 918 ms 78240 KB Output is correct
39 Correct 708 ms 78240 KB Output is correct
40 Correct 762 ms 78296 KB Output is correct
41 Correct 757 ms 83928 KB Output is correct
42 Correct 506 ms 83952 KB Output is correct
43 Correct 40 ms 53120 KB Output is correct
44 Correct 748 ms 84036 KB Output is correct
45 Correct 821 ms 84020 KB Output is correct
46 Correct 935 ms 78092 KB Output is correct
47 Correct 471 ms 77068 KB Output is correct
48 Correct 495 ms 76576 KB Output is correct
49 Correct 564 ms 83412 KB Output is correct
50 Correct 471 ms 84980 KB Output is correct
51 Correct 601 ms 77004 KB Output is correct
52 Correct 187 ms 77252 KB Output is correct
53 Correct 191 ms 77664 KB Output is correct
54 Correct 233 ms 83320 KB Output is correct
55 Correct 550 ms 82864 KB Output is correct
56 Correct 435 ms 74796 KB Output is correct
57 Correct 715 ms 83508 KB Output is correct
58 Correct 458 ms 78760 KB Output is correct
59 Correct 344 ms 77348 KB Output is correct
60 Correct 561 ms 84272 KB Output is correct
61 Correct 45 ms 56044 KB Output is correct
62 Correct 169 ms 76964 KB Output is correct
63 Correct 300 ms 77356 KB Output is correct
64 Correct 447 ms 83880 KB Output is correct
65 Correct 545 ms 85060 KB Output is correct
66 Correct 719 ms 84096 KB Output is correct
67 Correct 130 ms 58732 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47320 KB Output is correct
2 Correct 19 ms 47316 KB Output is correct
3 Correct 20 ms 47208 KB Output is correct
4 Correct 20 ms 47248 KB Output is correct
5 Correct 21 ms 47356 KB Output is correct
6 Correct 22 ms 47484 KB Output is correct
7 Correct 21 ms 47476 KB Output is correct
8 Correct 20 ms 47444 KB Output is correct
9 Correct 21 ms 47468 KB Output is correct
10 Correct 21 ms 47520 KB Output is correct
11 Correct 20 ms 47476 KB Output is correct
12 Correct 23 ms 47464 KB Output is correct
13 Correct 21 ms 47528 KB Output is correct
14 Correct 22 ms 47520 KB Output is correct
15 Correct 22 ms 47476 KB Output is correct
16 Correct 25 ms 47544 KB Output is correct
17 Correct 22 ms 47480 KB Output is correct
18 Correct 21 ms 47468 KB Output is correct
19 Correct 22 ms 47488 KB Output is correct
20 Correct 22 ms 47496 KB Output is correct
21 Correct 20 ms 47256 KB Output is correct
22 Correct 21 ms 47480 KB Output is correct
23 Correct 20 ms 47444 KB Output is correct
24 Correct 21 ms 47528 KB Output is correct
25 Correct 23 ms 47512 KB Output is correct
26 Correct 21 ms 47476 KB Output is correct
27 Correct 21 ms 47316 KB Output is correct
28 Correct 21 ms 47476 KB Output is correct
29 Correct 22 ms 47480 KB Output is correct
30 Correct 25 ms 47616 KB Output is correct
31 Correct 1025 ms 83208 KB Output is correct
32 Correct 57 ms 54060 KB Output is correct
33 Correct 1086 ms 83748 KB Output is correct
34 Correct 992 ms 83700 KB Output is correct
35 Correct 1054 ms 83308 KB Output is correct
36 Correct 1072 ms 83168 KB Output is correct
37 Correct 900 ms 84176 KB Output is correct
38 Correct 918 ms 78240 KB Output is correct
39 Correct 708 ms 78240 KB Output is correct
40 Correct 762 ms 78296 KB Output is correct
41 Correct 757 ms 83928 KB Output is correct
42 Correct 506 ms 83952 KB Output is correct
43 Correct 40 ms 53120 KB Output is correct
44 Correct 748 ms 84036 KB Output is correct
45 Correct 821 ms 84020 KB Output is correct
46 Correct 935 ms 78092 KB Output is correct
47 Correct 471 ms 77068 KB Output is correct
48 Correct 495 ms 76576 KB Output is correct
49 Correct 564 ms 83412 KB Output is correct
50 Correct 471 ms 84980 KB Output is correct
51 Correct 601 ms 77004 KB Output is correct
52 Correct 809 ms 136108 KB Output is correct
53 Correct 708 ms 111684 KB Output is correct
54 Correct 715 ms 111536 KB Output is correct
55 Correct 794 ms 136088 KB Output is correct
56 Correct 627 ms 94268 KB Output is correct
57 Correct 662 ms 111904 KB Output is correct
58 Correct 635 ms 111572 KB Output is correct
59 Correct 737 ms 136156 KB Output is correct
60 Correct 759 ms 136108 KB Output is correct
61 Correct 693 ms 136164 KB Output is correct
62 Correct 472 ms 135752 KB Output is correct
63 Correct 548 ms 136040 KB Output is correct
64 Correct 4462 ms 180452 KB Output is correct
65 Correct 152 ms 74440 KB Output is correct
66 Execution timed out 5020 ms 192888 KB Time limit exceeded
67 Halted 0 ms 0 KB -