oj.uz

답안 #487787

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
487787 2021-11-16T16:14:53 Z Redhood 새 집 (APIO18_new_home) C++14
10 / 100
 1754 ms 223544 KB 
#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)6e5 + 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;
    }


        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]});
        }

    if(k <= 400 && !ONE && false){



        /// 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]);
        }


        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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 37800 KB Output is correct
2 Correct 17 ms 37876 KB Output is correct
3 Correct 18 ms 37836 KB Output is correct
4 Runtime error 44 ms 76616 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 37800 KB Output is correct
2 Correct 17 ms 37876 KB Output is correct
3 Correct 18 ms 37836 KB Output is correct
4 Runtime error 44 ms 76616 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1754 ms 94976 KB Output is correct
2 Correct 1247 ms 101036 KB Output is correct
3 Correct 1461 ms 133120 KB Output is correct
4 Correct 1612 ms 112196 KB Output is correct
5 Correct 1226 ms 100916 KB Output is correct
6 Correct 1209 ms 101024 KB Output is correct
7 Correct 1318 ms 133104 KB Output is correct
8 Correct 1389 ms 111924 KB Output is correct
9 Correct 1443 ms 105376 KB Output is correct
10 Correct 1312 ms 102024 KB Output is correct
11 Correct 929 ms 100432 KB Output is correct
12 Correct 1090 ms 101572 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1297 ms 223544 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 37800 KB Output is correct
2 Correct 17 ms 37876 KB Output is correct
3 Correct 18 ms 37836 KB Output is correct
4 Runtime error 44 ms 76616 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 37800 KB Output is correct
2 Correct 17 ms 37876 KB Output is correct
3 Correct 18 ms 37836 KB Output is correct
4 Runtime error 44 ms 76616 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -