Submission #1028534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028534		vjudge1	New Home (APIO18_new_home)	C++17	57 / 100	5047 ms	301612 KiB

new_home

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(3)
int ans[300100];
multiset<int>stor[300100];
map<int,int>importpos;
struct segtree{
    stack<pair<int,int>>stk;
    int vl[1<<20];
    segtree(){for(auto&i:vl)i=-1e9;}
    void update(int i,int l,int r,int ll,int rr,int v){
        if(l>rr||ll>r)return;
        if(ll<=l&&r<=rr) return stk.push({i,vl[i]}),void(vl[i]=max(vl[i],v));
        update(i*2,l,l+r>>1,ll,rr,v);
        update(i*2+1,l+r+2>>1,r,ll,rr,v);
    }
    int query(int i,int l,int r,int p){
        if(l==r) return vl[i];
        if(l+r>>1<p)
            return max(vl[i],query(i*2+1,l+r+2>>1,r,p));
        return max(vl[i],query(i*2,l,l+r>>1,p));
    }
    void upd(int l,int r,int v){
        update(1,1,importpos.size(),importpos.lower_bound(l)->second,
            (--importpos.upper_bound(r))->second,v);
    }
    int qry(int p) {
        return query(1,1,importpos.size(),importpos[p]);
    }
    void reroll(int k){
        while(stk.size()>k){
            auto[a,b]=stk.top();
            stk.pop();
            vl[a]=b;
        }
    }
} seg1,seg2;
vector<pair<int,int>>todie[1<<20],qrys[300100];
void a_range(int l,int r){
    seg1.upd(l,l+r>>1,-l);
    seg2.upd(l+r+2>>1,r,r);
}
map<int,vector<pair<int,int>>>qr;
map<int,int>compr;
void splatonto(int i,int l,int r,int ll,int rr,pair<int,int>vl){
    if(ll<=l&&r<=rr)
        return todie[i].push_back(vl);
    if(ll>r||l>rr) return;
    splatonto(i*2,l,l+r>>1,ll,rr,vl);
    splatonto(i*2+1,l+r+2>>1,r,ll,rr,vl);
}
int depth=0;
void solve(int i,int ll,int rr){
    if(ll>rr)return;
    int sz1=seg1.stk.size(),sz2=seg2.stk.size();
    for(auto[p,t]:todie[i]) {
        stor[t].erase(stor[t].find(p));
        if(stor[t].find(p)==stor[t].end())
            a_range(*--stor[t].lower_bound(p),*stor[t].lower_bound(p));
    }
    if(ll==rr){
        for(auto[p,i]:qrys[ll])
            ans[i]=max(seg1.qry(p)+p,seg2.qry(p)-p);
    } else {
        solve(i*2,ll,ll+rr>>1);
        solve(i*2+1,ll+rr+2>>1,rr);
    }
    for(auto[p,t]:todie[i])
        stor[t].insert(p);
    seg1.reroll(sz1),seg2.reroll(sz2);
}
vector<array<int,4>> stores;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    importpos[-1e9]=0;
    int n,k,q;
    cin>>n>>k>>q;
    for(int i=0;i<n;i++){
        int l,r,a,b;
        cin>>a>>b>>l>>r;
        stor[b].insert(a);
        stores.push_back({a,b,l,r});
    }
    for(int i=1;i<=k;i++)
        stor[i].insert(-1e9),stor[i].insert(1e9);
    for(int i=0;i<q;i++){
        int x,y; cin>>x>>y;
        qr[y].push_back({x,i});
        compr[y];
        importpos[x];
    }
    int CDCC=0,CDC=0;
    for(auto&[i,j]:importpos)
        j=++CDC;
    importpos[1e9]=CDC+1;
    for(auto&[i,j]:compr)
        j=++CDCC;
    for(auto[k,x]:qr){
        int ind=compr[k];
        for(auto[p,i]:x)
            qrys[ind].push_back({p,i});
    }
    compr[-1e9]=0;
    compr[1e9]=CDCC+1;
    for(auto[pos,t,l,r]:stores){
        int k=(--compr.lower_bound(l))->second;
        splatonto(1,1,CDCC,1,k,{pos,t});
        k=compr.upper_bound(r)->second;
        splatonto(1,1,CDCC,k,CDCC,{pos,t});
    }
    for(int i=1;i<=k;i++){
        auto it=++stor[i].begin();
        while(it!=stor[i].end()){
            a_range(*prev(it),*it);
            it++;
        }
    }
    solve(1,1,CDCC);
    for(int i=0;i<q;i++)
        cout<<(ans[i]>1e8?-1:ans[i])<<'\n';
}

Compilation message (stderr)

new_home.cpp: In member function 'void segtree::update(int, int, int, int, int, int)':
new_home.cpp:14:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |         update(i*2,l,l+r>>1,ll,rr,v);
      |                      ~^~
new_home.cpp:15:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |         update(i*2+1,l+r+2>>1,r,ll,rr,v);
      |                      ~~~^~
new_home.cpp: In member function 'int segtree::query(int, int, int, int)':
new_home.cpp:19:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |         if(l+r>>1<p)
      |            ~^~
new_home.cpp:20:45: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |             return max(vl[i],query(i*2+1,l+r+2>>1,r,p));
      |                                          ~~~^~
new_home.cpp:21:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         return max(vl[i],query(i*2,l,l+r>>1,p));
      |                                      ~^~
new_home.cpp: In member function 'void segtree::reroll(int)':
new_home.cpp:31:25: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |         while(stk.size()>k){
      |               ~~~~~~~~~~^~
new_home.cpp: In function 'void a_range(int, int)':
new_home.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     seg1.upd(l,l+r>>1,-l);
      |                ~^~
new_home.cpp:41:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |     seg2.upd(l+r+2>>1,r,r);
      |              ~~~^~
new_home.cpp: In function 'void splatonto(int, int, int, int, int, std::pair<int, int>)':
new_home.cpp:49:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |     splatonto(i*2,l,l+r>>1,ll,rr,vl);
      |                     ~^~
new_home.cpp:50:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     splatonto(i*2+1,l+r+2>>1,r,ll,rr,vl);
      |                     ~~~^~
new_home.cpp: In function 'void solve(int, int, int)':
new_home.cpp:65:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |         solve(i*2,ll,ll+rr>>1);
      |                      ~~^~~
new_home.cpp:66:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |         solve(i*2+1,ll+rr+2>>1,rr);
      |                     ~~~~~^~

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