Submission #563030

#	Time	Username	Problem	Language	Result	Execution time	Memory
563030		Bill_00	New Home (APIO18_new_home)	C++14	5 / 100	5033 ms	37556 KiB

new_home

#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 (stderr)

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 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20