oj.uz

Submission #487791

# Submission time Handle Problem Language Result Execution time Memory
487791 2021-11-16T16:24:59 Z leaked New Home (APIO18_new_home) C++14
12 / 100
 1745 ms 10452 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define sz(x) (int)(x).size()
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pw(x) (1LL<<(x))
#define m_p make_pair
#define fast_iati ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;

const int N=4e2+100;
struct segtree{
    multiset<int> st[4*N];
    void add(int l,int r,int tp,int x,int v,int tl,int tr){
        if(tl>=l&&tr<=r){
            if(tp)
                st[v].insert(x);
            else
                st[v].erase(st[v].find(x));
//            cout<<"ADDT "<<tp<<' '<<tl<<' '<<tr<<' '<<x<<endl;
            return;
        }
        if(tl>r||tr<l) return;
        int tm=(tl+tr)>>1;
        add(l,r,tp,x,2*v,tl,tm);add(l,r,tp,x,2*v+1,tm+1,tr);
    }
    pii get(int id,int v,int tl,int tr){
        pii ans={-1e9,0};
        ans.s+=sz(st[v]);
        if(sz(st[v]))
            umax(ans.f,*st[v].rbegin());
        if(tl==tr){
            return ans;
        }
        int tm=(tl+tr)>>1;
        pii w;
        if(tm>=id)
            w=get(id,2*v,tl,tm);
        else
            w=get(id,2*v+1,tm+1,tr);
        ans.f=max(ans.f,w.f);
        ans.s+=w.s;
        return ans;
    }
}lft,rgt;
vec<int> kek;
int gl(int x){
    return upper_bound(all(kek),x)-kek.begin()-1;
}
int gu(int x){
    return upper_bound(all(kek),x)-kek.begin();
}
void add(int l,int r,int t){
    if(l==r) return;
    int mid=(l+r)>>1;
//    if(l!=-3e8 || r!=3e8){
////    cout<<"ADD "<<l<<' '<<mid<<' '<<t<<' '<<-l<<' '<<endl;
////    cout<<"ADD "<<mid+1<<' '<<r<<' '<<t<<' '<<r<<' '<<endl;
//    }
    if(gl(mid)>=0)
        lft.add(gl(l),gl(mid),t,-l,1,0,sz(kek)-1);
    if(gl(mid)+1<=gl(r))
        rgt.add(gl(mid)+1,gl(r),t,r,1,0,sz(kek)-1);
}
const int Nax=3e5+1;
multiset<int> st[N];
vec<int>here[N];
signed main(){
    fast_iati;
    int n,q,k;
//    n=400,q=240,k=7;
    cin>>n>>k>>q;
    vec<array<int,3>>arr;
    vec<int>x(n),a(n),b(n),t(n);
    for(int i=0;i<n;i++){
        cin>>x[i]>>t[i]>>a[i]>>b[i];
//        x[i]=rand(),t[i]=rand()%k+1;
//        a[i]=rand(),b[i]=rand();
//        if(a[i]>b[i])
//            swap(a[i],b[i]);
        kek.pb(x[i]);
        arr.pb({a[i],0,i});
        arr.pb({b[i]+1,-1,i});
        --t[i];
        here[t[i]].pb(i);
    }
    vec<int>l(q),y(q);
    for(int i=0;i<q;i++){
        cin>>l[i]>>y[i];
//        l[i]=rand(),y[i]=rand();
        kek.pb(l[i]);
        arr.pb({y[i],2,i});
    }
    sort(all(kek));kek.erase(unique(all(kek)),kek.end());
    sort(all(arr));
    auto stupid=[&](array<int,3> z){
        pii me={-1e9,0};
        int tx=l[z[1]];
        for(int j=0;j<k;j++){
            if(sz(st[j])==0) continue;
////            cout<<"TYP "<<endl;
////            for(auto &z : st[j])
////                cout<<z<<' ';
////            cout<<endl
            auto it=st[j].lower_bound(tx);
            int omn=2e9;
            if(it!=st[j].end()) umin(omn,*it-tx);
            if(it!=st[j].begin()) umin(omn,tx-*prev(it));
            umax(me.f,omn);me.s++;
        }
        return me;
    };
    auto solve=[&](array<int,3> z){
        pii me={-1e9,0};
        int x=l[z[1]];
        x=gl(x);
        pii fe=lft.get(x,1,0,sz(kek)-1);
        pii si=rgt.get(x,1,0,sz(kek)-1);
//        cout<<fe.f<<' '<<si.f<<endl;
        me.s=fe.s+si.s;
        me.f=max(fe.f+l[z[1]],si.f-l[z[1]]);
        return me;
    };
    vec<int>cnt(k,0);
//    for(int i=0;i<k;i++){
////        add(-3e8,3e8,1);
////        st[i].insert(-3e8);
////        st[i].insert(3e8);
//    }
    int total=0;
    vec<int>ans(q,-1);
    for(auto &z : arr){
        swap(z[1],z[2]);
        if(z[2]==2){
            pii og=stupid(z);
//            cout<<"TOTAL "<<total<<' '<<og.s<<endl;
//            assert(total==og.s);
            if(og.s!=k){
                ans[z[1]]=-1;
                continue;
            }
//            assert(rio.f==og.f);
//            pii rio=solve(z);
//            assert(rio.f==og.f);
            ans[z[1]]=og.f;
//            cerr<<"BRUTE "<<og.f<<' '<<og.s<<endl;
//            cerr<<"SOL "<<rio.f<<' '<<rio.s<<endl;
//            ans[z[1]]=rio.f;
        }
        else if(z[2]==-1){
            int i=z[1];
            auto it=st[t[i]].lower_bound(x[i]);
//            add(x[i],*next(it),0);
//            add(*prev(it),x[i],0);
//            add(*prev(it),*next(it),1);
            st[t[i]].erase(it);
//            cnt[t[i]]--;
//            if(!cnt[t[i]]) total--;
//            cout<<"DEL "<<t[i]<<' '<<x[i]<<endl;
        }
        else{
            int i=z[1];
//            if(!cnt[t[i]]) total++;
//            cnt[t[i]]++;
            st[t[i]].insert(x[i]);
//            cout<<"BLY "<<t[i]<<' '<<x[i]<<endl;
//            auto it=st[t[i]].lower_bound(x[i]);
//            add(*prev(it),*next(it),0);
//            add(x[i],*next(it),1);
//            add(*prev(it),x[i],1);
        }
    }
    for(auto &z : ans)
        cout<<z<<'\n';
    return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10


2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

1 1 1
100000000 1 1 1
1 1
*/

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:123:10: warning: variable 'solve' set but not used [-Wunused-but-set-variable]
  123 |     auto solve=[&](array<int,3> z){
      |          ^~~~~
new_home.cpp:140:9: warning: unused variable 'total' [-Wunused-variable]
  140 |     int total=0;
      |         ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 2 ms 588 KB Output is correct
14 Correct 1 ms 588 KB Output is correct
15 Correct 1 ms 588 KB Output is correct
16 Correct 1 ms 588 KB Output is correct
17 Correct 1 ms 588 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 1 ms 588 KB Output is correct
20 Correct 1 ms 588 KB Output is correct
21 Correct 1 ms 588 KB Output is correct
22 Correct 2 ms 588 KB Output is correct
23 Correct 1 ms 588 KB Output is correct
24 Correct 2 ms 588 KB Output is correct
25 Correct 1 ms 588 KB Output is correct
26 Correct 1 ms 588 KB Output is correct
27 Correct 1 ms 588 KB Output is correct
28 Correct 1 ms 588 KB Output is correct
29 Correct 1 ms 588 KB Output is correct
30 Correct 1 ms 460 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 2 ms 588 KB Output is correct
14 Correct 1 ms 588 KB Output is correct
15 Correct 1 ms 588 KB Output is correct
16 Correct 1 ms 588 KB Output is correct
17 Correct 1 ms 588 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 1 ms 588 KB Output is correct
20 Correct 1 ms 588 KB Output is correct
21 Correct 1 ms 588 KB Output is correct
22 Correct 2 ms 588 KB Output is correct
23 Correct 1 ms 588 KB Output is correct
24 Correct 2 ms 588 KB Output is correct
25 Correct 1 ms 588 KB Output is correct
26 Correct 1 ms 588 KB Output is correct
27 Correct 1 ms 588 KB Output is correct
28 Correct 1 ms 588 KB Output is correct
29 Correct 1 ms 588 KB Output is correct
30 Correct 1 ms 460 KB Output is correct
31 Correct 1745 ms 8464 KB Output is correct
32 Correct 101 ms 6332 KB Output is correct
33 Correct 157 ms 6536 KB Output is correct
34 Correct 1380 ms 6812 KB Output is correct
35 Correct 814 ms 8276 KB Output is correct
36 Correct 174 ms 8288 KB Output is correct
37 Correct 152 ms 5880 KB Output is correct
38 Correct 91 ms 6016 KB Output is correct
39 Correct 78 ms 5920 KB Output is correct
40 Correct 78 ms 6072 KB Output is correct
41 Correct 237 ms 5752 KB Output is correct
42 Correct 304 ms 5876 KB Output is correct
43 Correct 179 ms 8524 KB Output is correct
44 Correct 195 ms 5848 KB Output is correct
45 Correct 108 ms 5888 KB Output is correct
46 Correct 69 ms 5888 KB Output is correct
47 Correct 72 ms 5880 KB Output is correct
48 Correct 59 ms 5876 KB Output is correct
49 Correct 74 ms 5836 KB Output is correct
50 Correct 183 ms 5988 KB Output is correct
51 Correct 90 ms 5944 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 10436 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 7 ms 10452 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 0 ms 460 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 2 ms 588 KB Output is correct
14 Correct 1 ms 588 KB Output is correct
15 Correct 1 ms 588 KB Output is correct
16 Correct 1 ms 588 KB Output is correct
17 Correct 1 ms 588 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 1 ms 588 KB Output is correct
20 Correct 1 ms 588 KB Output is correct
21 Correct 1 ms 588 KB Output is correct
22 Correct 2 ms 588 KB Output is correct
23 Correct 1 ms 588 KB Output is correct
24 Correct 2 ms 588 KB Output is correct
25 Correct 1 ms 588 KB Output is correct
26 Correct 1 ms 588 KB Output is correct
27 Correct 1 ms 588 KB Output is correct
28 Correct 1 ms 588 KB Output is correct
29 Correct 1 ms 588 KB Output is correct
30 Correct 1 ms 460 KB Output is correct
31 Correct 1745 ms 8464 KB Output is correct
32 Correct 101 ms 6332 KB Output is correct
33 Correct 157 ms 6536 KB Output is correct
34 Correct 1380 ms 6812 KB Output is correct
35 Correct 814 ms 8276 KB Output is correct
36 Correct 174 ms 8288 KB Output is correct
37 Correct 152 ms 5880 KB Output is correct
38 Correct 91 ms 6016 KB Output is correct
39 Correct 78 ms 5920 KB Output is correct
40 Correct 78 ms 6072 KB Output is correct
41 Correct 237 ms 5752 KB Output is correct
42 Correct 304 ms 5876 KB Output is correct
43 Correct 179 ms 8524 KB Output is correct
44 Correct 195 ms 5848 KB Output is correct
45 Correct 108 ms 5888 KB Output is correct
46 Correct 69 ms 5888 KB Output is correct
47 Correct 72 ms 5880 KB Output is correct
48 Correct 59 ms 5876 KB Output is correct
49 Correct 74 ms 5836 KB Output is correct
50 Correct 183 ms 5988 KB Output is correct
51 Correct 90 ms 5944 KB Output is correct
52 Runtime error 2 ms 2764 KB Execution killed with signal 11
53 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 2 ms 588 KB Output is correct
14 Correct 1 ms 588 KB Output is correct
15 Correct 1 ms 588 KB Output is correct
16 Correct 1 ms 588 KB Output is correct
17 Correct 1 ms 588 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 1 ms 588 KB Output is correct
20 Correct 1 ms 588 KB Output is correct
21 Correct 1 ms 588 KB Output is correct
22 Correct 2 ms 588 KB Output is correct
23 Correct 1 ms 588 KB Output is correct
24 Correct 2 ms 588 KB Output is correct
25 Correct 1 ms 588 KB Output is correct
26 Correct 1 ms 588 KB Output is correct
27 Correct 1 ms 588 KB Output is correct
28 Correct 1 ms 588 KB Output is correct
29 Correct 1 ms 588 KB Output is correct
30 Correct 1 ms 460 KB Output is correct
31 Correct 1745 ms 8464 KB Output is correct
32 Correct 101 ms 6332 KB Output is correct
33 Correct 157 ms 6536 KB Output is correct
34 Correct 1380 ms 6812 KB Output is correct
35 Correct 814 ms 8276 KB Output is correct
36 Correct 174 ms 8288 KB Output is correct
37 Correct 152 ms 5880 KB Output is correct
38 Correct 91 ms 6016 KB Output is correct
39 Correct 78 ms 5920 KB Output is correct
40 Correct 78 ms 6072 KB Output is correct
41 Correct 237 ms 5752 KB Output is correct
42 Correct 304 ms 5876 KB Output is correct
43 Correct 179 ms 8524 KB Output is correct
44 Correct 195 ms 5848 KB Output is correct
45 Correct 108 ms 5888 KB Output is correct
46 Correct 69 ms 5888 KB Output is correct
47 Correct 72 ms 5880 KB Output is correct
48 Correct 59 ms 5876 KB Output is correct
49 Correct 74 ms 5836 KB Output is correct
50 Correct 183 ms 5988 KB Output is correct
51 Correct 90 ms 5944 KB Output is correct
52 Runtime error 7 ms 10436 KB Execution killed with signal 11
53 Halted 0 ms 0 KB -