oj.uz

Submission #1028479

# Submission time Handle Problem Language Result Execution time Memory
1028479 2024-07-20T02:22:27 Z vjudge1 New Home (APIO18_new_home) C++17
0 / 100
 1738 ms 545364 KB 
#include<bits/stdc++.h>
using namespace std;
map<int,vector<pair<int,int>>> ad,del,qr;
int ans[300100];
multiset<int>stor[401];
set<int>stuffhappens;
struct segtree{
    int rt,CC;
    int lc[1<<23],rc[1<<23], vl[1<<23];
    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>rr||ll>r)return;
        if(!i) i=++CC;
        if(ll<=l&&r<=rr) return 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);
    }
} seg1,seg2;
void a_range(int l,int r){
    seg1.upd(l,l+r>>1,-l);
    seg2.upd(l+r+2>>1,r,r);
}
int main(){
    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);
        del[r+1].push_back({a,b});
        stuffhappens.insert(r+1);
    }
    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});
        stuffhappens.insert(y);
    }
    for(int i=1;i<=k;i++){
        auto it=++stor[i].begin();
        while(it!=stor[i].end()){
            a_range(*prev(it),*it);
            it++;
        }
    }
    for(auto year:stuffhappens){
        for(auto[p,t]:del[year]) {
            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));
        }
        for(auto[p,i]:qr[year])
            ans[i]=max(seg1.qry(p)+p,seg2.qry(p)-p);
    }
    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(int&, int, int, int, int, int)':
new_home.cpp:15:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |         update(lc[i],l,l+r>>1,ll,rr,v);
      |                        ~^~
new_home.cpp:16:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |         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:20:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |         if(l+r>>1<p)
      |            ~^~
new_home.cpp:21:45: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |             return max(vl[i],query(rc[i],l+r+2>>1,r,p));
      |                                          ~~~^~
new_home.cpp:22:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         return max(vl[i],query(lc[i],l,l+r>>1,p));
      |                                        ~^~
new_home.cpp: In function 'void a_range(int, int)':
new_home.cpp:32:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     seg1.upd(l,l+r>>1,-l);
      |                ~^~
new_home.cpp:33:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |     seg2.upd(l+r+2>>1,r,r);
      |              ~~~^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 66136 KB Output is correct
2 Correct 26 ms 66092 KB Output is correct
3 Correct 26 ms 66132 KB Output is correct
4 Incorrect 27 ms 66188 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 66136 KB Output is correct
2 Correct 26 ms 66092 KB Output is correct
3 Correct 26 ms 66132 KB Output is correct
4 Incorrect 27 ms 66188 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1738 ms 545364 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 30 ms 66136 KB Output is correct
2 Correct 26 ms 66092 KB Output is correct
3 Correct 26 ms 66132 KB Output is correct
4 Incorrect 27 ms 66188 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 66136 KB Output is correct
2 Correct 26 ms 66092 KB Output is correct
3 Correct 26 ms 66132 KB Output is correct
4 Incorrect 27 ms 66188 KB Output isn't correct
5 Halted 0 ms 0 KB -