oj.uz

Submission #487808

# Submission time Handle Problem Language Result Execution time Memory
487808 2021-11-16T17:23:16 Z Redhood New Home (APIO18_new_home) C++14
45 / 100
 2260 ms 196324 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)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.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94148 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 51 ms 94328 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1811 ms 18636 KB Output is correct
32 Correct 83 ms 5568 KB Output is correct
33 Correct 190 ms 16780 KB Output is correct
34 Correct 1427 ms 16876 KB Output is correct
35 Correct 823 ms 18556 KB Output is correct
36 Correct 225 ms 18440 KB Output is correct
37 Correct 175 ms 15936 KB Output is correct
38 Correct 122 ms 15808 KB Output is correct
39 Correct 105 ms 15624 KB Output is correct
40 Correct 107 ms 15620 KB Output is correct
41 Correct 255 ms 15864 KB Output is correct
42 Correct 227 ms 15804 KB Output is correct
43 Correct 130 ms 102280 KB Output is correct
44 Correct 217 ms 15888 KB Output is correct
45 Correct 136 ms 15888 KB Output is correct
46 Correct 90 ms 15804 KB Output is correct
47 Correct 80 ms 15164 KB Output is correct
48 Correct 76 ms 15000 KB Output is correct
49 Correct 91 ms 15320 KB Output is correct
50 Correct 184 ms 15496 KB Output is correct
51 Correct 85 ms 15356 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1660 ms 151276 KB Output is correct
2 Correct 1259 ms 144836 KB Output is correct
3 Correct 1473 ms 175648 KB Output is correct
4 Correct 1530 ms 154856 KB Output is correct
5 Correct 1256 ms 144900 KB Output is correct
6 Correct 1225 ms 144756 KB Output is correct
7 Correct 1293 ms 175756 KB Output is correct
8 Correct 1407 ms 154504 KB Output is correct
9 Correct 1451 ms 148180 KB Output is correct
10 Correct 1349 ms 145364 KB Output is correct
11 Correct 944 ms 145904 KB Output is correct
12 Correct 1106 ms 146852 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2260 ms 166792 KB Output is correct
2 Correct 725 ms 131296 KB Output is correct
3 Correct 2114 ms 165964 KB Output is correct
4 Correct 1296 ms 196304 KB Output is correct
5 Correct 1368 ms 171784 KB Output is correct
6 Correct 1367 ms 175500 KB Output is correct
7 Correct 2040 ms 165860 KB Output is correct
8 Correct 2088 ms 165904 KB Output is correct
9 Correct 1318 ms 196324 KB Output is correct
10 Correct 1772 ms 173172 KB Output is correct
11 Correct 2138 ms 167828 KB Output is correct
12 Correct 2126 ms 166500 KB Output is correct
13 Correct 1142 ms 164208 KB Output is correct
14 Correct 1091 ms 163376 KB Output is correct
15 Correct 1255 ms 164760 KB Output is correct
16 Correct 1476 ms 165824 KB Output is correct
17 Correct 1254 ms 164448 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94148 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 51 ms 94328 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1811 ms 18636 KB Output is correct
32 Correct 83 ms 5568 KB Output is correct
33 Correct 190 ms 16780 KB Output is correct
34 Correct 1427 ms 16876 KB Output is correct
35 Correct 823 ms 18556 KB Output is correct
36 Correct 225 ms 18440 KB Output is correct
37 Correct 175 ms 15936 KB Output is correct
38 Correct 122 ms 15808 KB Output is correct
39 Correct 105 ms 15624 KB Output is correct
40 Correct 107 ms 15620 KB Output is correct
41 Correct 255 ms 15864 KB Output is correct
42 Correct 227 ms 15804 KB Output is correct
43 Correct 130 ms 102280 KB Output is correct
44 Correct 217 ms 15888 KB Output is correct
45 Correct 136 ms 15888 KB Output is correct
46 Correct 90 ms 15804 KB Output is correct
47 Correct 80 ms 15164 KB Output is correct
48 Correct 76 ms 15000 KB Output is correct
49 Correct 91 ms 15320 KB Output is correct
50 Correct 184 ms 15496 KB Output is correct
51 Correct 85 ms 15356 KB Output is correct
52 Incorrect 296 ms 119164 KB Output isn't correct
53 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94148 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 51 ms 94328 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1811 ms 18636 KB Output is correct
32 Correct 83 ms 5568 KB Output is correct
33 Correct 190 ms 16780 KB Output is correct
34 Correct 1427 ms 16876 KB Output is correct
35 Correct 823 ms 18556 KB Output is correct
36 Correct 225 ms 18440 KB Output is correct
37 Correct 175 ms 15936 KB Output is correct
38 Correct 122 ms 15808 KB Output is correct
39 Correct 105 ms 15624 KB Output is correct
40 Correct 107 ms 15620 KB Output is correct
41 Correct 255 ms 15864 KB Output is correct
42 Correct 227 ms 15804 KB Output is correct
43 Correct 130 ms 102280 KB Output is correct
44 Correct 217 ms 15888 KB Output is correct
45 Correct 136 ms 15888 KB Output is correct
46 Correct 90 ms 15804 KB Output is correct
47 Correct 80 ms 15164 KB Output is correct
48 Correct 76 ms 15000 KB Output is correct
49 Correct 91 ms 15320 KB Output is correct
50 Correct 184 ms 15496 KB Output is correct
51 Correct 85 ms 15356 KB Output is correct
52 Correct 1660 ms 151276 KB Output is correct
53 Correct 1259 ms 144836 KB Output is correct
54 Correct 1473 ms 175648 KB Output is correct
55 Correct 1530 ms 154856 KB Output is correct
56 Correct 1256 ms 144900 KB Output is correct
57 Correct 1225 ms 144756 KB Output is correct
58 Correct 1293 ms 175756 KB Output is correct
59 Correct 1407 ms 154504 KB Output is correct
60 Correct 1451 ms 148180 KB Output is correct
61 Correct 1349 ms 145364 KB Output is correct
62 Correct 944 ms 145904 KB Output is correct
63 Correct 1106 ms 146852 KB Output is correct
64 Correct 2260 ms 166792 KB Output is correct
65 Correct 725 ms 131296 KB Output is correct
66 Correct 2114 ms 165964 KB Output is correct
67 Correct 1296 ms 196304 KB Output is correct
68 Correct 1368 ms 171784 KB Output is correct
69 Correct 1367 ms 175500 KB Output is correct
70 Correct 2040 ms 165860 KB Output is correct
71 Correct 2088 ms 165904 KB Output is correct
72 Correct 1318 ms 196324 KB Output is correct
73 Correct 1772 ms 173172 KB Output is correct
74 Correct 2138 ms 167828 KB Output is correct
75 Correct 2126 ms 166500 KB Output is correct
76 Correct 1142 ms 164208 KB Output is correct
77 Correct 1091 ms 163376 KB Output is correct
78 Correct 1255 ms 164760 KB Output is correct
79 Correct 1476 ms 165824 KB Output is correct
80 Correct 1254 ms 164448 KB Output is correct
81 Incorrect 296 ms 119164 KB Output isn't correct
82 Halted 0 ms 0 KB -