Submission #1028518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028518		vjudge1	New Home (APIO18_new_home)	C++17	0 / 100	823 ms	1048576 KiB

new_home

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int ans[60100];
multiset<int>stor[60100];
set<int>importantyears;
struct segtree{
    stack<pair<int,int>>stk;
    int rt,CC;
    int lc[1<<21],rc[1<<21],vl[1<<21];
    segtree(){rt=CC=0;for(auto&i:vl)i=-2e9;}
    void update(int &i,int l,int r,int ll,int rr,int v){
        if(l>r) return;
        if(ll>rr)return;
        if(l>rr||ll>r)return;
        if(!i) i=++CC;
        if(ll<=l&&r<=rr) return stk.push({i,vl[i]}),void(vl[i]=max(vl[i],v));
        update(lc[i],l,l+r>>1,ll,rr,v);
        update(rc[i],l+r+2>>1,r,ll,rr,v);
    }
    int query(int i,int l,int r,int p){
        if(!i) return -2e9;
        if(l+r>>1<p)
            return max(vl[i],query(rc[i],l+r+2>>1,r,p));
        return max(vl[i],query(lc[i],l,l+r>>1,p));
    }
    void upd(int l,int r,int v){
        update(rt,1,1e8,l,r,v);
    }
    int qry(int p) {
        return query(rt,1,1e8,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<<18],qrys[60010];
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>rr) return;
    if(l>r) return;
    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){
    depth++;
    if(depth>1000) exit(0);
    if(ll>rr)return;
    int CC1=seg1.CC,CC2=seg2.CC;
    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);
    seg1.CC=CC1,seg2.CC=CC2;
    depth--;
}
vector<array<int,4>> stores;
int main(){
    cerr<<sizeof seg1;
    cin.tie(0)->sync_with_stdio(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;
        importantyears.insert(y);
        qr[y].push_back({x,i});
        compr[y];
    }
    int CDCC=0;
    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[0]=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:18:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |         update(lc[i],l,l+r>>1,ll,rr,v);
      |                        ~^~
new_home.cpp:19:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |         update(rc[i],l+r+2>>1,r,ll,rr,v);
      |                      ~~~^~
new_home.cpp: In member function 'int segtree::query(int, int, int, int)':
new_home.cpp:23:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |         if(l+r>>1<p)
      |            ~^~
new_home.cpp:24:45: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |             return max(vl[i],query(rc[i],l+r+2>>1,r,p));
      |                                          ~~~^~
new_home.cpp:25:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |         return max(vl[i],query(lc[i],l,l+r>>1,p));
      |                                        ~^~
new_home.cpp: In member function 'void segtree::reroll(int)':
new_home.cpp:34: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]
   34 |         while(stk.size()>k){
      |               ~~~~~~~~~~^~
new_home.cpp: In function 'void a_range(int, int)':
new_home.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     seg1.upd(l,l+r>>1,-l);
      |                ~^~
new_home.cpp:44:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     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:54:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     splatonto(i*2,l,l+r>>1,ll,rr,vl);
      |                     ~^~
new_home.cpp:55:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     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:73:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |         solve(i*2,ll,ll+rr>>1);
      |                      ~~^~~
new_home.cpp:74:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         solve(i*2+1,ll+rr+2>>1,rr);
      |                     ~~~~~^~

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