oj.uz

Submission #1028522

# Submission time Handle Problem Language Result Execution time Memory
1028522 2024-07-20T03:20:29 Z vjudge1 New Home (APIO18_new_home) C++17
0 / 100
 911 ms 525748 KB 
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define int long long
int ans[60100];
multiset<int>stor[60100];
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=-1e18;}
    void update(int &i,int l,int r,int ll,int rr,int v){
        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;
        }
    }
    void reroll2(int CC2){
        if(!CC2) rt=0;
        for(int i=CC2+1;i<=CC;i++)
            lc[i]=0,rc[i]=0,vl[i]=-1e18;
        CC=CC2;
    }
} 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<=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 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.reroll2(CC1),seg2.reroll2(CC2);
}
vector<array<int,4>> stores;
signed 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;
        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

new_home.cpp: In member function 'void segtree::update(long long int&, long long int, long long int, long long int, long long int, long long int)':
new_home.cpp:16:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |         update(lc[i],l,l+r>>1,ll,rr,v);
      |                        ~^~
new_home.cpp:17:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |         update(rc[i],l+r+2>>1,r,ll,rr,v);
      |                      ~~~^~
new_home.cpp: In member function 'long long int segtree::query(long long int, long long int, long long int, long long int)':
new_home.cpp:21:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         if(l+r>>1<p)
      |            ~^~
new_home.cpp:22:45: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |             return max(vl[i],query(rc[i],l+r+2>>1,r,p));
      |                                          ~~~^~
new_home.cpp:23:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |         return max(vl[i],query(lc[i],l,l+r>>1,p));
      |                                        ~^~
new_home.cpp: In member function 'void segtree::reroll(long long int)':
new_home.cpp:32:25: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   32 |         while(stk.size()>k){
      |               ~~~~~~~~~~^~
new_home.cpp: In function 'void a_range(long long int, long long int)':
new_home.cpp:47:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     seg1.upd(l,l+r>>1,-l);
      |                ~^~
new_home.cpp:48:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     seg2.upd(l+r+2>>1,r,r);
      |              ~~~^~
new_home.cpp: In function 'void splatonto(long long int, long long int, long long int, long long int, long long int, std::pair<long long int, long long int>)':
new_home.cpp:56:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |     splatonto(i*2,l,l+r>>1,ll,rr,vl);
      |                     ~^~
new_home.cpp:57:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     splatonto(i*2+1,l+r+2>>1,r,ll,rr,vl);
      |                     ~~~^~
new_home.cpp: In function 'void solve(long long int, long long int, long long 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.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 43608 KB Output is correct
2 Correct 17 ms 43492 KB Output is correct
3 Correct 17 ms 43612 KB Output is correct
4 Correct 16 ms 43644 KB Output is correct
5 Correct 17 ms 43608 KB Output is correct
6 Incorrect 22 ms 45148 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 43608 KB Output is correct
2 Correct 17 ms 43492 KB Output is correct
3 Correct 17 ms 43612 KB Output is correct
4 Correct 16 ms 43644 KB Output is correct
5 Correct 17 ms 43608 KB Output is correct
6 Incorrect 22 ms 45148 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 911 ms 525748 KB Execution killed with signal 7
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 560 ms 260500 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 43608 KB Output is correct
2 Correct 17 ms 43492 KB Output is correct
3 Correct 17 ms 43612 KB Output is correct
4 Correct 16 ms 43644 KB Output is correct
5 Correct 17 ms 43608 KB Output is correct
6 Incorrect 22 ms 45148 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 43608 KB Output is correct
2 Correct 17 ms 43492 KB Output is correct
3 Correct 17 ms 43612 KB Output is correct
4 Correct 16 ms 43644 KB Output is correct
5 Correct 17 ms 43608 KB Output is correct
6 Incorrect 22 ms 45148 KB Output isn't correct
7 Halted 0 ms 0 KB -