답안 #106990

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
106990	2019-04-21T12:06:57 Z	polyfish	새 집 (APIO18_new_home)	C++14	10 / 100	5000 ms	623940 KB

new_home

//Pantyhose(black) + glasses = infinity

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "new_home"

const int MAX_N = 300002;
const int INF = 1e9+100;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct segment_tree {

    int n;
    vector<int> st;

    void init(int _n) {
        n = _n;
        st.resize(4*n);
    }

    void upd(int pos, int val, int l, int r, int idx) {
        if (pos<l || pos>r)
            return;

        if (l==r) {
            st[idx] = val;
            return;
        }

        int mid = (l + r) / 2;
        upd(pos, val, l, mid, idx*2);
        upd(pos, val, mid+1, r, idx*2+1);

        st[idx] = max(st[idx*2], st[idx*2+1]);
    }

    bool get(int u, int v, int val, int l, int r, int idx) {
        if (v<l || u>r || st[idx]<=val)
            return true;

        if (u<=l && r<=v)
            return st[idx]<=val;

        int mid = (l + r) / 2;
        return get(u, v, val, mid+1, r, idx*2+1) && get(u, v, val, l, mid, idx*2);
    }

    void upd(int pos, int val) {
        upd(pos, val, 1, n, 1);
    }

    bool get(int u, int v, int val) {
        return get(u, v, val, 1, n, 1);
    }

};

struct store {
	int x, t, a, b;
};

struct query {
	int l, y;
};

int n, k, nQueries, res[MAX_N], idx[100000002], max_x;
vector<int> T, L, store_event[MAX_N*3], q[MAX_N*3];
store s[MAX_N];
query Q[MAX_N];
map<int, int> pos[MAX_N*3];
multiset<int> g[MAX_N*2];
segment_tree tr;

int read_int() {
    char c;

    for (c = getchar(); c<'0' || c>'9'; c = getchar());

    int res = c - '0';

    for (c = getchar(); '0'<=c && c<='9'; c = getchar())
        res = res * 10 + c - '0';

    return res;
}

void read_input() {
	n = read_int();
	k = read_int();
	nQueries = read_int();

	for (int i=1; i<=n; ++i) {
        s[i].x = read_int();
        s[i].t = read_int();
        s[i].a = read_int();
        s[i].b = read_int();
	}

	for (int i=1; i<=nQueries; ++i) {
		Q[i].l = read_int();
		Q[i].y = read_int();
	}
}

void compress() {
    L.push_back(-INF);
    L.push_back(INF);

	for (int i=1; i<=n; ++i) {
		T.push_back(s[i].a);
		T.push_back(s[i].b+1);
		L.push_back(s[i].x);
	}

	for (int i=1; i<=nQueries; ++i) {
		T.push_back(Q[i].y);
	}

	#define uniq(P) {sort(P.begin(), P.end()); P.resize(unique(P.begin(), P.end()) - P.begin());}
    uniq(T);
    uniq(L);
	#undef uniq

	#define get_pos(P, x) lower_bound(P.begin(), P.end(), x) - P.begin() + 1
	for (int i=1; i<=n; ++i) {
		s[i].a = get_pos(T, s[i].a);
		s[i].b = get_pos(T, s[i].b+1);
		s[i].x = get_pos(L, s[i].x);
	}

	for (int i=1; i<=nQueries; ++i) {
		Q[i].y = get_pos(T, Q[i].y);
//		Q[i].l = get_pos(L, Q[i].l);
	}
	#undef uniq

	max_x = L[L.size()-2];
}

void init() {
    tr.init(L.size());

	for (int i=1; i<=n; ++i) {
		store_event[s[i].a].push_back(i);
		store_event[s[i].b].push_back(-i);
	}

	for (int i=1; i<=nQueries; ++i) {
		q[Q[i].y].push_back(i);
	}

	for (int i=1; i<=k; ++i) {
		++pos[i][1];
		++pos[i][L.size()];
        g[1].insert(L.size());
	}

	for (int i=1; i<=L.size(); ++i)
        g[i].insert(0);

    tr.upd(1, L.size());

    for (int i=0, head=0; i<=max_x; ++i) {
        while (head+1<L.size() && L[head+1]<=i)
            ++head;
        idx[i] = head+1;
    }
}

