oj.uz

Submission #735238

# Submission time Handle Problem Language Result Execution time Memory
735238 2023-05-03T18:17:54 Z socpite New Home (APIO18_new_home) C++14
47 / 100
 5000 ms 435692 KB 
#include<bits/stdc++.h>
using namespace std;

#define f first 
#define s second

typedef long long ll;

const int inf = 1e8+5;
const int maxn = 3e5+5;

vector<int> posq;
int n, K, q;

int X[maxn], T[maxn], A[maxn], B[maxn], L[maxn], Y[maxn], ans[maxn], td[maxn][2];

int etype[maxn];

int tot;

set<pair<int, int>> lmao[maxn];
priority_queue<pair<int, pair<int, int>>> st[4*maxn][2];

void _add(int l, int r, int ql, int qr, pair<int, int> k, int ty, int id){
    //cout << ql << " " << qr << " " << ty << endl;
    if(ql > qr)return;
    if(l > qr || ql > r)return;
    else if(ql <= l && r <= qr){
        //cout << "a " << id << " " << ty << endl;
        if(!ty)st[id][ty].push({-k.f, {k.s, td[k.s][ty]}});
        else st[id][ty].push({k.f, {k.s, td[k.s][ty]}});
    }
    else {
        int mid = (l+r)>>1;
        _add(l, mid, ql, qr, k, ty, id<<1);
        _add(mid+1, r, ql, qr, k, ty, id<<1|1);
    }
}

int _query(int l, int r, int k, int id){
    //cout << l << " " << r << " " << id << endl;
    if(tot != K)return -1;
    int re = 0;
    while(!st[id][0].empty()){
        auto x = st[id][0].top();
        if(td[x.s.f][0] != x.s.s)st[id][0].pop();
        else break;
    }
    while(!st[id][1].empty()){
        auto x = st[id][1].top();
        if(td[x.s.f][1] != x.s.s)st[id][1].pop();
        else break;
    }
    if(!st[id][0].empty())re = max(re, posq[k] + st[id][0].top().f);
    if(!st[id][1].empty())re = max(re, st[id][1].top().f - posq[k]);
    if(l == r)return re;
    int mid = (l+r)>>1;
    if(k <= mid)re = max(re, _query(l, mid, k, id<<1));
    else re = max(re, _query(mid+1, r, k, id<<1|1));
    return re;
}

int query(int id){
    return _query(0, posq.size()-1, lower_bound(posq.begin(), posq.end(), L[id]) - posq.begin(), 1);    
}

void add(int ql, int qr, pair<int, int> k, int ty){
    _add(0, posq.size()-1, lower_bound(posq.begin(), posq.end(), ql) - posq.begin(), upper_bound(posq.begin(), posq.end(), qr) - posq.begin()-1, k, ty, 1);
}


void s_add(set<pair<int, int>>::iterator it, int ty){
    int id = it->s;
    if(ty == 0){
        if(next(it) == lmao[T[id]].end())add(X[id]+1, inf, {X[id], id}, 0);
        else add(X[id]+1, (next(it)->f+X[id])/2, {X[id], id}, 0);
    }
    else{
        if(it == lmao[T[id]].begin())add(0, X[id], {X[id], id}, 1);
        else add((prev(it)->f + X[id])/2+1, X[id], {X[id], id}, 1);
    }
}

