oj.uz

Submission #563030

# Submission time Handle Problem Language Result Execution time Memory
563030 2022-05-16T05:55:12 Z Bill_00 New Home (APIO18_new_home) C++14
5 / 100
 5000 ms 37556 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define N 300005 
typedef long long ll;

using namespace std;

ll n, k, q, ans[N];
struct stores{
    ll x, t, a, b;
};

struct query{
    ll l, y;
};

stores s[N];
query Q[N];

struct node{
    ll cnt;
    node *le, *ri;
    void update(ll l, ll r, ll pos, ll val){
        if(l == r){
            cnt += val;
            return;
        }
        ll m = l + r >> 1;
        if(m >= pos){
            if(le == NULL) le = new node();
            le -> update(l, m, pos, val);
            if(le -> cnt == 0){
                le = NULL;
                delete(le);
            }
        }
        else{
            if(ri == NULL) ri = new node();
            ri -> update(m + 1, r, pos, val);
            if(ri -> cnt == 0){
                ri = NULL;
                delete(ri);
            }
        }
        cnt = 0;
        if(le != NULL) cnt += le -> cnt;
        if(ri != NULL) cnt += ri -> cnt;
    }
    ll query(ll l, ll r, ll pos){
        if(l == r){
            return cnt;
        }
        ll m = l + r >> 1;
        if(pos > m){
            ll sup = 0;
            if(le != NULL) sup = le -> cnt;
            if(ri == NULL) return sup;
            return sup + ri -> query(m + 1, r, pos);
        }
        else{
            if(le == NULL) return 0;
            return le -> query(l, m, pos);
        }
    }
    ll search(ll l, ll r, ll val){
        if(l == r) return l;
        ll m = l + r >> 1;
        if(le == NULL){
            if(val == 0) return -1e18;
            if(ri == NULL) return 1e18;
            else{
                return ri -> search(m + 1, r, val);
            }
        }
        else{
            if(val <= le -> cnt){
                return le -> search(l, m, val);
            }
            else{
                if(ri == NULL) return 1e18;
                else{
                    return ri -> search(m + 1, r, val - le -> cnt);
                }
            }
        }
    }
} *root[404];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k >> q;
    for(ll i = 1; i <= n; i++){
        cin >> s[i].x >> s[i].t >> s[i].a >> s[i].b;
    }
    for(ll i = 1; i <= q; i++){
        cin >> Q[i].l >> Q[i].y;
    }
    if(k <= 400){
        vector<pair<ll, pair<ll, ll> > > v;
        for(ll i = 1; i <= n; i++){
            v.push_back({s[i].a, {-1, i}});
            v.push_back({s[i].b, {1, i}});
        }
        for(ll i = 1; i <= q; i++){
            v.push_back({Q[i].y, {0, i}});
        }
        sort(v.begin(), v.end());
        for(pair<ll, pair<ll, ll> > poll : v){
            ll id = poll.ss.ss;
            if(poll.ss.ff == -1){
                if(root[s[id].t] == NULL) root[s[id].t] = new node();
                root[s[id].t] -> update(1, 100000000, s[id].x, 1);
            }
            if(poll.ss.ff == 1){
                root[s[id].t] -> update(1, 100000000, s[id].x, -1);
                if(root[s[id].t] -> cnt == 0){
                    root[s[id].t] = NULL;
                    delete(root[s[id].t]);
                }
            }
            if(poll.ss.ff == 0){
                bool flag = 0;
                for(ll i = 1; i <= k; i++){
                    if(root[i] == NULL){
                        ans[id] = -1;
                        flag = 1;
                        break;
                    }
                }
                if(flag == 0){
                    ll lol = 0;
                    ll pos = Q[id].l;
                    for(ll i = 1; i <= k; i++){
                        ll many = root[i] -> query(1, 100000000, pos);
                        ll X = root[i] -> search(1, 100000000, many);
                        ll Y = root[i] -> search(1, 100000000, many + 1);
                        lol = max(lol, min(pos - X, Y - pos));
                    }
                    ans[id] = lol;
                }
            }
        }
        for(int i = 1; i <= q; i++){
            cout << ans[i] << '\n';
        }
    }
}

Compilation message

new_home.cpp: In member function 'void node::update(ll, ll, ll, ll)':
new_home.cpp:29:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         ll m = l + r >> 1;
      |                ~~^~~
new_home.cpp: In member function 'll node::query(ll, ll, ll)':
new_home.cpp:54:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         ll m = l + r >> 1;
      |                ~~^~~
new_home.cpp: In member function 'll node::search(ll, ll, ll)':
new_home.cpp:68:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |         ll m = l + r >> 1;
      |                ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 8 ms 724 KB Output is correct
16 Correct 11 ms 724 KB Output is correct
17 Correct 4 ms 724 KB Output is correct
18 Correct 7 ms 740 KB Output is correct
19 Correct 8 ms 736 KB Output is correct
20 Correct 4 ms 724 KB Output is correct
21 Correct 9 ms 724 KB Output is correct
22 Correct 11 ms 768 KB Output is correct
23 Correct 7 ms 636 KB Output is correct
24 Correct 8 ms 724 KB Output is correct
25 Correct 4 ms 724 KB Output is correct
26 Correct 2 ms 724 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 2 ms 596 KB Output is correct
30 Correct 1 ms 596 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 8 ms 724 KB Output is correct
16 Correct 11 ms 724 KB Output is correct
17 Correct 4 ms 724 KB Output is correct
18 Correct 7 ms 740 KB Output is correct
19 Correct 8 ms 736 KB Output is correct
20 Correct 4 ms 724 KB Output is correct
21 Correct 9 ms 724 KB Output is correct
22 Correct 11 ms 768 KB Output is correct
23 Correct 7 ms 636 KB Output is correct
24 Correct 8 ms 724 KB Output is correct
25 Correct 4 ms 724 KB Output is correct
26 Correct 2 ms 724 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 2 ms 596 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Execution timed out 5033 ms 37556 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 27916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 155 ms 27328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 8 ms 724 KB Output is correct
16 Correct 11 ms 724 KB Output is correct
17 Correct 4 ms 724 KB Output is correct
18 Correct 7 ms 740 KB Output is correct
19 Correct 8 ms 736 KB Output is correct
20 Correct 4 ms 724 KB Output is correct
21 Correct 9 ms 724 KB Output is correct
22 Correct 11 ms 768 KB Output is correct
23 Correct 7 ms 636 KB Output is correct
24 Correct 8 ms 724 KB Output is correct
25 Correct 4 ms 724 KB Output is correct
26 Correct 2 ms 724 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 2 ms 596 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Execution timed out 5033 ms 37556 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 8 ms 724 KB Output is correct
16 Correct 11 ms 724 KB Output is correct
17 Correct 4 ms 724 KB Output is correct
18 Correct 7 ms 740 KB Output is correct
19 Correct 8 ms 736 KB Output is correct
20 Correct 4 ms 724 KB Output is correct
21 Correct 9 ms 724 KB Output is correct
22 Correct 11 ms 768 KB Output is correct
23 Correct 7 ms 636 KB Output is correct
24 Correct 8 ms 724 KB Output is correct
25 Correct 4 ms 724 KB Output is correct
26 Correct 2 ms 724 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 2 ms 596 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Execution timed out 5033 ms 37556 KB Time limit exceeded
32 Halted 0 ms 0 KB -