Submission #491699

#	Time	Username	Problem	Language	Result	Execution time	Memory
491699		Redhood	New Home (APIO18_new_home)	C++14	0 / 100	642 ms	34972 KiB

new_home

#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define pb push_back
typedef long long ll;
typedef long double ld;
using namespace std;
struct fun{
    int tl , tr , bound,  x;
    fun(){}
    fun(int _tl , int _tr , int _bound , int _x){tl = _tl , tr = _tr , bound = _bound, x = _x;}
};

const int N = (int)6e2 + 10;
const int K = (int)3e2 + 10;
const int inf = 1e9;


const int M = (int)1e6 + 10;
set < pair < int , int > > pos[K];



vector < int > scanA[N], scanD[N], add[N], del[N];
int seg[4*M];

void upd(int v , int tl , int tr , int pos , int val){
    if(tl == tr){
        seg[v] = val;
        return;
    }
    int mid = (tl + tr) >> 1 , v1 = v << 1;
    if(pos <= mid)
        upd(v1 , tl , mid , pos , val);
    else
        upd(v1 | 1 , mid + 1 , tr , pos , val);
    seg[v] = min(seg[v1] , seg[v1|1]);
}
int get(int v , int tl , int tr , int l , int r){
    if(tl == l && tr == r){
        return seg[v];
    }
    int ans = inf, mid = (tl + tr) >> 1 , v1 = v << 1;
    if(l <= mid)
        ans = min(ans , get(v1, tl , mid , l , min(r , mid)));
    if(r > mid)
        ans = min(ans , get(v1 | 1 , mid + 1 , tr , max(l , mid + 1) , r));
    return ans;
}

