oj.uz

답안 #491527

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
491527 2021-12-02T22:00:14 Z leaked 새 집 (APIO18_new_home) C++14
47 / 100
 5000 ms 1048580 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 lg=log2(300'000)+1;
const int N=pw(lg);
bool del[5*N];
struct segtree{
    vec<int> uk[2*N][2];
    vec<int> pos[2*N];
    vec<int> mx[2*N];
    int type=0;
    void build(int v,int tl,int tr){
        /// my positions are like that
        if(type){
            for(int i=sz(pos[v])-2;i>=0;i--)
                umax(mx[v][i],mx[v][i+1]);
            if(tl==tr)
                return;
            for(int t=0;t<2;t++){
                uk[v][t].resize(sz(pos[v]));
                int u=2*v+t;
                int j=sz(pos[u]);
                for(int i=sz(pos[v])-1;i>=0;i--){
                    while(j!=0 && pos[u][j-1]>=pos[v][i]) --j;
                    uk[v][t][i]=j;
                }
            }
        }
        else{

            for(int i=1;i<sz(pos[v]);i++)
                umax(mx[v][i],mx[v][i-1]);
//            cout<<"BUILD "<<v<<endl;
//            for(auto &z : pos[v])
//                cout<<z<<' ';
//            cout<<endl;
//            for(auto &z : mx[v])
//                cout<<z<<' ';
//            cout<<endl;
            if(tl==tr)
                return;
            for(int t=0;t<2;t++){
                uk[v][t].resize(sz(pos[v]));
                int u=2*v+t;
                int j=-1;
                for(int i=0;i<sz(pos[v]);i++){
                    while(j+1!=sz(pos[u]) && pos[u][j+1]<=pos[v][i]) ++j;
                    uk[v][t][i]=j;
                }
            }
        }
        int tm=(tl+tr)>>1;
        build(2*v,tl,tm);build(2*v+1,tm+1,tr);
    }
    void add(int l,int r,int i,int x,int v,int tl,int tr){
        if(tl>r||tr<l)
            return;
        if(!sz(pos[v]) || pos[v].back()!=i)
            pos[v].pb(i),mx[v].pb(-1e9);
//        cout<<"ADDED "<<i<<' '<<x<<' '<<l<<' '<<r<<' '<<tl<<' '<<tr<<'\n';
        if(tl>=l&&tr<=r){
//            cout<<"_SET "<<v<<' '<<sz(mx[v])-1<<' '<<i<<' '<<x<<endl;
            umax(mx[v].back(),x);
            return;
        }
        int tm=(tl+tr)>>1;
        add(l,r,i,x,2*v,tl,tm);add(l,r,i,x,2*v+1,tm+1,tr);
    }
    int get(int _t,int j,int v,int tl,int tr){
        if(_t>tr || _t<tl)
            return -1e9;
        if(j==-1 || j==sz(pos[v]))
            return -1e9;
        int ans=mx[v][j];
        if(tl==tr){
            return ans;
        }
        int tm=(tl+tr)>>1;
        if(tm>=_t)
            return max(ans,get(_t,uk[v][0][j],2*v,tl,tm));
        else
            return max(ans,get(_t,uk[v][1][j],2*v+1,tm+1,tr));
    }
}lft,rgt;
vec<int> ts;
map<pii,int>mp;
int vr[4*N];
int tmr,cur_t=-1;
vec<array<int,4>>addls;
vec<array<int,4>>addrs;
void add(int l,int r,int t,int tp,int _e=-1){
    if(l==r) return;
    int mid=(l+r)>>1;
    if(!t){
        int st=vr[mp[{l,tp}]],_end=_e;
        if(st>_end)
            return;
        mp.erase({l,tp});
//        cout<<"ADDITIOn "<<l<<' '<<' '<<r<<' '<<st<<' '<<_end<<endl;
        addls.pb({mid,st,_end,-l});
//        cout<<"WHAT "<<mid<<' '<<r<<' '<<st<<' '<<_end<<endl;
        addrs.pb({mid+1,st,_end,r});
        return;
    }
//    cout<<"CHE "<<l<<' '<<r<<endl;
    mp[{l,tp}]=tmr;
    vr[tmr]=_e;
    ++tmr;
}
const int Nax=3e5+1;
multiset<int> st[Nax];
vec<int>here[Nax];
signed main(){
    fast_iati;
    lft.type=1;rgt.type=0;
    int n,q,k;
//    n=15;k=4;q=15;
    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]);
