Submission #579459

#	Time	Username	Problem	Language	Result	Execution time	Memory
579459		vovamr	New Home (APIO18_new_home)	C++17	100 / 100	4636 ms	330552 KiB

new_home

#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 (stderr)

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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20