Submission #406286

#	Time	Username	Problem	Language	Result	Execution time	Memory
406286		cheissmart	New Home (APIO18_new_home)	C++14	0 / 100	5072 ms	174248 KiB

new_home

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif

const int INF = 1e9 + 7, N = 1e6 + 7;


/*
    Multiset using splay tree
    Verification: https://loj.ac/s/1129334
*/

struct Splay_tree {
    struct node {
        int val, cnt, sz;
        node *c[2], *p;
        node(int _val, node* _p = nullptr) { 
            val = _val, sz = cnt = 1;
            c[0] = c[1] = nullptr, p = _p;
        }
    };
    node* root;
    Splay_tree() {
        root = nullptr;
    }
    int sz(node* v) { return v ? v -> sz : 0; }
    int dir(node* v) {
        if(v -> p) return v -> p -> c[0] == v ? 0 : 1;
        return 0;
    }
    void pull(node* v) {
        v -> sz = v -> cnt + sz(v -> c[0]) + sz(v -> c[1]);
    }
    void link(node* p, node* v, int dir) {
        if(p) p -> c[dir] = v;
        if(v) v -> p = p;
    }
    void rot(node* v) { // rotate v up
        node* p = v -> p, *g = p -> p;
        int d = dir(v), dd = dir(p);
        node* b = v -> c[d ^ 1];
        link(g, v, dd), link(v, p, d ^ 1), link(p, b, d);
        pull(p), pull(v); // order matters!!
    }
    void splay(node *v) {
        while(v -> p) {
            if(!(v -> p -> p)) rot(v); // zig
            else if(dir(v) != dir(v -> p)) rot(v), rot(v); // zig-zag
            else rot(v -> p), rot(v); // zig-zig
        }
        root = v;
    }
    node* pre() {
        node* v = root -> c[0];
        if(!v) return v;
        while(v -> c[1]) v = v -> c[1];
        return v;
    }
    node* nxt() {
        node* v = root -> c[1];
        if(!v) return v;
        while(v -> c[0]) v = v -> c[0];
        return v;
    }
    void insert(int val) {
        if(!root) {
            root = new node(val);
            return;
        }
        node* ptr = root, *lst;
        while(ptr) {
            lst = ptr;
            if(ptr -> val == val) break;
            else if(val < ptr -> val) ptr = ptr -> c[0];
            else ptr = ptr -> c[1];
        }
        if(ptr) ptr -> cnt++;
        else lst -> c[val > lst -> val] = ptr = new node(val, lst);
        splay(ptr);
    }
    void erase(int val) {
        node* v = find(val); // v is now the root
        if(!v) return;
        v -> cnt--;
        if(v -> cnt) pull(v);
        else {
            if(!v -> c[0] && !v -> c[1]) return root = nullptr, void(0);
            if(!v -> c[0]) return root = v -> c[1], root -> p = nullptr, void(0);
            node* x = pre();
            splay(x);
            link(x, v -> c[1], 1);
        }
    }
    node* find(int val) {
        if(!root) return nullptr;
        node* ptr = root, *lst;
        while(ptr && ptr -> val != val) {
            lst = ptr;
            if(val < ptr -> val) ptr = ptr -> c[0];
            else ptr = ptr -> c[1];
        }
        if(ptr) splay(ptr);
        else splay(lst);
        return ptr;
    }
    int order_of_key(int val) {
        if(!root) return 0;
        node* ptr = root, *lst;
        int ans = 0;
        while(ptr) {
            lst = ptr;
            if(val <= ptr -> val) ptr = ptr -> c[0];
            else ans += sz(ptr -> c[0]) + ptr -> cnt, ptr = ptr -> c[1];
        }
        if(ptr) splay(ptr);
        else splay(lst);
        return ans;
    }
    int find_by_order(int val) {
        assert(val < size());
        node* ptr = root;
        while(true) {
            if(sz(ptr -> c[0]) > val) ptr = ptr -> c[0];
            else if(sz(ptr -> c[0]) + ptr -> cnt <= val) val -= (sz(ptr -> c[0]) + ptr -> cnt), ptr = ptr -> c[1];
            else {
                splay(ptr);
                return ptr -> val;
            }
        }
    }
    int size() { return sz(root); }
    int count(int val) {
        node* v = find(val);
        return v ? v -> cnt : 0;
    }
};


