oj.uz

Submission #864610

# Submission time Handle Problem Language Result Execution time Memory
864610 2023-10-23T10:31:29 Z danikoynov New Home (APIO18_new_home) C++14
47 / 100
 2236 ms 360268 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 3e5 + 10, inf = 1e9;

struct store
{
    int x, t, a, b;
}s[maxn];

struct query
{
    int l, y, idx;
}task[maxn];

int n, k, q;

void input()
{
    cin >> n >> k >> q;
    for (int i = 1; i <= n; i ++)
        cin >> s[i].x >> s[i].t >> s[i].a >> s[i].b;

    for (int i = 1; i <= q; i ++)
        cin >> task[i].l >> task[i].y, task[i].idx = i;
}

unordered_map < int, int > rev;
int dif, back_to[2 * maxn];

int get_mid(int left, int right)
{
    if (left == right)
        return rev[left];
    
    int lf = rev[left], rf = rev[right];
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (abs(left - back_to[mf]) <= abs(right - back_to[mf]))
            lf = mf + 1;
        else
            rf = mf - 1;
    }

    return rf;
}
void compress_data()
{
    vector < int > cor;
    for (int i = 1; i <= n; i ++)
        cor.push_back(s[i].x);
    for (int i = 1; i <= q; i ++)
        cor.push_back(task[i].l);

    sort(cor.begin(), cor.end());
    int sz = cor.size();

    for (int i = 0; i < cor.size(); i ++)
    {
        if (i != 0 || cor[i - 1] != cor[i])
        {
            dif ++;
            rev[cor[i]] = dif;
            back_to[dif] = cor[i];
        }
    }
}
int type[maxn];
int solve_naive(int pivot, int year)
{
    for (int i = 1; i <= k; i ++)
        type[i] = inf;

    for (int i = 1; i <= n; i ++)
    {
        if (s[i].a <= year && s[i].b >= year)
            type[s[i].t] = min(type[s[i].t], abs(pivot - s[i].x));
    }

    int ans = -1;
    for (int i = 1; i <= k; i ++)
    {
        if (type[i] == inf)
            return -1;
        ans = max(ans, type[i]);
    }

    return ans;
}

bool cmp_query(query t1, query t2)
{
    return t1.y < t2.y;
}

struct event
{
    int type, cor, add, arrive;

    event(int _type, int _cor, int _add, int _arrive)
    {
        type = _type;
        cor = _cor;
        add = _add;
        arrive = _arrive;
    }
};

bool cmp_event(event e1, event e2)
{
    if (e1.arrive != e2.arrive)
        return e1.arrive < e2.arrive;

    if (e1.add != e2.add)
        return e1.add < e2.add;

    return e1.cor < e2.cor; /// could have dublicates
}




multiset < int > tree[4 * maxn];

void apply_update(int root, pair < int, int > val)
{
    if (val.first == -1)
    {
        tree[root].erase(tree[root].find(val.second));
    }
    else
    {
        tree[root].insert(val.second);
    }
}

void update(int root, int left, int right, int qleft, int qright, pair < int, int > val)
{
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        apply_update(root, val);
        return;
    }

    int mid = (left + right) / 2;

    update(root * 2, left, mid, qleft, qright, val);
    update(root * 2 + 1, mid + 1, right, qleft, qright, val);
}

int query(int root, int left, int right, int pos, int cor)
{   
   
    int far = 0;
    if (!tree[root].empty())
    {
        far = max(far, abs(cor - *tree[root].begin()));
        far = max(far, abs(cor - *tree[root].rbegin()));
    }
    
    if (left != right)
    {
        int mid = (left + right) / 2;
        if (pos <= mid)
            far = max(far, query(root * 2, left, mid, pos, cor));
        else
            far = max(far, query(root * 2 + 1, mid + 1, right, pos, cor));
    }
        ///cout << root << " " << left << " " << right << " " << pos << " " << cor << endl;
        ///cout << far << " : " << cor<< endl; 

    return far;
}

multiset < int > act[maxn];

