oj.uz

Submission #1028480

# Submission time Handle Problem Language Result Execution time Memory
1028480 2024-07-20T02:22:55 Z vjudge1 New Home (APIO18_new_home) C++17
33 / 100
 3745 ms 379936 KB 
#include<bits/stdc++.h>
using namespace std;
map<int,vector<pair<int,int>>> ad,del,qr;
int ans[300100];
multiset<int>stor[300100];
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 34 ms 80220 KB Output is correct
2 Correct 35 ms 80212 KB Output is correct
3 Correct 35 ms 80220 KB Output is correct
4 Incorrect 35 ms 80180 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 80220 KB Output is correct
2 Correct 35 ms 80212 KB Output is correct
3 Correct 35 ms 80220 KB Output is correct
4 Incorrect 35 ms 80180 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2284 ms 288592 KB Output is correct
2 Correct 2518 ms 311488 KB Output is correct
3 Correct 1393 ms 266424 KB Output is correct
4 Correct 2087 ms 282048 KB Output is correct
5 Correct 2325 ms 308868 KB Output is correct
6 Correct 2451 ms 311224 KB Output is correct
7 Correct 1301 ms 266564 KB Output is correct
8 Correct 1889 ms 279992 KB Output is correct
9 Correct 2326 ms 296592 KB Output is correct
10 Correct 2562 ms 312120 KB Output is correct
11 Correct 1422 ms 307896 KB Output is correct
12 Correct 1610 ms 308796 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3745 ms 362084 KB Output is correct
2 Correct 345 ms 105316 KB Output is correct
3 Correct 3285 ms 379108 KB Output is correct
4 Correct 2092 ms 332016 KB Output is correct
5 Correct 3071 ms 354132 KB Output is correct
6 Correct 2782 ms 347896 KB Output is correct
7 Correct 3116 ms 376436 KB Output is correct
8 Correct 3324 ms 378512 KB Output is correct
9 Correct 1840 ms 333140 KB Output is correct
10 Correct 2847 ms 351828 KB Output is correct
11 Correct 3462 ms 370116 KB Output is correct
12 Correct 3663 ms 379936 KB Output is correct
13 Correct 1519 ms 367276 KB Output is correct
14 Correct 1407 ms 366420 KB Output is correct
15 Correct 1831 ms 373576 KB Output is correct
16 Correct 2214 ms 375124 KB Output is correct
17 Correct 1759 ms 373076 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 80220 KB Output is correct
2 Correct 35 ms 80212 KB Output is correct
3 Correct 35 ms 80220 KB Output is correct
4 Incorrect 35 ms 80180 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 80220 KB Output is correct
2 Correct 35 ms 80212 KB Output is correct
3 Correct 35 ms 80220 KB Output is correct
4 Incorrect 35 ms 80180 KB Output isn't correct
5 Halted 0 ms 0 KB -