V<pi> G[N];
int ans[N], n, k, q;
vi compress_x, compress_t;


struct DS {
	static const int N = 3e5 + 7;
	Splay_tree bit[N];
	void insert(int pos, int val) {
		pos++;
		for(; pos < N; pos += pos & -pos)
			bit[pos].insert(val);
	}
	int qry(int pos, int less_than) {
		pos++;
		int cnt = 0;
		for(; pos; pos -= pos & -pos)
			cnt += bit[pos].order_of_key(less_than);
		return cnt;
	}
	int qry(int pos){
		auto ok = [&] (int d) {
			// [pos - d, pos + d]
			int lb = lower_bound(ALL(compress_x), pos - d) - compress_x.begin();
			int rb = upper_bound(ALL(compress_x), pos + d) - compress_x.begin() - 1;
			return qry(rb, lb) - qry(lb - 1, lb) == k;
		};
		int lb = 0, rb = 1e8;
		while(lb <= rb) {
			int mb = (lb + rb) / 2;
			if(ok(mb)) rb = mb - 1;
			else lb = mb + 1;
		}
		if(lb > 1e8) lb = -1;
		return lb;
	}
} ds;

struct tseg {
	struct node {

	};
	void upd(int l, int r, int x, int pre) {

	}
} tseg;

signed main()
{
	IO_OP;

	cin >> n >> k >> q;
	V<array<int, 4>> stores;	
	for(int i = 0; i < n; i++) {
		int x, type, tl, tr;
		cin >> x >> type >> tl >> tr;
		stores.PB({x, type, tl, tr});
		compress_x.PB(x), compress_t.PB(tl), compress_t.PB(tr);
	}
	V<pi> qq;
	for(int i = 0; i < q; i++) {
		int x, t;
		cin >> x >> t;
		compress_t.PB(t);
		qq.EB(x, t);
	}
	sort(ALL(compress_x));
	compress_x.resize(unique(ALL(compress_x)) - compress_x.begin());
	sort(ALL(compress_t));
	compress_t.resize(unique(ALL(compress_t)) - compress_t.begin());
	auto get_x = [&] (int x) {
		return int(lower_bound(ALL(compress_x), x) - compress_x.begin());
	};
	auto get_t = [&] (int t) {
		return int(lower_bound(ALL(compress_t), t) - compress_t.begin());
	};
	sort(ALL(stores));
	map<int, int> mp;
	for(auto p:stores) {
		int x = get_x(p[0]), type = p[1], tl = get_t(p[2]), tr = get_t(p[3]);
		int pre = (mp.count(type) ? mp[type] : -1);
		//tseg.upd(tl, tr + 1, x, pre);
		ds.insert(x, pre);
		mp[type] = x;
	}

	for(int i = 0; i < int(qq.size()); i++) {
		pi p = qq[i];
		int x = p.F, t = get_t(p.S);
		// G[t].EB(i, x);
		ans[i] = ds.qry(x);
	}

	for(int i = 0; i < q; i++)
		cout << ans[i] << '\n';

}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:243:37: warning: unused variable 'tl' [-Wunused-variable]
  243 |   int x = get_x(p[0]), type = p[1], tl = get_t(p[2]), tr = get_t(p[3]);
      |                                     ^~
new_home.cpp:243:55: warning: unused variable 'tr' [-Wunused-variable]
  243 |   int x = get_x(p[0]), type = p[1], tl = get_t(p[2]), tr = get_t(p[3]);
      |                                                       ^~
new_home.cpp:252:16: warning: unused variable 't' [-Wunused-variable]
  252 |   int x = p.F, t = get_t(p.S);
      |                ^

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