oj.uz

Submission #487786

# Submission time Handle Problem Language Result Execution time Memory
487786 2021-11-16T16:13:44 Z leaked New Home (APIO18_new_home) C++14
5 / 100
 5000 ms 10316 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;
    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];
        kek.pb(x[i]);
        arr.pb({a[i],i,0});
        arr.pb({b[i]+1,i,-1});
        --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];
        kek.pb(y[i]);
        arr.pb({y[i],i,2});
    }
    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(x);
//            int mn=2e9;
//            if(it!=st[j].end()) umin(mn,*it-x);
//            if(it!=st[j].begin()) umin(mn,x-*prev(it));
//            umax(me.f,mn);

//            me.s++;
            int mn=2e9;
            for(auto &tr : here[j]){
                if(a[tr]<=z[0]&&b[tr]>=z[0]){
                    umin(mn,abs(x[tr]-tx));
//                    cout<<"AE "<<z[1]<<' '<<t<<endl;
                }
            }
            if(mn==2e9) continue;
            umax(me.f,mn);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){
        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:165:17: warning: unused variable 'i' [-Wunused-variable]
  165 |             int i=z[1];
      |                 ^
new_home.cpp:176:17: warning: unused variable 'i' [-Wunused-variable]
  176 |             int i=z[1];
      |                 ^
new_home.cpp:128:10: warning: variable 'solve' set but not used [-Wunused-but-set-variable]
  128 |     auto solve=[&](array<int,3> z){
      |          ^~~~~
new_home.cpp:145:9: warning: unused variable 'total' [-Wunused-variable]
  145 |     int total=0;
      |         ^~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 10316 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 10316 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 1 ms 460 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 588 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 1 ms 460 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 1 ms 460 KB Output is correct
28 Correct 1 ms 460 KB Output is correct
29 Correct 1 ms 460 KB Output is correct
30 Correct 1 ms 460 KB Output is correct
31 Execution timed out 5025 ms 5944 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

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