oj.uz

Submission #735227

# Submission time Handle Problem Language Result Execution time Memory
735227 2023-05-03T18:06:49 Z socpite New Home (APIO18_new_home) C++14
47 / 100
 5000 ms 382736 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];

int etype[maxn];

int tot;

set<pair<int, int>> lmao[maxn];
set<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;
        st[id][ty].insert(k);
    }
    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);
    }
}

void _rmv(int l, int r, int ql, int qr, pair<int, int> k, int ty, int id){
    //cout << l << " " << r << " " << id << endl;
    if(ql > qr)return;
    if(l > qr || ql > r)return;
    else if(ql <= l && r <= qr)assert(st[id][ty].erase(k));
    else {
        int mid = (l+r)>>1;
        _rmv(l, mid, ql, qr, k, ty, id<<1);
        _rmv(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;
    if(!st[id][0].empty())re = max(re, posq[k] - st[id][0].begin()->f);
    if(!st[id][1].empty())re = max(re, st[id][1].rbegin()->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 rmv(int ql, int qr, pair<int, int> k, int ty){
    _rmv(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;
    if(ty == 0){
        if(next(it) == lmao[T[id]].end())rmv(X[id]+1, inf, {X[id], id}, 0);
        else rmv(X[id]+1, (next(it)->f+X[id])/2, {X[id], id}, 0);
    }
    else{
        if(it == lmao[T[id]].begin())rmv(0, X[id], {X[id], id}, 1);
        else rmv((prev(it)->f + X[id])/2+1, X[id], {X[id], id}, 1);
    }
}

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 54 ms 127056 KB Output is correct
2 Correct 54 ms 127128 KB Output is correct
3 Correct 56 ms 127064 KB Output is correct
4 Correct 56 ms 127048 KB Output is correct
5 Correct 57 ms 127184 KB Output is correct
6 Correct 55 ms 127200 KB Output is correct
7 Correct 56 ms 127392 KB Output is correct
8 Correct 59 ms 127308 KB Output is correct
9 Correct 63 ms 127372 KB Output is correct
10 Correct 57 ms 127316 KB Output is correct
11 Correct 59 ms 127356 KB Output is correct
12 Correct 58 ms 127312 KB Output is correct
13 Correct 68 ms 127204 KB Output is correct
14 Correct 61 ms 127192 KB Output is correct
15 Correct 67 ms 127256 KB Output is correct
16 Correct 60 ms 127300 KB Output is correct
17 Correct 57 ms 127216 KB Output is correct
18 Correct 59 ms 127292 KB Output is correct
19 Correct 60 ms 127264 KB Output is correct
20 Correct 59 ms 127284 KB Output is correct
21 Correct 55 ms 127132 KB Output is correct
22 Correct 59 ms 127312 KB Output is correct
23 Correct 58 ms 127320 KB Output is correct
24 Correct 58 ms 127240 KB Output is correct
25 Correct 58 ms 127276 KB Output is correct
26 Correct 59 ms 127128 KB Output is correct
27 Correct 55 ms 127180 KB Output is correct
28 Correct 59 ms 127128 KB Output is correct
29 Correct 59 ms 127168 KB Output is correct
30 Correct 60 ms 127228 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 127056 KB Output is correct
2 Correct 54 ms 127128 KB Output is correct
3 Correct 56 ms 127064 KB Output is correct
4 Correct 56 ms 127048 KB Output is correct
5 Correct 57 ms 127184 KB Output is correct
6 Correct 55 ms 127200 KB Output is correct
7 Correct 56 ms 127392 KB Output is correct
8 Correct 59 ms 127308 KB Output is correct
9 Correct 63 ms 127372 KB Output is correct
10 Correct 57 ms 127316 KB Output is correct
11 Correct 59 ms 127356 KB Output is correct
12 Correct 58 ms 127312 KB Output is correct
13 Correct 68 ms 127204 KB Output is correct
14 Correct 61 ms 127192 KB Output is correct
15 Correct 67 ms 127256 KB Output is correct
16 Correct 60 ms 127300 KB Output is correct
17 Correct 57 ms 127216 KB Output is correct
18 Correct 59 ms 127292 KB Output is correct
19 Correct 60 ms 127264 KB Output is correct
20 Correct 59 ms 127284 KB Output is correct
21 Correct 55 ms 127132 KB Output is correct
22 Correct 59 ms 127312 KB Output is correct
23 Correct 58 ms 127320 KB Output is correct
24 Correct 58 ms 127240 KB Output is correct
25 Correct 58 ms 127276 KB Output is correct
26 Correct 59 ms 127128 KB Output is correct
27 Correct 55 ms 127180 KB Output is correct
28 Correct 59 ms 127128 KB Output is correct
29 Correct 59 ms 127168 KB Output is correct
30 Correct 60 ms 127228 KB Output is correct
31 Correct 2514 ms 173224 KB Output is correct
32 Correct 182 ms 133556 KB Output is correct
33 Correct 896 ms 142036 KB Output is correct
34 Correct 2324 ms 152488 KB Output is correct
35 Correct 1873 ms 167072 KB Output is correct
36 Correct 929 ms 149092 KB Output is correct
37 Correct 691 ms 136340 KB Output is correct
38 Correct 508 ms 135344 KB Output is correct
39 Correct 451 ms 134660 KB Output is correct
40 Correct 442 ms 134604 KB Output is correct
41 Correct 781 ms 135132 KB Output is correct
42 Correct 819 ms 135212 KB Output is correct
43 Correct 139 ms 136840 KB Output is correct
44 Correct 779 ms 135044 KB Output is correct
45 Correct 657 ms 134832 KB Output is correct
46 Correct 529 ms 134808 KB Output is correct
47 Correct 356 ms 134280 KB Output is correct
48 Correct 311 ms 134364 KB Output is correct
49 Correct 438 ms 134524 KB Output is correct
50 Correct 592 ms 134788 KB Output is correct
51 Correct 439 ms 134480 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5036 ms 382736 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 5019 ms 309452 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 127056 KB Output is correct
2 Correct 54 ms 127128 KB Output is correct
3 Correct 56 ms 127064 KB Output is correct
4 Correct 56 ms 127048 KB Output is correct
5 Correct 57 ms 127184 KB Output is correct
6 Correct 55 ms 127200 KB Output is correct
7 Correct 56 ms 127392 KB Output is correct
8 Correct 59 ms 127308 KB Output is correct
9 Correct 63 ms 127372 KB Output is correct
10 Correct 57 ms 127316 KB Output is correct
11 Correct 59 ms 127356 KB Output is correct
12 Correct 58 ms 127312 KB Output is correct
13 Correct 68 ms 127204 KB Output is correct
14 Correct 61 ms 127192 KB Output is correct
15 Correct 67 ms 127256 KB Output is correct
16 Correct 60 ms 127300 KB Output is correct
17 Correct 57 ms 127216 KB Output is correct
18 Correct 59 ms 127292 KB Output is correct
19 Correct 60 ms 127264 KB Output is correct
20 Correct 59 ms 127284 KB Output is correct
21 Correct 55 ms 127132 KB Output is correct
22 Correct 59 ms 127312 KB Output is correct
23 Correct 58 ms 127320 KB Output is correct
24 Correct 58 ms 127240 KB Output is correct
25 Correct 58 ms 127276 KB Output is correct
26 Correct 59 ms 127128 KB Output is correct
27 Correct 55 ms 127180 KB Output is correct
28 Correct 59 ms 127128 KB Output is correct
29 Correct 59 ms 127168 KB Output is correct
30 Correct 60 ms 127228 KB Output is correct
31 Correct 2514 ms 173224 KB Output is correct
32 Correct 182 ms 133556 KB Output is correct
33 Correct 896 ms 142036 KB Output is correct
34 Correct 2324 ms 152488 KB Output is correct
35 Correct 1873 ms 167072 KB Output is correct
36 Correct 929 ms 149092 KB Output is correct
37 Correct 691 ms 136340 KB Output is correct
38 Correct 508 ms 135344 KB Output is correct
39 Correct 451 ms 134660 KB Output is correct
40 Correct 442 ms 134604 KB Output is correct
41 Correct 781 ms 135132 KB Output is correct
42 Correct 819 ms 135212 KB Output is correct
43 Correct 139 ms 136840 KB Output is correct
44 Correct 779 ms 135044 KB Output is correct
45 Correct 657 ms 134832 KB Output is correct
46 Correct 529 ms 134808 KB Output is correct
47 Correct 356 ms 134280 KB Output is correct
48 Correct 311 ms 134364 KB Output is correct
49 Correct 438 ms 134524 KB Output is correct
50 Correct 592 ms 134788 KB Output is correct
51 Correct 439 ms 134480 KB Output is correct
52 Correct 750 ms 182252 KB Output is correct
53 Correct 703 ms 152276 KB Output is correct
54 Correct 2062 ms 195516 KB Output is correct
55 Correct 854 ms 151108 KB Output is correct
56 Correct 828 ms 158996 KB Output is correct
57 Correct 892 ms 139960 KB Output is correct
58 Correct 1044 ms 151192 KB Output is correct
59 Correct 968 ms 159156 KB Output is correct
60 Correct 986 ms 140060 KB Output is correct
61 Correct 132 ms 140040 KB Output is correct
62 Correct 712 ms 182336 KB Output is correct
63 Correct 1593 ms 182212 KB Output is correct
64 Correct 1961 ms 174240 KB Output is correct
65 Correct 1954 ms 148040 KB Output is correct
66 Correct 934 ms 135892 KB Output is correct
67 Correct 559 ms 136992 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 127056 KB Output is correct
2 Correct 54 ms 127128 KB Output is correct
3 Correct 56 ms 127064 KB Output is correct
4 Correct 56 ms 127048 KB Output is correct
5 Correct 57 ms 127184 KB Output is correct
6 Correct 55 ms 127200 KB Output is correct
7 Correct 56 ms 127392 KB Output is correct
8 Correct 59 ms 127308 KB Output is correct
9 Correct 63 ms 127372 KB Output is correct
10 Correct 57 ms 127316 KB Output is correct
11 Correct 59 ms 127356 KB Output is correct
12 Correct 58 ms 127312 KB Output is correct
13 Correct 68 ms 127204 KB Output is correct
14 Correct 61 ms 127192 KB Output is correct
15 Correct 67 ms 127256 KB Output is correct
16 Correct 60 ms 127300 KB Output is correct
17 Correct 57 ms 127216 KB Output is correct
18 Correct 59 ms 127292 KB Output is correct
19 Correct 60 ms 127264 KB Output is correct
20 Correct 59 ms 127284 KB Output is correct
21 Correct 55 ms 127132 KB Output is correct
22 Correct 59 ms 127312 KB Output is correct
23 Correct 58 ms 127320 KB Output is correct
24 Correct 58 ms 127240 KB Output is correct
25 Correct 58 ms 127276 KB Output is correct
26 Correct 59 ms 127128 KB Output is correct
27 Correct 55 ms 127180 KB Output is correct
28 Correct 59 ms 127128 KB Output is correct
29 Correct 59 ms 127168 KB Output is correct
30 Correct 60 ms 127228 KB Output is correct
31 Correct 2514 ms 173224 KB Output is correct
32 Correct 182 ms 133556 KB Output is correct
33 Correct 896 ms 142036 KB Output is correct
34 Correct 2324 ms 152488 KB Output is correct
35 Correct 1873 ms 167072 KB Output is correct
36 Correct 929 ms 149092 KB Output is correct
37 Correct 691 ms 136340 KB Output is correct
38 Correct 508 ms 135344 KB Output is correct
39 Correct 451 ms 134660 KB Output is correct
40 Correct 442 ms 134604 KB Output is correct
41 Correct 781 ms 135132 KB Output is correct
42 Correct 819 ms 135212 KB Output is correct
43 Correct 139 ms 136840 KB Output is correct
44 Correct 779 ms 135044 KB Output is correct
45 Correct 657 ms 134832 KB Output is correct
46 Correct 529 ms 134808 KB Output is correct
47 Correct 356 ms 134280 KB Output is correct
48 Correct 311 ms 134364 KB Output is correct
49 Correct 438 ms 134524 KB Output is correct
50 Correct 592 ms 134788 KB Output is correct
51 Correct 439 ms 134480 KB Output is correct
52 Execution timed out 5036 ms 382736 KB Time limit exceeded
53 Halted 0 ms 0 KB -