Submission #968897

#	Time	Username	Problem	Language	Result	Execution time	Memory
968897		socpite	New Home (APIO18_new_home)	C++17	100 / 100	4669 ms	705464 KiB

new_home

// #pragma GCC optimize("arch=skylake")
#include<bits/stdc++.h>
using namespace std;

const int maxn = 6e5+5;
const int INF = 1e9+5;

vector<pair<int, pair<int, int>>> ev;
vector<int> cp, cpy;
int n, q, k;

int ans[maxn];
int p[maxn], ty[maxn];
int L[maxn], Y[maxn];

int st[4*maxn][2];

struct ev_upd{
    int l, r, val, ty;
    ev_upd(int _l, int _r, int _val, int _ty): l(_l), r(_r), ty(_ty), val(_val){};
};

vector<pair<int, int>> leaf_q[maxn];  
set<pair<int, int>> pos[maxn];
int last_time[maxn][2];


vector<ev_upd> st_time[4*maxn];

int crrt;

long long undo_stack[maxn*200];
int stksz = 0;

// 0 is min, 1 is max

void upd_st(int l, int r, int val, int ty, int &cnt){
    if(l > r)return;
    r++;
    for (l += cp.size(), r += cp.size(); l < r; l >>= 1, r >>= 1){
        if(l&1){
            int id = l++;
            if(ty == 0){
                if(st[id][0] > val){
                    undo_stack[stksz++] = ((long long)id<<30)|st[id][0];
                    // cout << undo_stack[stksz-1] << endl;
                    st[id][0] = val;  
                    cnt++;
                }
            }
            else {
                if(st[id][1] < val){
                    undo_stack[stksz++] = (1LL<<60)|(((long long)id<<30)|st[id][1]);
                    // cout << undo_stack[stksz-1] << endl;
                    st[id][1] = val;
                    cnt++;
                }
            }
        }
        if(r&1){
            int id = --r;
            if(ty == 0){
                if(st[id][0] > val){
                    undo_stack[stksz++] = ((long long)id<<30)|st[id][0];
                    // cout << undo_stack[stksz-1] << endl;
                    st[id][0] = val;  
                    cnt++;
                }
            }
            else {
                if(st[id][1] < val){
                    undo_stack[stksz++] = (1LL<<60)|(((long long)id<<30)|st[id][1]);
                    // cout << undo_stack[stksz-1] << endl;
                    st[id][1] = val;
                    cnt++;
                }
            }
        }
    }
}

int query_st(int p){
    int tmp = cp[p];
    int res = 0;
    for (p += cp.size(); p > 0; p >>= 1){
        res = max(res, tmp - st[p][0]);
        res = max(res, st[p][1] - tmp);
    }
    return res;
}

int cnt_segment;

void time_add(int ql, int qr, const ev_upd &ele, int l = 0, int r = cpy.size()-1, int id = 1){
    // cout << ql << " " << qr << " " << ele.l << " " << ele.r << " " << ele.ty << endl;  
    if(ql > qr || ql > cpy[r] || qr < cpy[l])return;
    if(ql <= cpy[l] && cpy[r] <= qr){
        st_time[id].push_back(ele);
        cnt_segment++;
    }
    else {
        int mid = (l+r)>>1;
        time_add(ql, qr, ele, l, mid, id<<1);
        time_add(ql, qr, ele, mid+1, r, id<<1|1);
    }
}

int sumcol[maxn];
int sumall = 0, ptr = 0;

void time_dfs(int l = 0, int r = cpy.size()-1, int id = 1){
    int cnt = 0;
    for(auto &ele: st_time[id])  {
        upd_st(ele.l, ele.r, ele.val, ele.ty, cnt);
    }
    if(l == r){
        while(ptr < ev.size() && ev[ptr].first <= cpy[l]){
            if(ev[ptr].second.first){
                sumcol[ty[ev[ptr].second.second]]--;
                if(!sumcol[ty[ev[ptr].second.second]])sumall--;
            }
            else {
                if(!sumcol[ty[ev[ptr].second.second]])sumall++;
                sumcol[ty[ev[ptr].second.second]]++;
            }
            ptr++;
        }
        // cout << sumall << endl;
        for(auto qq: leaf_q[l]){
            ans[qq.second] = sumall < k ? -1 : query_st(qq.first);
        }
    }
    else {
        int mid = (l+r)>>1;
        time_dfs(l, mid, id<<1);
        time_dfs(mid+1, r, id<<1|1);
    }
    for(int i = 0; i < cnt; i++){
        stksz--;
        long long tmp = undo_stack[stksz];
        // cout << tmp << " " << ((tmp&((1LL<<60) - 1)) >> 30) << endl; 
        st[(tmp&((1LL<<60) - 1)) >> 30][tmp>>60] = tmp&((1<<30) - 1); 
    }
}


void add_range(int l, int r){
    if(l != -INF)last_time[l][0] = crrt;
    if(r != INF)last_time[r][1] = crrt;
}

int lb(int x){
    return lower_bound(cp.begin(), cp.end(), x) - cp.begin();
}

