oj.uz

Submission #864618

# Submission time Handle Problem Language Result Execution time Memory
864618 2023-10-23T10:42:06 Z danikoynov New Home (APIO18_new_home) C++14
47 / 100
 5000 ms 725844 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

const int maxn = 6e5 + 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
}


struct node
{
    priority_queue < int > lf_act, lf_rem;
    priority_queue < int > rf_act, rf_rem;
};

node tree[4 * maxn];

void apply_update(int root, pair < int, int > val)
{
    if (val.first == -1)
    {
        tree[root].lf_rem.push(-val.second);
        tree[root].rf_rem.push(val.second);
        ///tree[root].erase(tree[root].find(val.second));
    }
    else
    {
        tree[root].lf_act.push(-val.second);
        tree[root].rf_act.push(val.second);
        ///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;
    while(!tree[root].rf_rem.empty() && 
        tree[root].rf_act.top() == tree[root].rf_rem.top())
    {
         tree[root].rf_act.pop();
         tree[root].rf_rem.pop();
    }
        while(!tree[root].lf_rem.empty() &&
        tree[root].lf_act.top() == tree[root].lf_rem.top())
    {
         tree[root].lf_act.pop();
         tree[root].lf_rem.pop();
    }
    if (!tree[root].rf_act.empty())
    {
        far = max(far, tree[root].rf_act.top() - cor);
        far = max(far, cor + tree[root].lf_act.top());
    }
    
    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();
}

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int main()
{
    speed();
    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:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int i = 0; i < cor.size(); i ++)
      |                     ~~^~~~~~~~~~~~
new_home.cpp:60:9: warning: unused variable 'sz' [-Wunused-variable]
   60 |     int sz = cor.size();
      |         ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 336724 KB Output is correct
2 Correct 61 ms 336976 KB Output is correct
3 Correct 60 ms 336936 KB Output is correct
4 Correct 60 ms 336872 KB Output is correct
5 Correct 62 ms 337176 KB Output is correct
6 Correct 65 ms 337236 KB Output is correct
7 Correct 63 ms 337120 KB Output is correct
8 Correct 64 ms 337232 KB Output is correct
9 Correct 72 ms 337248 KB Output is correct
10 Correct 64 ms 337120 KB Output is correct
11 Correct 62 ms 337228 KB Output is correct
12 Correct 69 ms 337188 KB Output is correct
13 Correct 63 ms 337176 KB Output is correct
14 Correct 63 ms 336976 KB Output is correct
15 Correct 64 ms 337264 KB Output is correct
16 Correct 65 ms 337232 KB Output is correct
17 Correct 69 ms 337300 KB Output is correct
18 Correct 65 ms 337280 KB Output is correct
19 Correct 69 ms 337104 KB Output is correct
20 Correct 67 ms 337116 KB Output is correct
21 Correct 67 ms 337068 KB Output is correct
22 Correct 64 ms 337244 KB Output is correct
23 Correct 67 ms 337276 KB Output is correct
24 Correct 64 ms 337268 KB Output is correct
25 Correct 66 ms 337064 KB Output is correct
26 Correct 68 ms 337236 KB Output is correct
27 Correct 65 ms 337216 KB Output is correct
28 Correct 65 ms 337136 KB Output is correct
29 Correct 65 ms 337100 KB Output is correct
30 Correct 67 ms 337184 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 336724 KB Output is correct
2 Correct 61 ms 336976 KB Output is correct
3 Correct 60 ms 336936 KB Output is correct
4 Correct 60 ms 336872 KB Output is correct
5 Correct 62 ms 337176 KB Output is correct
6 Correct 65 ms 337236 KB Output is correct
7 Correct 63 ms 337120 KB Output is correct
8 Correct 64 ms 337232 KB Output is correct
9 Correct 72 ms 337248 KB Output is correct
10 Correct 64 ms 337120 KB Output is correct
11 Correct 62 ms 337228 KB Output is correct
12 Correct 69 ms 337188 KB Output is correct
13 Correct 63 ms 337176 KB Output is correct
14 Correct 63 ms 336976 KB Output is correct
15 Correct 64 ms 337264 KB Output is correct
16 Correct 65 ms 337232 KB Output is correct
17 Correct 69 ms 337300 KB Output is correct
18 Correct 65 ms 337280 KB Output is correct
19 Correct 69 ms 337104 KB Output is correct
20 Correct 67 ms 337116 KB Output is correct
21 Correct 67 ms 337068 KB Output is correct
22 Correct 64 ms 337244 KB Output is correct
23 Correct 67 ms 337276 KB Output is correct
24 Correct 64 ms 337268 KB Output is correct
25 Correct 66 ms 337064 KB Output is correct
26 Correct 68 ms 337236 KB Output is correct
27 Correct 65 ms 337216 KB Output is correct
28 Correct 65 ms 337136 KB Output is correct
29 Correct 65 ms 337100 KB Output is correct
30 Correct 67 ms 337184 KB Output is correct
31 Correct 2168 ms 431504 KB Output is correct
32 Correct 258 ms 368216 KB Output is correct
33 Correct 1417 ms 398256 KB Output is correct
34 Correct 2206 ms 434952 KB Output is correct
35 Correct 1881 ms 420920 KB Output is correct
36 Correct 1383 ms 398292 KB Output is correct
37 Correct 1061 ms 404520 KB Output is correct
38 Correct 677 ms 389632 KB Output is correct
39 Correct 609 ms 392096 KB Output is correct
40 Correct 582 ms 389192 KB Output is correct
41 Correct 1515 ms 394756 KB Output is correct
42 Correct 1508 ms 398184 KB Output is correct
43 Correct 130 ms 350492 KB Output is correct
44 Correct 1388 ms 393880 KB Output is correct
45 Correct 1305 ms 386428 KB Output is correct
46 Correct 948 ms 383240 KB Output is correct
47 Correct 510 ms 388008 KB Output is correct
48 Correct 532 ms 387648 KB Output is correct
49 Correct 658 ms 391444 KB Output is correct
50 Correct 776 ms 401976 KB Output is correct
51 Correct 672 ms 386580 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5114 ms 725844 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 5110 ms 707920 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 336724 KB Output is correct
2 Correct 61 ms 336976 KB Output is correct
3 Correct 60 ms 336936 KB Output is correct
4 Correct 60 ms 336872 KB Output is correct
5 Correct 62 ms 337176 KB Output is correct
6 Correct 65 ms 337236 KB Output is correct
7 Correct 63 ms 337120 KB Output is correct
8 Correct 64 ms 337232 KB Output is correct
9 Correct 72 ms 337248 KB Output is correct
10 Correct 64 ms 337120 KB Output is correct
11 Correct 62 ms 337228 KB Output is correct
12 Correct 69 ms 337188 KB Output is correct
13 Correct 63 ms 337176 KB Output is correct
14 Correct 63 ms 336976 KB Output is correct
15 Correct 64 ms 337264 KB Output is correct
16 Correct 65 ms 337232 KB Output is correct
17 Correct 69 ms 337300 KB Output is correct
18 Correct 65 ms 337280 KB Output is correct
19 Correct 69 ms 337104 KB Output is correct
20 Correct 67 ms 337116 KB Output is correct
21 Correct 67 ms 337068 KB Output is correct
22 Correct 64 ms 337244 KB Output is correct
23 Correct 67 ms 337276 KB Output is correct
24 Correct 64 ms 337268 KB Output is correct
25 Correct 66 ms 337064 KB Output is correct
26 Correct 68 ms 337236 KB Output is correct
27 Correct 65 ms 337216 KB Output is correct
28 Correct 65 ms 337136 KB Output is correct
29 Correct 65 ms 337100 KB Output is correct
30 Correct 67 ms 337184 KB Output is correct
31 Correct 2168 ms 431504 KB Output is correct
32 Correct 258 ms 368216 KB Output is correct
33 Correct 1417 ms 398256 KB Output is correct
34 Correct 2206 ms 434952 KB Output is correct
35 Correct 1881 ms 420920 KB Output is correct
36 Correct 1383 ms 398292 KB Output is correct
37 Correct 1061 ms 404520 KB Output is correct
38 Correct 677 ms 389632 KB Output is correct
39 Correct 609 ms 392096 KB Output is correct
40 Correct 582 ms 389192 KB Output is correct
41 Correct 1515 ms 394756 KB Output is correct
42 Correct 1508 ms 398184 KB Output is correct
43 Correct 130 ms 350492 KB Output is correct
44 Correct 1388 ms 393880 KB Output is correct
45 Correct 1305 ms 386428 KB Output is correct
46 Correct 948 ms 383240 KB Output is correct
47 Correct 510 ms 388008 KB Output is correct
48 Correct 532 ms 387648 KB Output is correct
49 Correct 658 ms 391444 KB Output is correct
50 Correct 776 ms 401976 KB Output is correct
51 Correct 672 ms 386580 KB Output is correct
52 Correct 684 ms 390560 KB Output is correct
53 Correct 662 ms 389596 KB Output is correct
54 Correct 1470 ms 416520 KB Output is correct
55 Correct 1147 ms 399648 KB Output is correct
56 Correct 998 ms 399028 KB Output is correct
57 Correct 1389 ms 400476 KB Output is correct
58 Correct 1229 ms 400612 KB Output is correct
59 Correct 1073 ms 399108 KB Output is correct
60 Correct 1531 ms 402012 KB Output is correct
61 Correct 134 ms 356720 KB Output is correct
62 Correct 671 ms 390900 KB Output is correct
63 Correct 1185 ms 405708 KB Output is correct
64 Correct 1412 ms 412360 KB Output is correct
65 Correct 1709 ms 415988 KB Output is correct
66 Correct 1636 ms 402328 KB Output is correct
67 Correct 587 ms 403344 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 336724 KB Output is correct
2 Correct 61 ms 336976 KB Output is correct
3 Correct 60 ms 336936 KB Output is correct
4 Correct 60 ms 336872 KB Output is correct
5 Correct 62 ms 337176 KB Output is correct
6 Correct 65 ms 337236 KB Output is correct
7 Correct 63 ms 337120 KB Output is correct
8 Correct 64 ms 337232 KB Output is correct
9 Correct 72 ms 337248 KB Output is correct
10 Correct 64 ms 337120 KB Output is correct
11 Correct 62 ms 337228 KB Output is correct
12 Correct 69 ms 337188 KB Output is correct
13 Correct 63 ms 337176 KB Output is correct
14 Correct 63 ms 336976 KB Output is correct
15 Correct 64 ms 337264 KB Output is correct
16 Correct 65 ms 337232 KB Output is correct
17 Correct 69 ms 337300 KB Output is correct
18 Correct 65 ms 337280 KB Output is correct
19 Correct 69 ms 337104 KB Output is correct
20 Correct 67 ms 337116 KB Output is correct
21 Correct 67 ms 337068 KB Output is correct
22 Correct 64 ms 337244 KB Output is correct
23 Correct 67 ms 337276 KB Output is correct
24 Correct 64 ms 337268 KB Output is correct
25 Correct 66 ms 337064 KB Output is correct
26 Correct 68 ms 337236 KB Output is correct
27 Correct 65 ms 337216 KB Output is correct
28 Correct 65 ms 337136 KB Output is correct
29 Correct 65 ms 337100 KB Output is correct
30 Correct 67 ms 337184 KB Output is correct
31 Correct 2168 ms 431504 KB Output is correct
32 Correct 258 ms 368216 KB Output is correct
33 Correct 1417 ms 398256 KB Output is correct
34 Correct 2206 ms 434952 KB Output is correct
35 Correct 1881 ms 420920 KB Output is correct
36 Correct 1383 ms 398292 KB Output is correct
37 Correct 1061 ms 404520 KB Output is correct
38 Correct 677 ms 389632 KB Output is correct
39 Correct 609 ms 392096 KB Output is correct
40 Correct 582 ms 389192 KB Output is correct
41 Correct 1515 ms 394756 KB Output is correct
42 Correct 1508 ms 398184 KB Output is correct
43 Correct 130 ms 350492 KB Output is correct
44 Correct 1388 ms 393880 KB Output is correct
45 Correct 1305 ms 386428 KB Output is correct
46 Correct 948 ms 383240 KB Output is correct
47 Correct 510 ms 388008 KB Output is correct
48 Correct 532 ms 387648 KB Output is correct
49 Correct 658 ms 391444 KB Output is correct
50 Correct 776 ms 401976 KB Output is correct
51 Correct 672 ms 386580 KB Output is correct
52 Execution timed out 5114 ms 725844 KB Time limit exceeded
53 Halted 0 ms 0 KB -