void add_event(int type, int cor)
{
    multiset < int > :: iterator it = act[type].upper_bound(cor);
    int aft = *it;
    int bef = *prev(it);

    if (bef == -inf && aft == inf)
    {
        update(1, 1, dif, 1, dif, {-1, -inf});
        update(1, 1, dif, 1, rev[cor], {1, cor});
        update(1, 1, dif, rev[cor], dif, {1, cor});
        ///cout << "from to " << rev[cor] << endl;
    }
    else
    if (bef == - inf) // aft != inf
    {
        update(1, 1, dif, 1, rev[aft], {-1, aft});
        update(1, 1, dif, 1, rev[cor], {1, cor});
        int mid = get_mid(cor, aft);
        update(1, 1, dif, rev[cor], mid, {1, cor});
        update(1, 1, dif, mid + 1, rev[aft], {1, aft});
    }
    else
    if (aft == inf) // bef != inf
    {
        update(1, 1, dif, rev[bef], dif, {-1, bef});
        update(1, 1, dif, rev[cor], dif, {1, cor});
        int mid = get_mid(bef, cor);
        ///cout << "here " << mid << endl;
        update(1, 1, dif, rev[bef], mid, {1, bef});
        update(1, 1, dif, mid + 1, rev[cor], {1, cor});
    }
    else   /// aft != inf && bef != inf
    {
        int mid = get_mid(bef, aft);
        update(1, 1, dif, rev[bef], mid, {-1, bef});
        update(1, 1, dif, mid + 1, rev[aft], {-1, aft});
        int mid_left = get_mid(bef, cor);
        update(1, 1, dif, rev[bef], mid_left, {1, bef});
        update(1, 1, dif, mid_left + 1, rev[cor], {1, cor});
        int mid_right = get_mid(cor, aft);
        update(1, 1, dif, rev[cor], mid_right, {1, cor});
        update(1, 1, dif, mid_right + 1, rev[aft], {1, aft});
    }

    act[type].insert(cor);
}

void remove_event(int type, int cor)
{
    multiset < int > :: iterator it = act[type].find(cor);
    int aft = *next(it);
    int bef = *prev(it);

    if (bef == -inf && aft == inf)
    {
        update(1, 1, dif, 1, dif, {+1, -inf});
        update(1, 1, dif, 1, rev[cor], {-1, cor});
        update(1, 1, dif, rev[cor], dif, {-1, cor});
    }
    else
    if (bef == - inf) // aft != inf
    {
        update(1, 1, dif, 1, rev[aft], {1, aft});
        update(1, 1, dif, 1, rev[cor], {-1, cor});
        int mid = get_mid(cor, aft);
        update(1, 1, dif, rev[cor], mid, {-1, cor});
        update(1, 1, dif, mid + 1, rev[aft], {-1, aft});
    }
    else
    if (aft == inf) // bef != inf
    {
        update(1, 1, dif, rev[bef], dif, {1, bef});
        update(1, 1, dif, rev[cor], dif, {-1, cor});
        int mid = get_mid(bef, cor);
        update(1, 1, dif, rev[bef], mid, {-1, bef});
        update(1, 1, dif, mid + 1, rev[cor], {-1, cor});
    }
    else   /// aft != inf && bef != inf
    {
        int mid = get_mid(bef, aft);
        update(1, 1, dif, rev[bef], mid, {1, bef});
        update(1, 1, dif, mid + 1, rev[aft], {1, aft});
        int mid_left = get_mid(bef, cor);
        update(1, 1, dif, rev[bef], mid_left, {-1, bef});
        update(1, 1, dif, mid_left + 1, rev[cor], {-1, cor});
        int mid_right = get_mid(cor, aft);
        update(1, 1, dif, rev[cor], mid_right, {-1, cor});
        update(1, 1, dif, mid_right + 1, rev[aft], {-1, aft});
    }

    act[type].erase(it);
}

int ans[maxn];

int single_query(int cor)
{
    /**int far = 0;
    for (int i = 1; i <= k; i ++)
    {
        multiset < int > :: iterator it = act[i].upper_bound(cor);
        int closest = inf;
        ///if (it != act[i].end())
        ///cout << "here " << cor << " " << *it << endl;
        if (it != act[i].end())
            closest = min(closest, *it - cor);
        
        if (it != act[i].begin())
            closest = min(closest, cor - *prev(it));
        
        far = max(far, closest);
        ///cout << far << endl;
    }*/

    int far = query(1, 1, dif, rev[cor], cor);

    if (far > 2e8)
        return -1;

    return far;
}

