답안 #1028533

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1028533	2024-07-20T03:54:16 Z	vjudge1	새 집 (APIO18_new_home)	C++17	10 / 100	5000 ms	301560 KB

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=-2e9;}
    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[-2e9]=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(-2e9),stor[i].insert(2e9);
    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[2e9]=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[-2e9]=0;
    compr[2e9]=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]>2e9?-1:ans[i])<<'\n';
}

Compilation message

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
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	54364 KB	Output is correct
2	Incorrect	10 ms	54420 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	54364 KB	Output is correct
2	Incorrect	10 ms	54420 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1844 ms	229432 KB	Output is correct
2	Correct	1456 ms	156524 KB	Output is correct
3	Correct	1718 ms	301560 KB	Output is correct
4	Correct	1869 ms	242580 KB	Output is correct
5	Correct	1347 ms	147852 KB	Output is correct
6	Correct	1466 ms	152964 KB	Output is correct
7	Correct	1693 ms	301480 KB	Output is correct
8	Correct	1676 ms	243240 KB	Output is correct
9	Correct	1677 ms	217664 KB	Output is correct
10	Correct	1540 ms	178168 KB	Output is correct
11	Correct	966 ms	159264 KB	Output is correct
12	Correct	1141 ms	175056 KB	Output is correct