oj.uz

Submission #579459

# Submission time Handle Problem Language Result Execution time Memory
579459 2022-06-19T07:59:25 Z vovamr New Home (APIO18_new_home) C++17
100 / 100
 4636 ms 330552 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("-O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 1 << 20;

map<int,int> mp[N];
multiset<int> fe[N];
int t[N * 2];

int L, R;
inline void upd(int v, int vl, int vr, int pos, int type, int prev) {
        if (vl == vr) {
                if (mp[vl].find(type) == mp[vl].end()) {
                        mp[vl][type] = prev;
                        fe[vl].insert(prev);
                }
                else {
                        fe[vl].erase(fe[vl].find(mp[vl][type]));
                        mp[vl][type] = prev;
                        fe[vl].insert(prev);
                }
                t[v] = *fe[vl].begin();
                return;
        }
        int m = vl + vr >> 1;
        if (pos <= m) upd(2 * v + 1, vl, m, pos, type, prev);
        else upd(2 * v + 2, m + 1,vr, pos, type, prev);
        t[v] = min(t[2 * v + 1], t[2 * v + 2]);
}
inline void erase(int v, int vl, int vr, int pos, int type) {
        if (vl == vr) {
                fe[vl].erase(fe[vl].find(mp[vl][type]));
                mp[vl].erase(type);
                if (sz(fe[vl])) t[v] = *fe[vl].begin();
                else t[v] = iinf;
                return;
        }
        int m = vl + vr >> 1;
        if (pos <= m) erase(2 * v + 1, vl, m, pos, type);
        else erase(2 * v + 2, m + 1, vr, pos, type);
        t[v] = min(t[2 * v + 1], t[2 * v + 2]);
}
inline int get(int v, int vl, int vr, int l, int r) {
        if (vl == l && vr == r) return t[v];
        int m = vl + vr >> 1;
        if (r <= m) return get(2 * v + 1, vl, m, l, r);
        else if (l > m) return get(2 * v + 2, m + 1, vr, l, r);
        else return min(get(2 * v + 1, vl, m, l, m), get(2 * v + 2, m + 1, vr, m + 1, r));
}
inline int get(int l, int r) { if(l>r){return iinf;}return get(0, L, R, l, r); }
inline void upd(int pos, int type, int prev) { upd(0, L, R, pos, type, prev); }
inline void erase(int pos, int type) { erase(0, L, R, pos, type); }

const int M = 3e5 + 10;
ve<int> alt, al;
array<int,4> a[M];
array<int,2> f[M];
ve<pii> add[3 * M], del[3 * M], ask[3 * M];
map<int,int> g[M];
int res[M];

inline void solve() {
        fill(t, t + 2 * N, iinf); al.pb(-iinf);

        int n, k, q;
        cin >> n >> k >> q;
        for (int i = 0; i < n; ++i) {
                int x, t, l, r;
                cin >> x >> t >> l >> r;
                a[i] = {x, t, l, r};
                alt.pb(l);
                alt.pb(r + 1);
                al.pb(x);
        }
        for (int i = 0; i < q; ++i) {
                int x, t;
                cin >> x >> t;
                alt.pb(t);
                al.pb(x);
                f[i] = {x, t};
        }
        sort(all(alt));
        alt.erase(unique(all(alt)), alt.end());
        sort(all(al)); al.pb(iinf);
        al.erase(unique(all(al)), al.end());
        L = 0, R = sz(al) - 1;
        
        for (auto &[x, t, l, r] : a) {
                l = lower_bound(all(alt), l) - alt.begin();
                r = lower_bound(all(alt), r + 1) - alt.begin();
                x = lower_bound(all(al), x) - al.begin();
        }
        for (auto &[x, t] : f) {
                t = lower_bound(all(alt), t) - alt.begin();
                x = lower_bound(all(al), x) - al.begin();
        }
        
        int m = sz(alt);
        for (auto &[x, t, l, r] : a) {
                add[l].pb({x, t});
                del[r].pb({x, t});
        }
        for (int i = 0; i < q; ++i) {
                auto &[x, t] = f[i];
                ask[t].pb({x, i});
        }
        
        for (int type = 1; type <= k; ++type) add[0].pb({R, type});
        
        for (int curt = 0; curt < m; ++curt) {
                for (auto &[x, type] : add[curt]) {
                        auto it = g[type].upper_bound(x);
                        if (it != g[type].end()) upd(it->fi, type, x);
                        it = g[type].lower_bound(x);
                        if (it != g[type].begin()) {
                                --it;
                                upd(x, type, it->fi);
                        }
                        else upd(x, type, L);
                        ++g[type][x];
                }
                for (auto &[x, type] : del[curt]) {
                        --g[type][x];
                        if (!g[type][x]) g[type].erase(x);
                        
                        auto it = g[type].lower_bound(x);
                        
                        int prev = L;
                        if (it != g[type].begin()) {
                                --it;
                                prev = it->fi;
                        }
                        it = g[type].upper_bound(x);
                        if (g[type].count(x)) continue;
                        erase(x, type);
                        if (it != g[type].end()) upd(it->fi, type, prev);
                }
                for (auto &[x, id] : ask[curt]) {
                        int l = 0, r = 1e8 + 10, mid, ans = -1;
                        while (l <= r) {
                                mid = l + r >> 1;
                                
                                int re = upper_bound(all(al), al[x] + mid) - al.begin();
                                int f = get(re, R);
                                
                                if (f == iinf || al[f] >= al[x] - mid) ans = mid, r = mid - 1;
                                else l = mid + 1;
                        }
                        res[id] = ans;
                }
        }
        
        for (int i = 0; i < q; ++i) cout << res[i] << '\n';
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Compilation message

new_home.cpp: In function 'void upd(int, int, int, int, int, int)':
new_home.cpp:46:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |         int m = vl + vr >> 1;
      |                 ~~~^~~~
new_home.cpp: In function 'void erase(int, int, int, int, int)':
new_home.cpp:59:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |         int m = vl + vr >> 1;
      |                 ~~~^~~~
new_home.cpp: In function 'int get(int, int, int, int, int)':
new_home.cpp:66:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |         int m = vl + vr >> 1;
      |                 ~~~^~~~
new_home.cpp: In function 'void solve()':
new_home.cpp:162:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  162 |                                 mid = l + r >> 1;
      |                                       ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 197856 KB Output is correct
2 Correct 136 ms 197888 KB Output is correct
3 Correct 151 ms 197964 KB Output is correct
4 Correct 161 ms 197892 KB Output is correct
5 Correct 149 ms 197968 KB Output is correct
6 Correct 152 ms 197956 KB Output is correct
7 Correct 200 ms 197964 KB Output is correct
8 Correct 169 ms 197920 KB Output is correct
9 Correct 164 ms 197936 KB Output is correct
10 Correct 168 ms 197964 KB Output is correct
11 Correct 162 ms 197900 KB Output is correct
12 Correct 197 ms 197944 KB Output is correct
13 Correct 156 ms 198008 KB Output is correct
14 Correct 155 ms 198024 KB Output is correct
15 Correct 174 ms 197980 KB Output is correct
16 Correct 153 ms 197936 KB Output is correct
17 Correct 154 ms 197980 KB Output is correct
18 Correct 169 ms 198048 KB Output is correct
19 Correct 172 ms 197920 KB Output is correct
20 Correct 161 ms 197908 KB Output is correct
21 Correct 141 ms 197968 KB Output is correct
22 Correct 174 ms 197956 KB Output is correct
23 Correct 157 ms 197916 KB Output is correct
24 Correct 154 ms 197916 KB Output is correct
25 Correct 156 ms 197996 KB Output is correct
26 Correct 182 ms 198076 KB Output is correct
27 Correct 144 ms 197948 KB Output is correct
28 Correct 157 ms 198012 KB Output is correct
29 Correct 173 ms 197960 KB Output is correct
30 Correct 193 ms 198008 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 197856 KB Output is correct
2 Correct 136 ms 197888 KB Output is correct
3 Correct 151 ms 197964 KB Output is correct
4 Correct 161 ms 197892 KB Output is correct
5 Correct 149 ms 197968 KB Output is correct
6 Correct 152 ms 197956 KB Output is correct
7 Correct 200 ms 197964 KB Output is correct
8 Correct 169 ms 197920 KB Output is correct
9 Correct 164 ms 197936 KB Output is correct
10 Correct 168 ms 197964 KB Output is correct
11 Correct 162 ms 197900 KB Output is correct
12 Correct 197 ms 197944 KB Output is correct
13 Correct 156 ms 198008 KB Output is correct
14 Correct 155 ms 198024 KB Output is correct
15 Correct 174 ms 197980 KB Output is correct
16 Correct 153 ms 197936 KB Output is correct
17 Correct 154 ms 197980 KB Output is correct
18 Correct 169 ms 198048 KB Output is correct
19 Correct 172 ms 197920 KB Output is correct
20 Correct 161 ms 197908 KB Output is correct
21 Correct 141 ms 197968 KB Output is correct
22 Correct 174 ms 197956 KB Output is correct
23 Correct 157 ms 197916 KB Output is correct
24 Correct 154 ms 197916 KB Output is correct
25 Correct 156 ms 197996 KB Output is correct
26 Correct 182 ms 198076 KB Output is correct
27 Correct 144 ms 197948 KB Output is correct
28 Correct 157 ms 198012 KB Output is correct
29 Correct 173 ms 197960 KB Output is correct
30 Correct 193 ms 198008 KB Output is correct
31 Correct 781 ms 214220 KB Output is correct
32 Correct 234 ms 199544 KB Output is correct
33 Correct 814 ms 208832 KB Output is correct
34 Correct 783 ms 208888 KB Output is correct
35 Correct 792 ms 214156 KB Output is correct
36 Correct 894 ms 214184 KB Output is correct
37 Correct 684 ms 206404 KB Output is correct
38 Correct 660 ms 206264 KB Output is correct
39 Correct 629 ms 205768 KB Output is correct
40 Correct 621 ms 205712 KB Output is correct
41 Correct 544 ms 206036 KB Output is correct
42 Correct 587 ms 205748 KB Output is correct
43 Correct 190 ms 201532 KB Output is correct
44 Correct 633 ms 206172 KB Output is correct
45 Correct 579 ms 205816 KB Output is correct
46 Correct 560 ms 205776 KB Output is correct
47 Correct 497 ms 205268 KB Output is correct
48 Correct 493 ms 205272 KB Output is correct
49 Correct 575 ms 205552 KB Output is correct
50 Correct 547 ms 205644 KB Output is correct
51 Correct 526 ms 205420 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2605 ms 280224 KB Output is correct
2 Correct 3893 ms 268992 KB Output is correct
3 Correct 3123 ms 316272 KB Output is correct
4 Correct 2820 ms 286204 KB Output is correct
5 Correct 3883 ms 268500 KB Output is correct
6 Correct 3648 ms 268896 KB Output is correct
7 Correct 2751 ms 316172 KB Output is correct
8 Correct 2281 ms 286256 KB Output is correct
9 Correct 2341 ms 275824 KB Output is correct
10 Correct 3165 ms 270072 KB Output is correct
11 Correct 2477 ms 268244 KB Output is correct
12 Correct 2406 ms 269696 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3534 ms 278276 KB Output is correct
2 Correct 526 ms 211564 KB Output is correct
3 Correct 4396 ms 275888 KB Output is correct
4 Correct 3448 ms 321088 KB Output is correct
5 Correct 2746 ms 285148 KB Output is correct
6 Correct 2843 ms 291120 KB Output is correct
7 Correct 4168 ms 275308 KB Output is correct
8 Correct 4108 ms 275656 KB Output is correct
9 Correct 3180 ms 322364 KB Output is correct
10 Correct 2921 ms 288716 KB Output is correct
11 Correct 2814 ms 279976 KB Output is correct
12 Correct 3964 ms 276788 KB Output is correct
13 Correct 2275 ms 273664 KB Output is correct
14 Correct 2331 ms 272752 KB Output is correct
15 Correct 2564 ms 274804 KB Output is correct
16 Correct 2718 ms 276260 KB Output is correct
17 Correct 2693 ms 274320 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 197856 KB Output is correct
2 Correct 136 ms 197888 KB Output is correct
3 Correct 151 ms 197964 KB Output is correct
4 Correct 161 ms 197892 KB Output is correct
5 Correct 149 ms 197968 KB Output is correct
6 Correct 152 ms 197956 KB Output is correct
7 Correct 200 ms 197964 KB Output is correct
8 Correct 169 ms 197920 KB Output is correct
9 Correct 164 ms 197936 KB Output is correct
10 Correct 168 ms 197964 KB Output is correct
11 Correct 162 ms 197900 KB Output is correct
12 Correct 197 ms 197944 KB Output is correct
13 Correct 156 ms 198008 KB Output is correct
14 Correct 155 ms 198024 KB Output is correct
15 Correct 174 ms 197980 KB Output is correct
16 Correct 153 ms 197936 KB Output is correct
17 Correct 154 ms 197980 KB Output is correct
18 Correct 169 ms 198048 KB Output is correct
19 Correct 172 ms 197920 KB Output is correct
20 Correct 161 ms 197908 KB Output is correct
21 Correct 141 ms 197968 KB Output is correct
22 Correct 174 ms 197956 KB Output is correct
23 Correct 157 ms 197916 KB Output is correct
24 Correct 154 ms 197916 KB Output is correct
25 Correct 156 ms 197996 KB Output is correct
26 Correct 182 ms 198076 KB Output is correct
27 Correct 144 ms 197948 KB Output is correct
28 Correct 157 ms 198012 KB Output is correct
29 Correct 173 ms 197960 KB Output is correct
30 Correct 193 ms 198008 KB Output is correct
31 Correct 781 ms 214220 KB Output is correct
32 Correct 234 ms 199544 KB Output is correct
33 Correct 814 ms 208832 KB Output is correct
34 Correct 783 ms 208888 KB Output is correct
35 Correct 792 ms 214156 KB Output is correct
36 Correct 894 ms 214184 KB Output is correct
37 Correct 684 ms 206404 KB Output is correct
38 Correct 660 ms 206264 KB Output is correct
39 Correct 629 ms 205768 KB Output is correct
40 Correct 621 ms 205712 KB Output is correct
41 Correct 544 ms 206036 KB Output is correct
42 Correct 587 ms 205748 KB Output is correct
43 Correct 190 ms 201532 KB Output is correct
44 Correct 633 ms 206172 KB Output is correct
45 Correct 579 ms 205816 KB Output is correct
46 Correct 560 ms 205776 KB Output is correct
47 Correct 497 ms 205268 KB Output is correct
48 Correct 493 ms 205272 KB Output is correct
49 Correct 575 ms 205552 KB Output is correct
50 Correct 547 ms 205644 KB Output is correct
51 Correct 526 ms 205420 KB Output is correct
52 Correct 755 ms 222988 KB Output is correct
53 Correct 789 ms 217716 KB Output is correct
54 Correct 654 ms 217068 KB Output is correct
55 Correct 654 ms 211788 KB Output is correct
56 Correct 699 ms 214728 KB Output is correct
57 Correct 627 ms 207736 KB Output is correct
58 Correct 691 ms 211728 KB Output is correct
59 Correct 649 ms 214616 KB Output is correct
60 Correct 589 ms 207696 KB Output is correct
61 Correct 300 ms 218560 KB Output is correct
62 Correct 761 ms 223132 KB Output is correct
63 Correct 686 ms 217212 KB Output is correct
64 Correct 733 ms 214484 KB Output is correct
65 Correct 641 ms 208664 KB Output is correct
66 Correct 540 ms 206208 KB Output is correct
67 Correct 438 ms 203104 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 197856 KB Output is correct
2 Correct 136 ms 197888 KB Output is correct
3 Correct 151 ms 197964 KB Output is correct
4 Correct 161 ms 197892 KB Output is correct
5 Correct 149 ms 197968 KB Output is correct
6 Correct 152 ms 197956 KB Output is correct
7 Correct 200 ms 197964 KB Output is correct
8 Correct 169 ms 197920 KB Output is correct
9 Correct 164 ms 197936 KB Output is correct
10 Correct 168 ms 197964 KB Output is correct
11 Correct 162 ms 197900 KB Output is correct
12 Correct 197 ms 197944 KB Output is correct
13 Correct 156 ms 198008 KB Output is correct
14 Correct 155 ms 198024 KB Output is correct
15 Correct 174 ms 197980 KB Output is correct
16 Correct 153 ms 197936 KB Output is correct
17 Correct 154 ms 197980 KB Output is correct
18 Correct 169 ms 198048 KB Output is correct
19 Correct 172 ms 197920 KB Output is correct
20 Correct 161 ms 197908 KB Output is correct
21 Correct 141 ms 197968 KB Output is correct
22 Correct 174 ms 197956 KB Output is correct
23 Correct 157 ms 197916 KB Output is correct
24 Correct 154 ms 197916 KB Output is correct
25 Correct 156 ms 197996 KB Output is correct
26 Correct 182 ms 198076 KB Output is correct
27 Correct 144 ms 197948 KB Output is correct
28 Correct 157 ms 198012 KB Output is correct
29 Correct 173 ms 197960 KB Output is correct
30 Correct 193 ms 198008 KB Output is correct
31 Correct 781 ms 214220 KB Output is correct
32 Correct 234 ms 199544 KB Output is correct
33 Correct 814 ms 208832 KB Output is correct
34 Correct 783 ms 208888 KB Output is correct
35 Correct 792 ms 214156 KB Output is correct
36 Correct 894 ms 214184 KB Output is correct
37 Correct 684 ms 206404 KB Output is correct
38 Correct 660 ms 206264 KB Output is correct
39 Correct 629 ms 205768 KB Output is correct
40 Correct 621 ms 205712 KB Output is correct
41 Correct 544 ms 206036 KB Output is correct
42 Correct 587 ms 205748 KB Output is correct
43 Correct 190 ms 201532 KB Output is correct
44 Correct 633 ms 206172 KB Output is correct
45 Correct 579 ms 205816 KB Output is correct
46 Correct 560 ms 205776 KB Output is correct
47 Correct 497 ms 205268 KB Output is correct
48 Correct 493 ms 205272 KB Output is correct
49 Correct 575 ms 205552 KB Output is correct
50 Correct 547 ms 205644 KB Output is correct
51 Correct 526 ms 205420 KB Output is correct
52 Correct 2605 ms 280224 KB Output is correct
53 Correct 3893 ms 268992 KB Output is correct
54 Correct 3123 ms 316272 KB Output is correct
55 Correct 2820 ms 286204 KB Output is correct
56 Correct 3883 ms 268500 KB Output is correct
57 Correct 3648 ms 268896 KB Output is correct
58 Correct 2751 ms 316172 KB Output is correct
59 Correct 2281 ms 286256 KB Output is correct
60 Correct 2341 ms 275824 KB Output is correct
61 Correct 3165 ms 270072 KB Output is correct
62 Correct 2477 ms 268244 KB Output is correct
63 Correct 2406 ms 269696 KB Output is correct
64 Correct 3534 ms 278276 KB Output is correct
65 Correct 526 ms 211564 KB Output is correct
66 Correct 4396 ms 275888 KB Output is correct
67 Correct 3448 ms 321088 KB Output is correct
68 Correct 2746 ms 285148 KB Output is correct
69 Correct 2843 ms 291120 KB Output is correct
70 Correct 4168 ms 275308 KB Output is correct
71 Correct 4108 ms 275656 KB Output is correct
72 Correct 3180 ms 322364 KB Output is correct
73 Correct 2921 ms 288716 KB Output is correct
74 Correct 2814 ms 279976 KB Output is correct
75 Correct 3964 ms 276788 KB Output is correct
76 Correct 2275 ms 273664 KB Output is correct
77 Correct 2331 ms 272752 KB Output is correct
78 Correct 2564 ms 274804 KB Output is correct
79 Correct 2718 ms 276260 KB Output is correct
80 Correct 2693 ms 274320 KB Output is correct
81 Correct 755 ms 222988 KB Output is correct
82 Correct 789 ms 217716 KB Output is correct
83 Correct 654 ms 217068 KB Output is correct
84 Correct 654 ms 211788 KB Output is correct
85 Correct 699 ms 214728 KB Output is correct
86 Correct 627 ms 207736 KB Output is correct
87 Correct 691 ms 211728 KB Output is correct
88 Correct 649 ms 214616 KB Output is correct
89 Correct 589 ms 207696 KB Output is correct
90 Correct 300 ms 218560 KB Output is correct
91 Correct 761 ms 223132 KB Output is correct
92 Correct 686 ms 217212 KB Output is correct
93 Correct 733 ms 214484 KB Output is correct
94 Correct 641 ms 208664 KB Output is correct
95 Correct 540 ms 206208 KB Output is correct
96 Correct 438 ms 203104 KB Output is correct
97 Correct 4359 ms 330104 KB Output is correct
98 Correct 541 ms 213748 KB Output is correct
99 Correct 4364 ms 258268 KB Output is correct
100 Correct 4070 ms 303460 KB Output is correct
101 Correct 3774 ms 300152 KB Output is correct
102 Correct 4636 ms 285008 KB Output is correct
103 Correct 3263 ms 246164 KB Output is correct
104 Correct 3313 ms 245556 KB Output is correct
105 Correct 2668 ms 242860 KB Output is correct
106 Correct 2700 ms 242988 KB Output is correct
107 Correct 3028 ms 272840 KB Output is correct
108 Correct 3264 ms 286200 KB Output is correct
109 Correct 2792 ms 253460 KB Output is correct
110 Correct 2955 ms 273344 KB Output is correct
111 Correct 3368 ms 287716 KB Output is correct
112 Correct 2631 ms 253092 KB Output is correct
113 Correct 1035 ms 307828 KB Output is correct
114 Correct 4075 ms 330552 KB Output is correct
115 Correct 3860 ms 301136 KB Output is correct
116 Correct 3719 ms 287104 KB Output is correct
117 Correct 3273 ms 258664 KB Output is correct
118 Correct 2654 ms 245636 KB Output is correct
119 Correct 2119 ms 230320 KB Output is correct
120 Correct 1722 ms 239832 KB Output is correct
121 Correct 1987 ms 241688 KB Output is correct
122 Correct 2063 ms 241332 KB Output is correct
123 Correct 2045 ms 242564 KB Output is correct
124 Correct 2094 ms 243080 KB Output is correct
125 Correct 2309 ms 242672 KB Output is correct
126 Correct 2160 ms 243400 KB Output is correct