void answer_queries()
{
    sort(task + 1, task + q + 1, cmp_query);
    
    vector < event > events;
    for (int i = 1; i <= n; i ++)
    {
        events.push_back(event(s[i].t, s[i].x, 1, s[i].a));
        events.push_back(event(s[i].t, s[i].x, -1, s[i].b + 1));
    }

    sort(events.begin(), events.end(), cmp_event);

    for (int i = 1; i <= k; i ++)
    {
        act[i].insert(-inf);
        act[i].insert(inf);
        update(1, 1, dif, 1, dif, {1, -inf});
    }

    int pt = 1;
    for (event cur : events)
    {
        
        while(pt <= q && task[pt].y < cur.arrive)
        {
            ans[task[pt].idx] = single_query(task[pt].l);
            pt ++;
        }
        ///cout << "event " << cur.arrive << " " << cur.add << " " << cur.cor << endl;
        if (cur.add == 1)
            add_event(cur.type, cur.cor);
        else
            remove_event(cur.type, cur.cor);
    }

    while(pt <= q)
    {
         ans[task[pt].idx] = single_query(task[pt].l);
         pt ++;
    }

    for (int i = 1; i <= q; i ++)
        cout << ans[i] << endl;
}
void solve()
{
    input();
    compress_data();
    answer_queries();
}

int main()
{
    solve();
    return 0;
}

/**
2 1 2
3 1 1 3
5 1 3 4
3 3
3 4




4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

1 1 1
100000000 1 1 1
1 1



*/

Compilation message

new_home.cpp: In function 'void compress_data()':
new_home.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int i = 0; i < cor.size(); i ++)
      |                     ~~^~~~~~~~~~~~
new_home.cpp:59:9: warning: unused variable 'sz' [-Wunused-variable]
   59 |     int sz = cor.size();
      |         ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 78424 KB Output is correct