//        ts.pb(a[i]);
//        ts.pb(b[i]+1);
        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();
        ts.pb(y[i]);
        arr.pb({y[i],2,i});
    }
    ts.pb(-2e9);
    sort(all(ts));ts.erase(unique(all(ts)),ts.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])==2) continue;
            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));
//            cout<<"COLOUR "<<j<<' '<<omn<<' '<<tx<<endl;
            umax(me.f,omn);me.s++;
        }
        return me;
    };
    int uk=0,uk1=0;
    vec<int> srt1;
    vec<int> et1;
    for(auto &z : arr){
        while(uk+1<sz(ts) && ts[uk+1]<=z[0]-1) ++uk;
        while(uk1<sz(ts) && ts[uk1]<z[0]) ++uk1;
        et1.pb(uk);srt1.pb(uk1);
//        cout<<"ALOt "<<z[0]<<' '<<uk<<' '<<ts[uk]<<endl;
//        if(z[1]!=2)
//            z[0]=uk+z[1];
    }
    vec<int>cnt(k,0);
    cur_t=0;
    for(int i=0;i<k;i++){
        add(-3e8,3e8,1,i,0);
        st[i].insert(-3e8);st[i].insert(3e8);
    }
    int total=0;
    vec<int>sta(q,-1);
    vec<bool>bad(q,0);
    uk=0;
    for(auto &z : arr){
        if(z[1]!=2)
            cur_t=z[0];
        swap(z[1],z[2]);
        ++uk;
//        if(z[2]!=2)cout<<"ALO "<<x[z[1]]<<' '<<z[1]<<endl;
        if(z[2]==2){
            bad[z[1]]=(total==k?0:1);
            continue;
        }
//        cout<<"TYPE "<<t[z[1]]<<endl;
        if(z[2]==-1){
            int i=z[1];
            auto it=st[t[i]].lower_bound(x[i]);
            int et=et1[uk-1];
            int srt=srt1[uk-1];
            add(x[i],*next(it),0,t[i],et);
            add(*prev(it),x[i],0,t[i],et);
            add(*prev(it),*next(it),1,t[i],srt);
            st[t[i]].erase(it);
            cnt[t[i]]--;
            if(!cnt[t[i]])
                total--;
        }
        else{
            int i=z[1];
            int et=et1[uk-1];
            int srt=srt1[uk-1];
            if(!cnt[t[i]])
                total++;
            cnt[t[i]]++;
            st[t[i]].insert(x[i]);
            auto it=st[t[i]].lower_bound(x[i]);
            add(*prev(it),*next(it),0,t[i],et);
            add(x[i],*next(it),1,t[i],srt);
            add(*prev(it),x[i],1,t[i],srt);
        }
//        cout<<z[0]<<' '<<total<<endl;
    }
    ///building
    sort(all(addls));sort(all(addrs));
    for(auto &z : addls)
        lft.add(z[1],z[2],z[0],z[3],1,0,sz(ts)-1);
    for(auto &z : addrs)
        rgt.add(z[1],z[2],z[0],z[3],1,0,sz(ts)-1);
    lft.build(1,0,sz(ts)-1);
    rgt.build(1,0,sz(ts)-1);

    for(int i=0;i<q;i++){
        int j=l[i];
        int my_t=lower_bound(all(ts),y[i])-ts.begin();
        if(bad[i]){
            cout<<-1<<'\n';
            continue;
        }
        int id=lower_bound(all(lft.pos[1]),j)-lft.pos[1].begin();
        int ans=max(0,j+lft.get(my_t,id,1,0,sz(ts)-1));
        id=upper_bound(all(rgt.pos[1]),j)-rgt.pos[1].begin()-1;
        umax(ans,-j+rgt.get(my_t,id,1,0,sz(ts)-1));
        if(ans>1e8)
            ans=-1;
        cout<<ans<<'\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:162:10: warning: variable 'stupid' set but not used [-Wunused-but-set-variable]
  162 |     auto stupid=[&](array<int,3> z){
      |          ^~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 218380 KB Output is correct
2 Correct 113 ms 218320 KB Output is correct
3 Correct 113 ms 218436 KB Output is correct
4 Correct 116 ms 218440 KB Output is correct
5 Correct 126 ms 218552 KB Output is correct
6 Correct 114 ms 219200 KB Output is correct
7 Correct 115 ms 219236 KB Output is correct
8 Correct 118 ms 219360 KB Output is correct
9 Correct 115 ms 219244 KB Output is correct
10 Correct 121 ms 219336 KB Output is correct
11 Correct 115 ms 219048 KB Output is correct
12 Correct 119 ms 218948 KB Output is correct
13 Correct 124 ms 218800 KB Output is correct
14 Correct 119 ms 218868 KB Output is correct
15 Correct 114 ms 219300 KB Output is correct
16 Correct 116 ms 219404 KB Output is correct
17 Correct 116 ms 219324 KB Output is correct
18 Correct 123 ms 219280 KB Output is correct
19 Correct 118 ms 219368 KB Output is correct
20 Correct 115 ms 219356 KB Output is correct
21 Correct 113 ms 218708 KB Output is correct
22 Correct 114 ms 219332 KB Output is correct
23 Correct 115 ms 219340 KB Output is correct
24 Correct 115 ms 219456 KB Output is correct
25 Correct 117 ms 219332 KB Output is correct
26 Correct 115 ms 219052 KB Output is correct
27 Correct 113 ms 218708 KB Output is correct
28 Correct 114 ms 219120 KB Output is correct
29 Correct 116 ms 218948 KB Output is correct
30 Correct 114 ms 218820 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 218380 KB Output is correct
2 Correct 113 ms 218320 KB Output is correct
3 Correct 113 ms 218436 KB Output is correct
4 Correct 116 ms 218440 KB Output is correct
5 Correct 126 ms 218552 KB Output is correct
6 Correct 114 ms 219200 KB Output is correct
7 Correct 115 ms 219236 KB Output is correct
8 Correct 118 ms 219360 KB Output is correct
9 Correct 115 ms 219244 KB Output is correct
10 Correct 121 ms 219336 KB Output is correct
11 Correct 115 ms 219048 KB Output is correct
12 Correct 119 ms 218948 KB Output is correct
13 Correct 124 ms 218800 KB Output is correct
14 Correct 119 ms 218868 KB Output is correct
15 Correct 114 ms 219300 KB Output is correct
16 Correct 116 ms 219404 KB Output is correct
17 Correct 116 ms 219324 KB Output is correct
18 Correct 123 ms 219280 KB Output is correct
19 Correct 118 ms 219368 KB Output is correct
20 Correct 115 ms 219356 KB Output is correct
21 Correct 113 ms 218708 KB Output is correct
22 Correct 114 ms 219332 KB Output is correct
23 Correct 115 ms 219340 KB Output is correct
24 Correct 115 ms 219456 KB Output is correct
25 Correct 117 ms 219332 KB Output is correct
26 Correct 115 ms 219052 KB Output is correct
27 Correct 113 ms 218708 KB Output is correct
28 Correct 114 ms 219120 KB Output is correct
29 Correct 116 ms 218948 KB Output is correct
30 Correct 114 ms 218820 KB Output is correct
31 Correct 1766 ms 491700 KB Output is correct
32 Correct 216 ms 226564 KB Output is correct
33 Correct 1587 ms 473428 KB Output is correct
34 Correct 1655 ms 474792 KB Output is correct
35 Correct 1704 ms 491368 KB Output is correct
36 Correct 1662 ms 490888 KB Output is correct
37 Correct 1238 ms 447840 KB Output is correct
38 Correct 1190 ms 447052 KB Output is correct
39 Correct 886 ms 402388 KB Output is correct
40 Correct 941 ms 413908 KB Output is correct
41 Correct 1559 ms 432844 KB Output is correct
42 Correct 1387 ms 435684 KB Output is correct
43 Correct 196 ms 228852 KB Output is correct
44 Correct 1495 ms 429572 KB Output is correct
45 Correct 1415 ms 408044 KB Output is correct
46 Correct 1226 ms 364452 KB Output is correct
47 Correct 709 ms 358420 KB Output is correct
48 Correct 677 ms 347400 KB Output is correct
49 Correct 791 ms 379064 KB Output is correct
50 Correct 936 ms 422132 KB Output is correct
51 Correct 780 ms 366068 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3238 ms 781352 KB Output is correct
2 Correct 2820 ms 713172 KB Output is correct
3 Runtime error 3680 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5133 ms 870372 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 218380 KB Output is correct
2 Correct 113 ms 218320 KB Output is correct
3 Correct 113 ms 218436 KB Output is correct
4 Correct 116 ms 218440 KB Output is correct
5 Correct 126 ms 218552 KB Output is correct
6 Correct 114 ms 219200 KB Output is correct
7 Correct 115 ms 219236 KB Output is correct
8 Correct 118 ms 219360 KB Output is correct
9 Correct 115 ms 219244 KB Output is correct
10 Correct 121 ms 219336 KB Output is correct
11 Correct 115 ms 219048 KB Output is correct
12 Correct 119 ms 218948 KB Output is correct
13 Correct 124 ms 218800 KB Output is correct
14 Correct 119 ms 218868 KB Output is correct
15 Correct 114 ms 219300 KB Output is correct
16 Correct 116 ms 219404 KB Output is correct
17 Correct 116 ms 219324 KB Output is correct
18 Correct 123 ms 219280 KB Output is correct
19 Correct 118 ms 219368 KB Output is correct
20 Correct 115 ms 219356 KB Output is correct
21 Correct 113 ms 218708 KB Output is correct
22 Correct 114 ms 219332 KB Output is correct
23 Correct 115 ms 219340 KB Output is correct
24 Correct 115 ms 219456 KB Output is correct
25 Correct 117 ms 219332 KB Output is correct
26 Correct 115 ms 219052 KB Output is correct
27 Correct 113 ms 218708 KB Output is correct
28 Correct 114 ms 219120 KB Output is correct
29 Correct 116 ms 218948 KB Output is correct
30 Correct 114 ms 218820 KB Output is correct
31 Correct 1766 ms 491700 KB Output is correct
32 Correct 216 ms 226564 KB Output is correct
33 Correct 1587 ms 473428 KB Output is correct
34 Correct 1655 ms 474792 KB Output is correct
35 Correct 1704 ms 491368 KB Output is correct
36 Correct 1662 ms 490888 KB Output is correct
37 Correct 1238 ms 447840 KB Output is correct
38 Correct 1190 ms 447052 KB Output is correct
39 Correct 886 ms 402388 KB Output is correct
40 Correct 941 ms 413908 KB Output is correct
41 Correct 1559 ms 432844 KB Output is correct
42 Correct 1387 ms 435684 KB Output is correct
43 Correct 196 ms 228852 KB Output is correct
44 Correct 1495 ms 429572 KB Output is correct
45 Correct 1415 ms 408044 KB Output is correct
46 Correct 1226 ms 364452 KB Output is correct
47 Correct 709 ms 358420 KB Output is correct
48 Correct 677 ms 347400 KB Output is correct
49 Correct 791 ms 379064 KB Output is correct
50 Correct 936 ms 422132 KB Output is correct
51 Correct 780 ms 366068 KB Output is correct
52 Correct 1335 ms 433512 KB Output is correct
53 Correct 1337 ms 429156 KB Output is correct
54 Correct 1472 ms 479480 KB Output is correct
55 Correct 1417 ms 449804 KB Output is correct
56 Correct 1362 ms 449888 KB Output is correct
57 Correct 1558 ms 435792 KB Output is correct
58 Correct 1442 ms 446248 KB Output is correct
59 Correct 1417 ms 444012 KB Output is correct
60 Correct 1431 ms 438340 KB Output is correct
61 Correct 345 ms 251908 KB Output is correct
62 Correct 1235 ms 441304 KB Output is correct
63 Correct 1516 ms 471192 KB Output is correct
64 Correct 1568 ms 478200 KB Output is correct
65 Correct 1620 ms 486944 KB Output is correct
66 Correct 1561 ms 449716 KB Output is correct
67 Correct 346 ms 236968 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 218380 KB Output is correct
2 Correct 113 ms 218320 KB Output is correct
3 Correct 113 ms 218436 KB Output is correct
4 Correct 116 ms 218440 KB Output is correct
5 Correct 126 ms 218552 KB Output is correct
6 Correct 114 ms 219200 KB Output is correct
7 Correct 115 ms 219236 KB Output is correct
8 Correct 118 ms 219360 KB Output is correct
9 Correct 115 ms 219244 KB Output is correct
10 Correct 121 ms 219336 KB Output is correct
11 Correct 115 ms 219048 KB Output is correct
12 Correct 119 ms 218948 KB Output is correct
13 Correct 124 ms 218800 KB Output is correct
14 Correct 119 ms 218868 KB Output is correct
15 Correct 114 ms 219300 KB Output is correct
16 Correct 116 ms 219404 KB Output is correct
17 Correct 116 ms 219324 KB Output is correct
18 Correct 123 ms 219280 KB Output is correct
19 Correct 118 ms 219368 KB Output is correct
20 Correct 115 ms 219356 KB Output is correct
21 Correct 113 ms 218708 KB Output is correct
22 Correct 114 ms 219332 KB Output is correct
23 Correct 115 ms 219340 KB Output is correct
24 Correct 115 ms 219456 KB Output is correct
25 Correct 117 ms 219332 KB Output is correct
26 Correct 115 ms 219052 KB Output is correct
27 Correct 113 ms 218708 KB Output is correct
28 Correct 114 ms 219120 KB Output is correct
29 Correct 116 ms 218948 KB Output is correct
30 Correct 114 ms 218820 KB Output is correct
31 Correct 1766 ms 491700 KB Output is correct
32 Correct 216 ms 226564 KB Output is correct
33 Correct 1587 ms 473428 KB Output is correct
34 Correct 1655 ms 474792 KB Output is correct
35 Correct 1704 ms 491368 KB Output is correct
36 Correct 1662 ms 490888 KB Output is correct
37 Correct 1238 ms 447840 KB Output is correct
38 Correct 1190 ms 447052 KB Output is correct
39 Correct 886 ms 402388 KB Output is correct
40 Correct 941 ms 413908 KB Output is correct
41 Correct 1559 ms 432844 KB Output is correct
42 Correct 1387 ms 435684 KB Output is correct
43 Correct 196 ms 228852 KB Output is correct
44 Correct 1495 ms 429572 KB Output is correct
45 Correct 1415 ms 408044 KB Output is correct
46 Correct 1226 ms 364452 KB Output is correct
47 Correct 709 ms 358420 KB Output is correct
48 Correct 677 ms 347400 KB Output is correct
49 Correct 791 ms 379064 KB Output is correct
50 Correct 936 ms 422132 KB Output is correct
51 Correct 780 ms 366068 KB Output is correct
52 Correct 3238 ms 781352 KB Output is correct
53 Correct 2820 ms 713172 KB Output is correct
54 Runtime error 3680 ms 1048580 KB Execution killed with signal 9
55 Halted 0 ms 0 KB -