void add_store(int idx) {
	int tmp = ++pos[s[idx].t][s[idx].x];

	if (tmp==1) {
		auto u = pos[s[idx].t].lower_bound(s[idx].x);
		--u;
		auto v = pos[s[idx].t].upper_bound(s[idx].x);
//        debug(u->first);
//        debug(v->first);

        g[u->first].erase(g[u->first].find(v->first));
        g[u->first].insert(s[idx].x);
        g[s[idx].x].insert(v->first);

        tr.upd(u->first, *g[u->first].rbegin());
//        cerr << u->first << ' ' << *g[u->first].rbegin() << '\n';
        tr.upd(s[idx].x, *g[s[idx].x].rbegin());
//        cerr << s[idx].x << ' ' << *g[s[idx].x].rbegin() << '\n';
	}
}

void remove_store(int idx) {
	int tmp = --pos[s[idx].t][s[idx].x];

	if (!tmp) {
		auto u = pos[s[idx].t].lower_bound(s[idx].x);
		--u;
		auto v = pos[s[idx].t].upper_bound(s[idx].x);
//        debug(u->first);
//        debug(v->first);

        g[u->first].erase(g[u->first].find(s[idx].x));
        g[s[idx].x].erase(g[s[idx].x].find(v->first));
        g[u->first].insert(v->first);

        tr.upd(u->first, *g[u->first].rbegin());
//        cerr << u->first << ' ' << *g[u->first].rbegin() << '\n';
        tr.upd(s[idx].x, *g[s[idx].x].rbegin());
//        cerr << s[idx].x << ' ' << *g[s[idx].x].rbegin() << '\n';

        pos[s[idx].t].erase(s[idx].x);
	}
}

int bisect(int x) {
	int l = 0, r = max_x;

	for (int mid=(l+r)/2; mid!=l && r!=mid; mid=(l+r)/2) {
		if (tr.get(1, idx[max(0, x-mid-1)], idx[min(max_x, x+mid)]))
			r = mid;
		else
			l = mid;
	}

	for (int i=l; i<=r; ++i) {
		if (tr.get(1, idx[max(0, x-i-1)], idx[min(max_x, x+i)]))
			return i;
	}

	return -1;
}

void solve() {
    int tmp = 0;
    for (int i=1; i<=nQueries; ++i)
        tmp = max(tmp, Q[i].y);

	for (int i=1; i<=tmp; ++i) {
		for (auto x : store_event[i]) {
			if (x>0)
				add_store(x);
			else
				remove_store(-x);
		}

//		debug(tr.get(1, 2, 4));
		for (auto x : q[i])
			res[x] = bisect(Q[x].l);
	}

//	debug(tr.get())
	for (int i=1; i<=nQueries; ++i)
		cout << res[i] << '\n';
}

int main() {
	#ifdef GLASSES_GIRL
		freopen(FILE_NAME".in", "r", stdin);
//		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);

	read_input();
	compress();
	init();
	solve();
}

Compilation message

new_home.cpp: In function 'void init()':
new_home.cpp:164:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<=L.size(); ++i)
                ~^~~~~~~~~~
new_home.cpp:170:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (head+1<L.size() && L[head+1]<=i)
                ~~~~~~^~~~~~~~~
new_home.cpp: In function 'void solve()':
new_home.cpp:240:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i=1; i<=nQueries; ++i)
     ^~~
new_home.cpp:243:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (int i=1; i<=tmp; ++i) {
  ^~~

Subtask #1
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	107 ms	113084 KB	Output is correct
2	Correct	129 ms	113012 KB	Output is correct
3	Incorrect	129 ms	113108 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	107 ms	113084 KB	Output is correct
2	Correct	129 ms	113012 KB	Output is correct
3	Incorrect	129 ms	113108 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4112 ms	590476 KB	Output is correct
2	Correct	4778 ms	580832 KB	Output is correct
3	Correct	4379 ms	623940 KB	Output is correct
4	Correct	3977 ms	595720 KB	Output is correct
5	Correct	4533 ms	580088 KB	Output is correct
6	Correct	4774 ms	580348 KB	Output is correct
7	Correct	4011 ms	623824 KB	Output is correct
8	Correct	3316 ms	595632 KB	Output is correct
9	Correct	3437 ms	585728 KB	Output is correct
10	Correct	3778 ms	581036 KB	Output is correct
11	Correct	3038 ms	579388 KB	Output is correct
12	Correct	3286 ms	580768 KB	Output is correct