signed main(){
    int n , q , k;
    cin >> n >> k >> q;

    vector < int > x(n), t(n), a(n), b(n);


    vector < int > times, cords;
    for(int i = 0 ; i < n; ++i){
        cin >> x[i] >> t[i] >> a[i] >> b[i];
        b[i]++;
        times.push_back(a[i]), times.push_back(b[i]);
        cords.push_back(x[i]);
    }

    vector < pair < int , int > > que(q);
    for(auto &i : que){
        cin >> i.fi >> i.se;
        cords.push_back(i.fi);
        times.push_back(i.se);
    }
    cords.pb(inf), cords.pb(-inf);
    sort(all(times)), times.erase(unique(all(times)), times.end());
    sort(all(cords)), cords.erase(unique(all(cords)), cords.end());
    int Latest = inf;
    vector < int > latest(k + 1 , -inf);
    for(int i = 0 ; i < n; ++i){
        x[i] = lower_bound(all(cords) , x[i]) - cords.begin();
        a[i] = lower_bound(all(times) , a[i]) - times.begin();
        b[i] = lower_bound(all(times) , b[i]) - times.begin();
        add[a[i]].push_back(i);
        del[b[i]].push_back(i);
        latest[t[i]] = max(latest[t[i]], b[i]);
    }
    for(int t = 1; t <= k; ++t)
        Latest= min(Latest ,latest[t]);

    for(auto &i : que){
        i.fi = lower_bound(all(cords), i.fi) - cords.begin();
        i.se = lower_bound(all(times) , i.se) - times.begin();
    }
    /// first of all we should parse function R L


    for(int i = 1; i <= k; ++i)
    pos[i].insert({sz(cords)-1 , n}), pos[i].insert({0,  n});

    vector < fun > L, R;

    vector < int > lstL(n + 1), lstR(n + 1);
    for(int ti = 0; ti <= sz(times); ++ti){
        for(auto &u : add[ti]){
            int type = t[u];
            auto it = pos[type].lower_bound(make_pair(x[u], -1));
            auto it1 = it;
            it1--;
            /// how we change left and how we change right
            int m = (cords[it->fi] + cords[it1->fi]) / 2;


            if(lstL[it1->se] <= ti - 1){
                L.push_back({lstL[it1->se], ti - 1, m, it1->fi});
                lstL[it1->se] = ti;
            }
            lstL[it1->se] = ti;
            if(lstR[it->se] <= ti - 1){
                R.push_back({lstR[it->se], ti - 1, m, it->fi});
                lstR[it->se] = ti;
            }
            lstR[it->se] = ti;


            lstL[u] = ti;
            lstR[u] = ti;
            pos[type].insert(make_pair(x[u], u));


        }
        for(auto &u : del[ti]){
            int type = t[u];
            auto it = pos[type].lower_bound(make_pair(x[u], u));
            auto it1 = it;
            it1--;
            auto it2 = it;
            it2++;


            if(lstR[it->se] <= ti - 1){
//                assert(lstR[it1->se] >= lstL[it->se]);
                int m1 = (cords[it->fi] + cords[it1->fi]) / 2;
                R.push_back({lstR[it->se], ti - 1, m1, it->fi});
            }
            if(lstL[it->se] <= ti - 1){
//                assert(lstR[it2->se] <= lstR[it2->se]);
                int m2 = (cords[it->fi] + cords[it2->fi]) / 2;
                L.push_back({lstL[it->se], ti - 1, m2, it->fi});
            }

            lstL[it1->se] = ti;
            lstR[it2->se] = ti;
            pos[type].erase(it);
        }
    }
    vector < int > answer(q, inf);


    vector < int > qperm(q);
    vector < int > ans(q);
    iota(all(qperm) , 0);
    sort(all(qperm) , [&](int x , int y){
            return que[x].se < que[y].se;
         });

    /// do scan LINE

//    cout << " YO FUN \n";
//    cout << "L \n";
//    for(auto &u : L){
//        cout << u.tl << ' ' << u.tr << ' ' << u.bound << ' ' << cords[u.x] << endl;
//    }
//cout << "R \n";
//    for(auto &u : R){
//        cout << u.tl << ' ' << u.tr << ' ' << u.bound << ' ' << cords[u.x] << endl;
//    }
//    cout << endl;
//
//    for(auto &u : que)
//        cout << cords[u.fi] << ' ' << u.se << endl;
//    cout << endl;




    for(int i = 0; i < q; ++i){
        assert(ans[i] == 0);
//        cout << " LOL " << i << ' ' << que[i].se << endl;
        for(auto &j : L){
            if(j.tl <= que[i].se && j.tr >= que[i].se && que[i].fi <= j.bound){
                ans[i] = max(ans[i] , cords[que[i].fi] - cords[j.x]);
            }
        }
        for(auto &j : R){
            if(j.tl <= que[i].se && j.tr >= que[i].se && que[i].fi >= j.bound){
                ans[i] = max(ans[i] , -cords[que[i].fi] + cords[j.x]);
            }
        }
        if(ans[i] >= (int)1e8 || que[i].se < Latest)
        cout << ans[i] << '\n';
        else
        cout << -1 << '\n';
    }
    return 0;
    if(false){
        for(int i =  0; i < N; ++i){
            scanA[i].clear();
            scanD[i].clear();
        }
        /// so we gotta get them pos
        vector < int > pos(sz(L));
        iota(all(pos) , 0);
        sort(all(pos) , [&](int x , int y){
                return L[x].bound <= L[y].bound;
             });
        vector < int > revpos(sz(L));
        for(int i = 0; i < sz(pos); ++i){
            revpos[pos[i]] = i;
        }

        for(int i = 0; i < sz(pos); ++i){
            scanA[L[i].tl].push_back(i);
            scanD[R[i].tr + 1].push_back(i);
        }

        int lst = 0;
        for(int tt = 0; tt < N; ++tt){
            for(auto &u : scanA[tt]){
                upd(1 , 0 , M - 1 , revpos[u], L[u].x);
            }
            for(auto &u : scanD[tt]){
                upd(1 , 0 , M - 1 , revpos[u], inf);
            }
            while(lst < q && que[qperm[lst]].se == tt){
                int f = qperm[lst];

                int l = 0 , r = sz(L) - 1;
                while(l != r){
                    int mid = (l + r) >> 1;
                    if(cords[que[f].fi] <= L[mid].bound){
                        if(l + 1 == r)
                            l = r;
                        else
                            l = mid;
                    }else
                        r = mid;
                }
                if(cords[que[f].fi] <= L[r].bound)
                    ++r;
                --r;
                /// so what do we say we say that suffix is GOOOD
                int tv;
                if(r == -1)
                    tv = inf;
                else
                    tv = get(1 , 0, M-1, r , sz(L) - 1);

                if(tv == inf)
                    tv = inf;
                else
                    tv = cords[tv];
                ans[f] = max(ans[f] , cords[que[f].fi] - tv);
                lst++;
            }
        }



    }






    if(false){
        for(int i =  0; i < N; ++i){
            scanA[i].clear();
            scanD[i].clear();
        }
        /// so we gotta get them pos
        vector < int > pos(sz(R));
        iota(all(pos) , 0);
        sort(all(pos) , [&](int x , int y){
                return R[x].bound <= R[y].bound;
             });
        vector < int > revpos(sz(R));
        for(int i = 0; i < sz(pos); ++i){
            revpos[pos[i]] = i;
        }

        for(int i = 0; i < sz(pos); ++i){
            scanA[R[i].tl].push_back(i);
            scanD[R[i].tr + 1].push_back(i);
        }

        int lst = 0;
        for(int tt = 0; tt < N; ++tt){
            for(auto &u : scanA[tt]){
                upd(1 , 0 , M - 1 , revpos[u], -R[u].x);
            }
            for(auto &u : scanD[tt]){
                upd(1 , 0 , M - 1 , revpos[u], inf);
            }
            while(lst < q && que[qperm[lst]].se == tt){
                int f = qperm[lst];

                int l = 0 , r = sz(R) - 1;
                while(l != r){
                    int mid = (l + r) >> 1;
                    if(cords[que[f].fi] <= R[mid].bound){
                        if(l + 1 == r)
                            l = r;
                        else
                            l = mid;
                    }else
                        r = mid;
                }
                if(cords[que[f].fi] <= R[r].bound)
                    ++r;
                --r;
                /// so what do we say we say that suffix is GOOOD
                int tv;
                if(r == -1)
                    tv = inf;
                else
                    tv = get(1 , 0, M-1, 0 , r);

                if(tv == inf)
                    tv = inf;
                else
                    tv = cords[tv];
                tv *= -1;
                ans[f] = max(ans[f] , tv - cords[que[f].fi]);
                lst++;
            }
        }
    }
    for(int i = 0 ; i < q; ++i){
        if(ans[i] >= (int)1e8)
            cout << -1 << '\n';
        else
            cout << ans[i] << '\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 1

*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20