Submission #735251

#	Time	Username	Problem	Language	Result	Execution time	Memory
735251		socpite	New Home (APIO18_new_home)	C++14	0 / 100	5115 ms	794820 KiB

new_home

#pragma GCC optimize("Ofast")
#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 pc[inf];

int lb(int x){return pc[x-1];}
int ub(int x){return pc[x];}

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, lb(L[id]), 1);    
}
 
void add(int ql, int qr, pair<int, int> k, int ty){
    _add(0, posq.size()-1, lb(ql), ub(qr)-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(1, 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());
    for(auto v: posq)pc[v]++;
    for(int i = 1; i < inf; i++)pc[i]+=pc[i-1];
    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";
}

Compilation message (stderr)

new_home.cpp: In function 'void s_add(std::set<std::pair<int, int> >::iterator, int)':
new_home.cpp:20:26: warning: array subscript 100000005 is above array bounds of 'int [100000005]' [-Warray-bounds]
   20 | int ub(int x){return pc[x];}
      |                      ~~~~^
new_home.cpp:17:5: note: while referencing 'pc'
   17 | int pc[inf];
      |     ^~
new_home.cpp: In function 'void s_add(std::set<std::pair<int, int> >::iterator, int)':
new_home.cpp:20:26: warning: array subscript 100000005 is above array bounds of 'int [100000005]' [-Warray-bounds]
   20 | int ub(int x){return pc[x];}
      |                      ~~~~^
new_home.cpp:17:5: note: while referencing 'pc'
   17 | int pc[inf];
      |     ^~

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