void s_rmv(set<pair<int, int>>::iterator it, int ty){
    int id = it->s;
    td[id][ty]++;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> K >> q;
    vector<pair<int, pair<int, int>>> ev;
    for(int i = 0; i < n; i++){
        cin >> X[i] >> T[i] >> A[i] >> B[i];
        ev.push_back({A[i], {0, i}});
        ev.push_back({B[i]+1, {1, i}});
    }
    for(int i = 0; i < q; i++){
        cin >> L[i] >> Y[i];
        ev.push_back({Y[i], {2, i}});
        posq.push_back(L[i]);
    }
    sort(posq.begin(), posq.end());
    posq.erase(unique(posq.begin(), posq.end()), posq.end());
    sort(ev.begin(), ev.end());
    for(auto v: ev){
        //cout << v.s.f << " " << v.s.s << endl;
        int id = v.s.s;
        if(v.s.f == 0){
            auto it = lmao[T[id]].lower_bound({X[id], id});
            if(it != lmao[T[id]].end())s_rmv(it, 1);
            if(it != lmao[T[id]].begin())s_rmv(prev(it), 0);
            it = lmao[T[id]].insert({X[id], id}).f;
            s_add(it, 0);
            s_add(it, 1);
            if(it != lmao[T[id]].begin())s_add(prev(it), 0);
            if(next(it) != lmao[T[id]].end())s_add(next(it), 1);
            tot += (etype[T[id]]++)==0;
        }
        else if(v.s.f == 1){
            auto it = lmao[T[id]].find({X[id], id});
            assert(it != lmao[T[id]].end());
            s_rmv(it, 0);
            s_rmv(it, 1);
            if(it != lmao[T[id]].begin())s_rmv(prev(it), 0);
            if(next(it) != lmao[T[id]].end())s_rmv(next(it), 1);
            lmao[T[id]].erase(it);
            it = lmao[T[id]].lower_bound({X[id], id});
            if(it != lmao[T[id]].end())s_add(it, 1);
            if(it != lmao[T[id]].begin())s_add(prev(it), 0);
            tot -= (--etype[T[id]])==0;
        }
        else ans[id] = query(id);
    }
    for(int i = 0; i < q; i++)cout << ans[i] << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 89552 KB Output is correct
2 Correct 44 ms 89492 KB Output is correct
3 Correct 42 ms 89544 KB Output is correct
4 Correct 48 ms 89548 KB Output is correct
5 Correct 47 ms 89628 KB Output is correct
6 Correct 42 ms 89676 KB Output is correct
7 Correct 49 ms 89592 KB Output is correct
8 Correct 49 ms 89708 KB Output is correct
9 Correct 43 ms 89612 KB Output is correct
10 Correct 43 ms 89812 KB Output is correct
11 Correct 43 ms 89664 KB Output is correct
12 Correct 45 ms 89688 KB Output is correct
13 Correct 42 ms 89608 KB Output is correct
14 Correct 42 ms 89680 KB Output is correct
15 Correct 44 ms 89808 KB Output is correct
16 Correct 45 ms 89752 KB Output is correct
17 Correct 42 ms 89840 KB Output is correct
18 Correct 44 ms 89724 KB Output is correct
19 Correct 50 ms 89636 KB Output is correct
20 Correct 44 ms 89696 KB Output is correct
21 Correct 42 ms 89672 KB Output is correct
22 Correct 41 ms 89688 KB Output is correct
23 Correct 48 ms 89752 KB Output is correct
24 Correct 42 ms 89676 KB Output is correct
25 Correct 42 ms 89720 KB Output is correct
26 Correct 48 ms 89676 KB Output is correct
27 Correct 46 ms 89676 KB Output is correct
28 Correct 42 ms 89640 KB Output is correct
29 Correct 43 ms 89700 KB Output is correct
30 Correct 43 ms 89676 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 89552 KB Output is correct
2 Correct 44 ms 89492 KB Output is correct
3 Correct 42 ms 89544 KB Output is correct
4 Correct 48 ms 89548 KB Output is correct
5 Correct 47 ms 89628 KB Output is correct
6 Correct 42 ms 89676 KB Output is correct
7 Correct 49 ms 89592 KB Output is correct
8 Correct 49 ms 89708 KB Output is correct
9 Correct 43 ms 89612 KB Output is correct
10 Correct 43 ms 89812 KB Output is correct
11 Correct 43 ms 89664 KB Output is correct
12 Correct 45 ms 89688 KB Output is correct
13 Correct 42 ms 89608 KB Output is correct
14 Correct 42 ms 89680 KB Output is correct
15 Correct 44 ms 89808 KB Output is correct
16 Correct 45 ms 89752 KB Output is correct
17 Correct 42 ms 89840 KB Output is correct
18 Correct 44 ms 89724 KB Output is correct
19 Correct 50 ms 89636 KB Output is correct
20 Correct 44 ms 89696 KB Output is correct
21 Correct 42 ms 89672 KB Output is correct
22 Correct 41 ms 89688 KB Output is correct
23 Correct 48 ms 89752 KB Output is correct
24 Correct 42 ms 89676 KB Output is correct
25 Correct 42 ms 89720 KB Output is correct
26 Correct 48 ms 89676 KB Output is correct
27 Correct 46 ms 89676 KB Output is correct
28 Correct 42 ms 89640 KB Output is correct
29 Correct 43 ms 89700 KB Output is correct
30 Correct 43 ms 89676 KB Output is correct
31 Correct 1086 ms 143444 KB Output is correct
32 Correct 161 ms 96168 KB Output is correct
33 Correct 746 ms 118084 KB Output is correct
34 Correct 1083 ms 142796 KB Output is correct
35 Correct 1006 ms 134832 KB Output is correct
36 Correct 733 ms 117428 KB Output is correct
37 Correct 614 ms 120436 KB Output is correct
38 Correct 420 ms 110176 KB Output is correct
39 Correct 410 ms 112196 KB Output is correct
40 Correct 361 ms 109884 KB Output is correct
41 Correct 755 ms 113984 KB Output is correct
42 Correct 704 ms 121356 KB Output is correct
43 Correct 113 ms 97992 KB Output is correct
44 Correct 760 ms 113504 KB Output is correct
45 Correct 809 ms 109088 KB Output is correct
46 Correct 621 ms 107644 KB Output is correct
47 Correct 281 ms 112524 KB Output is correct
48 Correct 262 ms 111576 KB Output is correct
49 Correct 331 ms 115376 KB Output is correct
50 Correct 391 ms 123048 KB Output is correct
51 Correct 377 ms 113432 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4678 ms 386136 KB Output is correct
2 Correct 4230 ms 240216 KB Output is correct
3 Correct 1742 ms 238860 KB Output is correct
4 Correct 4267 ms 358728 KB Output is correct
5 Correct 2815 ms 170216 KB Output is correct
6 Correct 3736 ms 215820 KB Output is correct
7 Correct 1799 ms 238676 KB Output is correct
8 Correct 3394 ms 349120 KB Output is correct
9 Correct 4888 ms 435692 KB Output is correct
10 Execution timed out 5086 ms 374096 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 89552 KB Output is correct
2 Correct 44 ms 89492 KB Output is correct
3 Correct 42 ms 89544 KB Output is correct
4 Correct 48 ms 89548 KB Output is correct
5 Correct 47 ms 89628 KB Output is correct
6 Correct 42 ms 89676 KB Output is correct
7 Correct 49 ms 89592 KB Output is correct
8 Correct 49 ms 89708 KB Output is correct
9 Correct 43 ms 89612 KB Output is correct
10 Correct 43 ms 89812 KB Output is correct
11 Correct 43 ms 89664 KB Output is correct
12 Correct 45 ms 89688 KB Output is correct
13 Correct 42 ms 89608 KB Output is correct
14 Correct 42 ms 89680 KB Output is correct
15 Correct 44 ms 89808 KB Output is correct
16 Correct 45 ms 89752 KB Output is correct
17 Correct 42 ms 89840 KB Output is correct
18 Correct 44 ms 89724 KB Output is correct
19 Correct 50 ms 89636 KB Output is correct
20 Correct 44 ms 89696 KB Output is correct
21 Correct 42 ms 89672 KB Output is correct
22 Correct 41 ms 89688 KB Output is correct
23 Correct 48 ms 89752 KB Output is correct
24 Correct 42 ms 89676 KB Output is correct
25 Correct 42 ms 89720 KB Output is correct
26 Correct 48 ms 89676 KB Output is correct
27 Correct 46 ms 89676 KB Output is correct
28 Correct 42 ms 89640 KB Output is correct
29 Correct 43 ms 89700 KB Output is correct
30 Correct 43 ms 89676 KB Output is correct
31 Correct 1086 ms 143444 KB Output is correct
32 Correct 161 ms 96168 KB Output is correct
33 Correct 746 ms 118084 KB Output is correct
34 Correct 1083 ms 142796 KB Output is correct
35 Correct 1006 ms 134832 KB Output is correct
36 Correct 733 ms 117428 KB Output is correct
37 Correct 614 ms 120436 KB Output is correct
38 Correct 420 ms 110176 KB Output is correct
39 Correct 410 ms 112196 KB Output is correct
40 Correct 361 ms 109884 KB Output is correct
41 Correct 755 ms 113984 KB Output is correct
42 Correct 704 ms 121356 KB Output is correct
43 Correct 113 ms 97992 KB Output is correct
44 Correct 760 ms 113504 KB Output is correct
45 Correct 809 ms 109088 KB Output is correct
46 Correct 621 ms 107644 KB Output is correct
47 Correct 281 ms 112524 KB Output is correct
48 Correct 262 ms 111576 KB Output is correct
49 Correct 331 ms 115376 KB Output is correct
50 Correct 391 ms 123048 KB Output is correct
51 Correct 377 ms 113432 KB Output is correct
52 Correct 284 ms 112444 KB Output is correct
53 Correct 293 ms 112332 KB Output is correct
54 Correct 633 ms 137088 KB Output is correct
55 Correct 552 ms 119288 KB Output is correct
56 Correct 480 ms 118568 KB Output is correct
57 Correct 722 ms 119872 KB Output is correct
58 Correct 531 ms 122032 KB Output is correct
59 Correct 456 ms 121216 KB Output is correct
60 Correct 621 ms 123828 KB Output is correct
61 Correct 105 ms 100428 KB Output is correct
62 Correct 282 ms 114188 KB Output is correct
63 Correct 483 ms 127372 KB Output is correct
64 Correct 556 ms 131660 KB Output is correct
65 Correct 701 ms 134104 KB Output is correct
66 Correct 714 ms 120544 KB Output is correct
67 Correct 182 ms 107680 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 89552 KB Output is correct
2 Correct 44 ms 89492 KB Output is correct
3 Correct 42 ms 89544 KB Output is correct
4 Correct 48 ms 89548 KB Output is correct
5 Correct 47 ms 89628 KB Output is correct
6 Correct 42 ms 89676 KB Output is correct
7 Correct 49 ms 89592 KB Output is correct
8 Correct 49 ms 89708 KB Output is correct
9 Correct 43 ms 89612 KB Output is correct
10 Correct 43 ms 89812 KB Output is correct
11 Correct 43 ms 89664 KB Output is correct
12 Correct 45 ms 89688 KB Output is correct
13 Correct 42 ms 89608 KB Output is correct
14 Correct 42 ms 89680 KB Output is correct
15 Correct 44 ms 89808 KB Output is correct
16 Correct 45 ms 89752 KB Output is correct
17 Correct 42 ms 89840 KB Output is correct
18 Correct 44 ms 89724 KB Output is correct
19 Correct 50 ms 89636 KB Output is correct
20 Correct 44 ms 89696 KB Output is correct
21 Correct 42 ms 89672 KB Output is correct
22 Correct 41 ms 89688 KB Output is correct
23 Correct 48 ms 89752 KB Output is correct
24 Correct 42 ms 89676 KB Output is correct
25 Correct 42 ms 89720 KB Output is correct
26 Correct 48 ms 89676 KB Output is correct
27 Correct 46 ms 89676 KB Output is correct
28 Correct 42 ms 89640 KB Output is correct
29 Correct 43 ms 89700 KB Output is correct
30 Correct 43 ms 89676 KB Output is correct
31 Correct 1086 ms 143444 KB Output is correct
32 Correct 161 ms 96168 KB Output is correct
33 Correct 746 ms 118084 KB Output is correct
34 Correct 1083 ms 142796 KB Output is correct
35 Correct 1006 ms 134832 KB Output is correct
36 Correct 733 ms 117428 KB Output is correct
37 Correct 614 ms 120436 KB Output is correct
38 Correct 420 ms 110176 KB Output is correct
39 Correct 410 ms 112196 KB Output is correct
40 Correct 361 ms 109884 KB Output is correct
41 Correct 755 ms 113984 KB Output is correct
42 Correct 704 ms 121356 KB Output is correct
43 Correct 113 ms 97992 KB Output is correct
44 Correct 760 ms 113504 KB Output is correct
45 Correct 809 ms 109088 KB Output is correct
46 Correct 621 ms 107644 KB Output is correct
47 Correct 281 ms 112524 KB Output is correct
48 Correct 262 ms 111576 KB Output is correct
49 Correct 331 ms 115376 KB Output is correct
50 Correct 391 ms 123048 KB Output is correct
51 Correct 377 ms 113432 KB Output is correct
52 Correct 4678 ms 386136 KB Output is correct
53 Correct 4230 ms 240216 KB Output is correct
54 Correct 1742 ms 238860 KB Output is correct
55 Correct 4267 ms 358728 KB Output is correct
56 Correct 2815 ms 170216 KB Output is correct
57 Correct 3736 ms 215820 KB Output is correct
58 Correct 1799 ms 238676 KB Output is correct
59 Correct 3394 ms 349120 KB Output is correct
60 Correct 4888 ms 435692 KB Output is correct
61 Execution timed out 5086 ms 374096 KB Time limit exceeded
62 Halted 0 ms 0 KB -