int ub(int x){
    return upper_bound(cp.begin(), cp.end(), x) - cp.begin() - 1;
}

void del_range(int l, int r){
    // return;
    if(l == -INF){
        ev_upd ele(lb(-INF), ub(p[r]), p[r], 1);
        time_add(last_time[r][1], crrt-1, ele);
        last_time[r][1] = 0;
    }
    else if(r == INF){
        time_add(last_time[l][0], crrt-1, ev_upd(lb(p[l]), ub(INF), p[l], 0));
        last_time[l][0] = 0;
    }
    else {
        int mid = (p[l]+p[r])/2;
        time_add(last_time[l][0], crrt-1, ev_upd(lb(p[l]), ub(mid), p[l], 0));
        time_add(last_time[r][1], crrt-1, ev_upd(lb(mid+1), ub(p[r]), p[r], 1));
        last_time[r][1] = 0;
        last_time[l][0] = 0;
    }
}

void add(int x, int col){
    // cout << x << endl;
    auto it = pos[col].insert(make_pair(p[x], x)).first;
    if(pos[col].size() == 1){
        add_range(-INF, x);
        add_range(x, INF);
    }
    else {
        if(next(it) == pos[col].end()){
            int prv = prev(it)->second;
            del_range(prv, INF);
            add_range(prv, x);
            add_range(x, INF);
        }
        else if(it == pos[col].begin()){
            int nxt = next(it)->second;
            del_range(-INF, nxt);
            add_range(-INF, x);
            add_range(x, nxt);
        }
        else {
            int prv = prev(it)->second;
            int nxt = next(it)->second;
            del_range(prv, nxt);
            add_range(prv, x);
            add_range(x, nxt);
        }
    }
}

void del(int x, int col){
    // cout << "DEL " << x << endl;
    auto it = pos[col].erase(pos[col].find(make_pair(p[x], x)));
    if(pos[col].size() == 0){
        del_range(-INF, x);
        del_range(x, INF);
    }
    else {
        if(it == pos[col].end()){
            int prv = prev(it)->second;
            del_range(x, INF);
            del_range(prv, x);
            add_range(prv, INF);
        }
        else if(it == pos[col].begin()){
            int nxt = it->second;
            del_range(-INF, x);
            del_range(x, nxt);
            add_range(-INF, nxt);
        }
        else {
            int prv = prev(it)->second;
            int nxt = it->second;
            del_range(x, nxt);
            del_range(prv, x);
            add_range(prv, nxt);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    auto t1 = clock();
    // freopen("test_input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    cin >> n >> k >> q;
    for(int i = 0; i < 4*maxn; i++)st[i][0] = INF, st[i][1] = 0;
    for(int i = 1; i <= n; i++){
        int a, b;
        cin >> p[i] >> ty[i] >> a >> b;
        ev.push_back({a, {0, i}});
        ev.push_back({b+1, {1, i}});
    }
    for(int i = 1; i <= q; i++){
        cin >> L[i] >> Y[i];
        cp.push_back(L[i]);
        cpy.push_back(Y[i]);
    }
    sort(cp.begin(), cp.end());
    cp.erase(unique(cp.begin(), cp.end()), cp.end());
    sort(cpy.begin(), cpy.end());
    cpy.erase(unique(cpy.begin(), cpy.end()), cpy.end()); 
    sort(ev.begin(), ev.end());
    for(int i = 1; i <= q; i++)leaf_q[lower_bound(cpy.begin(), cpy.end(), Y[i]) - cpy.begin()].push_back({lb(L[i]), i});
    for(auto v: ev){
        crrt = v.first;
        if(v.second.first)del(v.second.second, ty[v.second.second]);
        else add(v.second.second, ty[v.second.second]);
    }
    // cout << "SUS" << endl;  
    // if(n > 100000)return 0;
    // cout << cnt_segment << endl;
    // return 0;
    time_dfs();
    // cout << clock() - t1 << endl;
    for(int i = 1; i <= q; i++)cout << ans[i] << "\n";
    
}

Compilation message (stderr)

new_home.cpp: In constructor 'ev_upd::ev_upd(int, int, int, int)':
new_home.cpp:19:20: warning: 'ev_upd::ty' will be initialized after [-Wreorder]
   19 |     int l, r, val, ty;
      |                    ^~
new_home.cpp:19:15: warning:   'int ev_upd::val' [-Wreorder]
   19 |     int l, r, val, ty;
      |               ^~~
new_home.cpp:20:5: warning:   when initialized here [-Wreorder]
   20 |     ev_upd(int _l, int _r, int _val, int _ty): l(_l), r(_r), ty(_ty), val(_val){};
      |     ^~~~~~
new_home.cpp: In function 'void time_dfs(int, int, int)':
new_home.cpp:117:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         while(ptr < ev.size() && ev[ptr].first <= cpy[l]){
      |               ~~~~^~~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:243:10: warning: unused variable 't1' [-Wunused-variable]
  243 |     auto t1 = clock();
      |          ^~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20