2 Correct 14 ms 78172 KB Output is correct
3 Correct 14 ms 78396 KB Output is correct
4 Correct 14 ms 78428 KB Output is correct
5 Correct 16 ms 78424 KB Output is correct
6 Correct 18 ms 78428 KB Output is correct
7 Correct 16 ms 78428 KB Output is correct
8 Correct 17 ms 78684 KB Output is correct
9 Correct 16 ms 78684 KB Output is correct
10 Correct 17 ms 78412 KB Output is correct
11 Correct 16 ms 78428 KB Output is correct
12 Correct 16 ms 78296 KB Output is correct
13 Correct 18 ms 78424 KB Output is correct
14 Correct 16 ms 78428 KB Output is correct
15 Correct 17 ms 78428 KB Output is correct
16 Correct 16 ms 78380 KB Output is correct
17 Correct 17 ms 78428 KB Output is correct
18 Correct 17 ms 78428 KB Output is correct
19 Correct 17 ms 78428 KB Output is correct
20 Correct 16 ms 78352 KB Output is correct
21 Correct 16 ms 78428 KB Output is correct
22 Correct 16 ms 78680 KB Output is correct
23 Correct 17 ms 78428 KB Output is correct
24 Correct 16 ms 78588 KB Output is correct
25 Correct 17 ms 78352 KB Output is correct
26 Correct 21 ms 78428 KB Output is correct
27 Correct 17 ms 78424 KB Output is correct
28 Correct 16 ms 78428 KB Output is correct
29 Correct 16 ms 78440 KB Output is correct
30 Correct 16 ms 78428 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 78424 KB Output is correct
2 Correct 14 ms 78172 KB Output is correct
3 Correct 14 ms 78396 KB Output is correct
4 Correct 14 ms 78428 KB Output is correct
5 Correct 16 ms 78424 KB Output is correct
6 Correct 18 ms 78428 KB Output is correct
7 Correct 16 ms 78428 KB Output is correct
8 Correct 17 ms 78684 KB Output is correct
9 Correct 16 ms 78684 KB Output is correct
10 Correct 17 ms 78412 KB Output is correct
11 Correct 16 ms 78428 KB Output is correct
12 Correct 16 ms 78296 KB Output is correct
13 Correct 18 ms 78424 KB Output is correct
14 Correct 16 ms 78428 KB Output is correct
15 Correct 17 ms 78428 KB Output is correct
16 Correct 16 ms 78380 KB Output is correct
17 Correct 17 ms 78428 KB Output is correct
18 Correct 17 ms 78428 KB Output is correct
19 Correct 17 ms 78428 KB Output is correct
20 Correct 16 ms 78352 KB Output is correct
21 Correct 16 ms 78428 KB Output is correct
22 Correct 16 ms 78680 KB Output is correct
23 Correct 17 ms 78428 KB Output is correct
24 Correct 16 ms 78588 KB Output is correct
25 Correct 17 ms 78352 KB Output is correct
26 Correct 21 ms 78428 KB Output is correct
27 Correct 17 ms 78424 KB Output is correct
28 Correct 16 ms 78428 KB Output is correct
29 Correct 16 ms 78440 KB Output is correct
30 Correct 16 ms 78428 KB Output is correct
31 Correct 2236 ms 132760 KB Output is correct
32 Correct 321 ms 82884 KB Output is correct
33 Correct 792 ms 95564 KB Output is correct
34 Correct 1971 ms 106052 KB Output is correct
35 Correct 1740 ms 124200 KB Output is correct
36 Correct 896 ms 106492 KB Output is correct
37 Correct 629 ms 88124 KB Output is correct
38 Correct 475 ms 87204 KB Output is correct
39 Correct 464 ms 86764 KB Output is correct
40 Correct 441 ms 86744 KB Output is correct
41 Correct 694 ms 87084 KB Output is correct
42 Correct 720 ms 87044 KB Output is correct
43 Correct 220 ms 86624 KB Output is correct
44 Correct 673 ms 87012 KB Output is correct
45 Correct 581 ms 86964 KB Output is correct
46 Correct 507 ms 87344 KB Output is correct
47 Correct 371 ms 86524 KB Output is correct
48 Correct 366 ms 86808 KB Output is correct
49 Correct 440 ms 86792 KB Output is correct
50 Correct 575 ms 86900 KB Output is correct
51 Correct 436 ms 86788 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1061 ms 360268 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1275 ms 354776 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 78424 KB Output is correct
2 Correct 14 ms 78172 KB Output is correct
3 Correct 14 ms 78396 KB Output is correct
4 Correct 14 ms 78428 KB Output is correct
5 Correct 16 ms 78424 KB Output is correct
6 Correct 18 ms 78428 KB Output is correct
7 Correct 16 ms 78428 KB Output is correct
8 Correct 17 ms 78684 KB Output is correct
9 Correct 16 ms 78684 KB Output is correct
10 Correct 17 ms 78412 KB Output is correct
11 Correct 16 ms 78428 KB Output is correct
12 Correct 16 ms 78296 KB Output is correct
13 Correct 18 ms 78424 KB Output is correct
14 Correct 16 ms 78428 KB Output is correct
15 Correct 17 ms 78428 KB Output is correct
16 Correct 16 ms 78380 KB Output is correct
17 Correct 17 ms 78428 KB Output is correct
18 Correct 17 ms 78428 KB Output is correct
19 Correct 17 ms 78428 KB Output is correct
20 Correct 16 ms 78352 KB Output is correct
21 Correct 16 ms 78428 KB Output is correct
22 Correct 16 ms 78680 KB Output is correct
23 Correct 17 ms 78428 KB Output is correct
24 Correct 16 ms 78588 KB Output is correct
25 Correct 17 ms 78352 KB Output is correct
26 Correct 21 ms 78428 KB Output is correct
27 Correct 17 ms 78424 KB Output is correct
28 Correct 16 ms 78428 KB Output is correct
29 Correct 16 ms 78440 KB Output is correct
30 Correct 16 ms 78428 KB Output is correct
31 Correct 2236 ms 132760 KB Output is correct
32 Correct 321 ms 82884 KB Output is correct
33 Correct 792 ms 95564 KB Output is correct
34 Correct 1971 ms 106052 KB Output is correct
35 Correct 1740 ms 124200 KB Output is correct
36 Correct 896 ms 106492 KB Output is correct
37 Correct 629 ms 88124 KB Output is correct
38 Correct 475 ms 87204 KB Output is correct
39 Correct 464 ms 86764 KB Output is correct
40 Correct 441 ms 86744 KB Output is correct
41 Correct 694 ms 87084 KB Output is correct
42 Correct 720 ms 87044 KB Output is correct
43 Correct 220 ms 86624 KB Output is correct
44 Correct 673 ms 87012 KB Output is correct
45 Correct 581 ms 86964 KB Output is correct
46 Correct 507 ms 87344 KB Output is correct
47 Correct 371 ms 86524 KB Output is correct
48 Correct 366 ms 86808 KB Output is correct
49 Correct 440 ms 86792 KB Output is correct
50 Correct 575 ms 86900 KB Output is correct
51 Correct 436 ms 86788 KB Output is correct
52 Correct 914 ms 141656 KB Output is correct
53 Correct 786 ms 111608 KB Output is correct
54 Correct 2096 ms 153220 KB Output is correct
55 Correct 907 ms 105256 KB Output is correct
56 Correct 891 ms 117456 KB Output is correct
57 Correct 817 ms 95240 KB Output is correct
58 Correct 964 ms 108372 KB Output is correct
59 Correct 983 ms 117516 KB Output is correct
60 Correct 839 ms 95332 KB Output is correct
61 Correct 243 ms 97388 KB Output is correct
62 Correct 852 ms 144884 KB Output is correct
63 Correct 1679 ms 142476 KB Output is correct
64 Correct 1882 ms 133192 KB Output is correct
65 Correct 1499 ms 103864 KB Output is correct
66 Correct 789 ms 90364 KB Output is correct
67 Correct 1212 ms 97048 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 78424 KB Output is correct
2 Correct 14 ms 78172 KB Output is correct
3 Correct 14 ms 78396 KB Output is correct
4 Correct 14 ms 78428 KB Output is correct
5 Correct 16 ms 78424 KB Output is correct
6 Correct 18 ms 78428 KB Output is correct
7 Correct 16 ms 78428 KB Output is correct
8 Correct 17 ms 78684 KB Output is correct
9 Correct 16 ms 78684 KB Output is correct
10 Correct 17 ms 78412 KB Output is correct
11 Correct 16 ms 78428 KB Output is correct
12 Correct 16 ms 78296 KB Output is correct
13 Correct 18 ms 78424 KB Output is correct
14 Correct 16 ms 78428 KB Output is correct
15 Correct 17 ms 78428 KB Output is correct
16 Correct 16 ms 78380 KB Output is correct
17 Correct 17 ms 78428 KB Output is correct
18 Correct 17 ms 78428 KB Output is correct
19 Correct 17 ms 78428 KB Output is correct
20 Correct 16 ms 78352 KB Output is correct
21 Correct 16 ms 78428 KB Output is correct
22 Correct 16 ms 78680 KB Output is correct
23 Correct 17 ms 78428 KB Output is correct
24 Correct 16 ms 78588 KB Output is correct
25 Correct 17 ms 78352 KB Output is correct
26 Correct 21 ms 78428 KB Output is correct
27 Correct 17 ms 78424 KB Output is correct
28 Correct 16 ms 78428 KB Output is correct
29 Correct 16 ms 78440 KB Output is correct
30 Correct 16 ms 78428 KB Output is correct
31 Correct 2236 ms 132760 KB Output is correct
32 Correct 321 ms 82884 KB Output is correct
33 Correct 792 ms 95564 KB Output is correct
34 Correct 1971 ms 106052 KB Output is correct
35 Correct 1740 ms 124200 KB Output is correct
36 Correct 896 ms 106492 KB Output is correct
37 Correct 629 ms 88124 KB Output is correct
38 Correct 475 ms 87204 KB Output is correct
39 Correct 464 ms 86764 KB Output is correct
40 Correct 441 ms 86744 KB Output is correct
41 Correct 694 ms 87084 KB Output is correct
42 Correct 720 ms 87044 KB Output is correct
43 Correct 220 ms 86624 KB Output is correct
44 Correct 673 ms 87012 KB Output is correct
45 Correct 581 ms 86964 KB Output is correct
46 Correct 507 ms 87344 KB Output is correct
47 Correct 371 ms 86524 KB Output is correct
48 Correct 366 ms 86808 KB Output is correct
49 Correct 440 ms 86792 KB Output is correct
50 Correct 575 ms 86900 KB Output is correct
51 Correct 436 ms 86788 KB Output is correct
52 Runtime error 1061 ms 360268 KB Execution killed with signal 11
53 Halted 0 ms 0 KB -