Submission #487808

#	Time	Username	Problem	Language	Result	Execution time	Memory
487808		Redhood	New Home (APIO18_new_home)	C++14	45 / 100	2260 ms	196324 KiB

new_home

#include<bits/stdc++.h>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define sz(x) (int)(x).size()
typedef long long ll;
typedef long double ld;
using namespace std;
 
const int N = (int)1.5e6 + 10;
const int inf = 1e9;
struct seg{
    int a[4*N];
    int p[4*N];
    void clr(int x = inf){
        fill(a , a + 4 * N , x);
        fill(p , p + 4 * N , x);
    }
    void push(int v){
        int v1 = v << 1;
        for(auto u : {v1 , v1|1}){
            a[u] = min(a[u] , p[v]);
            p[u] = min(p[u] , p[v]);
        }
        p[v] = inf;
    }
    int get(int v , int tl , int tr , int l , int r){
        if(tl == l && tr == r){
            return a[v];
        }
        int mid = (tl + tr) >> 1 , v1 = v << 1;
        push(v);
        int ans = inf;
        if(l <= mid)
            ans = min(ans , get(v1, tl , mid , l , r));
        if(r > mid)
            ans = min(ans , get(v1 | 1,  mid + 1 , tr , max(l , mid + 1), r));
        return ans;
    }
    void upd(int v , int tl , int tr , int l , int r , int val){
        if(tl == l && tr == r){
            p[v] = min(p[v] , val);
            a[v] = min(a[v] , val);
            return;
        }
        int mid = (tl + tr) >> 1 , v1 = v << 1;
        push(v);
        if(l <= mid)
            upd(v1 , tl , mid , l , min(r , mid) , val);
        if(r > mid)
            upd(v1 | 1 , mid + 1 , tr , max(l , mid + 1) , r, val);
        a[v] = min(a[v1] , a[v1|1]);
    }
}MN,MX;
 
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n , k , q;
    cin >> n >> k >> q;
    vector < int > x(n), t(n), a(n), b(n);
 
 
    vector < int > zipyear;
    for(int i = 0; i < n; ++i){
        cin >> x[i] >> t[i] >> a[i] >> b[i];
        b[i]++;
        zipyear.pb(a[i]), zipyear.pb(b[i]);
    }
 
 
    vector < pair < int , int >>  que(q);
    for(auto &i : que){
        cin >> i.fi >> i.se;
        zipyear.pb(i.se);
    }
    sort(all(zipyear)), zipyear.erase(unique(all(zipyear)), zipyear.end());
    for(int i = 0; i < n; ++i){
        a[i] = lower_bound(all(zipyear), a[i]) - zipyear.begin();
        b[i] = lower_bound(all(zipyear), b[i]) - zipyear.begin();
    }
    for(int i = 0; i < q; ++i){
        que[i].se = lower_bound(all(zipyear), que[i].se) - zipyear.begin();
    }
    vector < int > answer(q, -1);
 
    vector < pair < int , int > > pr;
    for(int i = 0; i < q; ++i)
        pr.pb({que[i].se, i});
    sort(all(pr));
        multiset < int > type[k + 1];
        int year = -1;
 
                vector < pair < int , int >  > open[sz(zipyear) + 1];
        vector < pair < int , int > > close[sz(zipyear) + 1];
 
 
    bool ONE  = 1;
    for(int i = 0; i < n; ++i){
        if(a[i] != 0)
            ONE = 0;
    }
 
 

 
    if(k <= 400 && !ONE){
 
        for(int i = 0; i < n; ++i){
            open[a[i]].push_back({t[i], x[i]});
            close[b[i]].push_back({t[i], x[i]});
        } 
 
        /// inc
        for(auto &i : pr){
            while(year + 1 <= i.fi){
                /// lol
                for(auto &shop : open[year + 1]){
                    type[shop.fi].insert(shop.se);
                }
                /// lol
                for(auto &shop : close[year + 1]){
                    type[shop.fi].erase(type[shop.fi].find(shop.se));
                }
                year++;
            }
            int ans = -1;
 
//
//            cout << "LOL " << i.fi << ' ' << "\n";
//            for(int t  =1 ;t <=k; ++t){
//                cout << "TYPE " << t << '\n';
//                for(auto &u : type[t])
//                    cout << u << ' ';
//                cout << endl;
//            }
 
            for(int t = 1;t <= k; ++t){
                if(type[t].empty()){
                    ans = -1;
                    break;
                }
                int dist = 1e9;
                auto it = type[t].lower_bound(que[i.se].fi);
                if(it != type[t].end())
                    dist = min(dist , *it - que[i.se].fi);
                if(it != type[t].begin()){
                    --it;
                    dist = min(dist , que[i.se].fi - *it);
                }
                ans = max(ans , dist);
            }
            answer[i.se] = ans;
        }
    }else if(true){
        vector < int > cord;
        cord = x;
        for(auto &i : que)
            cord.pb(i.fi);
        sort(all(cord));
        cord.erase(unique(all(cord)) , cord.end());
 
        MN.clr(), MX.clr();
        for(int i = 0; i < sz(cord); ++i){
            MN.upd(1 , 0 , N-1, i , i , cord[i]);
            MX.upd(1 , 0 , N-1, i , i , -cord[i]);
        }
        vector < int > pos[k + 1];
        for(int i =  0 ; i< n; ++i){
            x[i] = lower_bound(all(cord), x[i]) - cord.begin();
            pos[t[i]].pb(x[i]);
        }
 
        for(int i = 0; i < n; ++i){
            open[a[i]].push_back({t[i], x[i]});
            close[b[i]].push_back({t[i], x[i]});
        }

 
        auto put = [&](int L , int R){
                if(L == R){
                    MN.upd(1 , 0, N-1 , L, L, cord[L]);
                    MX.upd(1 , 0, N-1 , L, L, -cord[L]);
                    return;
                }
                int l = L;
                int r = R;
                if(L > R)
                    assert(false);
                while(l != r){
//                    cout << l << ' ' << r << endl;
                    int m = (l + r) >> 1;
                    if(cord[m] - cord[L] <= cord[R] - cord[m]){
                        if(l + 1 == r)
                            l = r;
                        else
                            l = m;
                    }else
                        r = m;
                }
//                if(r - 1 < L)assert(false);
//                if(r > R)assert(false);
//                assert(r -  1 >= L);
//                assert(r + 1 <= R);
 
                MN.upd(1 , 0 , N - 1 , L , r - 1, cord[L]);
                MX.upd(1 , 0 , N - 1 , r , R , -cord[R]);
        };
        auto putbegin = [&](int X){
            MX.upd(1 , 0 , N-1, 0 , X, -cord[X]);
        };
        auto putend = [&](int X){
            MN.upd(1 , 0 , N - 1 , X , sz(cord) - 1,  cord[X]);
        };
        auto gt = [&](int X){
            assert(X >= 0 && X < sz(cord));
            int val = MN.get(1 , 0 , N - 1 , X , X);
            int val1 = MX.get(1 , 0 , N-1 , X , X);
 
            return max((cord[X]-val), -val1 - cord[X]);
        };
 
        for(int t = 1; t <= k; ++t){
            sort(all(pos[t]));
            /// 0
            if(pos[t].empty())
                continue;
            putbegin(pos[t][0]);
            putend(pos[t].back());
 
            for(int i = 0; i < sz(pos[t]) - 1; ++i){
                put(pos[t][i], pos[t][i+ 1]);
            }
 
        }
        bool done = 0;
 
//                cout << "HERE\n";
//        return 0;
        vector < int > diff(k + 1);
        for(int i = 0; i < n; ++i)
            diff[t[i]] = 1;
        for(int t = 1; t <= k; ++t){
            if(!diff[t]){
                for(int i = 0 ; i < q; ++i)
                    cout << -1 << '\n';
                return 0;
            }
        }
        for(auto &i : pr){
            while(year + 1 <= i.fi){
                /// lol
                for(auto &shop : open[year + 1]){
                    type[shop.fi].insert(shop.se);
                }
                /// lol
                for(auto &shop : close[year + 1]){
 
 
 
                    type[shop.fi].erase(type[shop.fi].find(shop.se));
 
 
                    if(type[shop.fi].empty()){
                        done = 1;
                        break;
                    }
                    auto it = type[shop.fi].lower_bound(shop.se);
 
                    if(it != type[shop.fi].begin() && it != type[shop.fi].end()){
                        auto it1 = it;it1--;
                        put(*it1 , *it);
                    }else{
                        if(it == type[shop.fi].end()){
                            --it;
                            putend(*it);
                        }else{
                            putbegin(*it);
                        }
                    }
                }
                if(done)
                    break;
                year++;
            }
            if(done)
                break;
//            cout << " ITTER " << i.fi << ' ' << year << endl;
//
//            cout << "YEAR\n";
//            for(int t = 1; t <= k; ++t){
//                cout << "SZ " << t << ' ' << type[t].size() << endl;
//            }
//            cout << "LOL\n";
            int ps = lower_bound(all(cord) , que[i.se].fi) - cord.begin();
            answer[i.se] = gt(ps);
        }
 
 
 
    }
    for(int i = 0 ; i < q; ++i)
        cout << answer[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 1 6
1 3
1 5
1 7
 
 
1 1 1
100000000 1 1 1
1 1
 
 
*/

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