oj.uz

답안 #106992

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106992 2019-04-21T12:23:05 Z polyfish 새 집 (APIO18_new_home) C++14
47 / 100
 5000 ms 594536 KB 
//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], max_x;
vector<int> idx;
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);
		max_x = max(max_x, Q[i].l);
	}

	#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 = max(max_x, L[L.size()-2]);
}

void init() {
    tr.init(L.size());
    idx.resize(max_x+1);

	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=-1; 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 get_id(int x) {
    return upper_bound(L.begin(), L.end(), x) - L.begin();
}

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

	for (int mid=(l+r)/2; mid!=l && r!=mid; mid=(l+r)/2) {
//        debug(get_id(x-mid-1));
		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:167:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<=L.size(); ++i)
                ~^~~~~~~~~~
new_home.cpp:173: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:248:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i=1; i<=nQueries; ++i)
     ^~~
new_home.cpp:251: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
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 113016 KB Output is correct
2 Correct 135 ms 113100 KB Output is correct
3 Correct 122 ms 113144 KB Output is correct
4 Correct 1656 ms 483288 KB Output is correct
5 Correct 114 ms 113144 KB Output is correct
6 Correct 857 ms 503440 KB Output is correct
7 Correct 650 ms 503564 KB Output is correct
8 Correct 671 ms 504720 KB Output is correct
9 Correct 650 ms 503956 KB Output is correct
10 Correct 639 ms 504164 KB Output is correct
11 Correct 665 ms 504008 KB Output is correct
12 Correct 667 ms 504596 KB Output is correct
13 Correct 631 ms 503544 KB Output is correct
14 Correct 634 ms 503800 KB Output is correct
15 Correct 617 ms 504420 KB Output is correct
16 Correct 630 ms 504612 KB Output is correct
17 Correct 604 ms 504284 KB Output is correct
18 Correct 611 ms 504716 KB Output is correct
19 Correct 642 ms 503900 KB Output is correct
20 Correct 606 ms 504388 KB Output is correct
21 Correct 656 ms 504760 KB Output is correct
22 Correct 617 ms 504568 KB Output is correct
23 Correct 662 ms 504056 KB Output is correct
24 Correct 638 ms 504424 KB Output is correct
25 Correct 616 ms 504588 KB Output is correct
26 Correct 638 ms 503800 KB Output is correct
27 Correct 111 ms 113144 KB Output is correct
28 Correct 581 ms 504564 KB Output is correct
29 Correct 658 ms 504736 KB Output is correct
30 Correct 648 ms 504728 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 113016 KB Output is correct
2 Correct 135 ms 113100 KB Output is correct
3 Correct 122 ms 113144 KB Output is correct
4 Correct 1656 ms 483288 KB Output is correct
5 Correct 114 ms 113144 KB Output is correct
6 Correct 857 ms 503440 KB Output is correct
7 Correct 650 ms 503564 KB Output is correct
8 Correct 671 ms 504720 KB Output is correct
9 Correct 650 ms 503956 KB Output is correct
10 Correct 639 ms 504164 KB Output is correct
11 Correct 665 ms 504008 KB Output is correct
12 Correct 667 ms 504596 KB Output is correct
13 Correct 631 ms 503544 KB Output is correct
14 Correct 634 ms 503800 KB Output is correct
15 Correct 617 ms 504420 KB Output is correct
16 Correct 630 ms 504612 KB Output is correct
17 Correct 604 ms 504284 KB Output is correct
18 Correct 611 ms 504716 KB Output is correct
19 Correct 642 ms 503900 KB Output is correct
20 Correct 606 ms 504388 KB Output is correct
21 Correct 656 ms 504760 KB Output is correct
22 Correct 617 ms 504568 KB Output is correct
23 Correct 662 ms 504056 KB Output is correct
24 Correct 638 ms 504424 KB Output is correct
25 Correct 616 ms 504588 KB Output is correct
26 Correct 638 ms 503800 KB Output is correct
27 Correct 111 ms 113144 KB Output is correct
28 Correct 581 ms 504564 KB Output is correct
29 Correct 658 ms 504736 KB Output is correct
30 Correct 648 ms 504728 KB Output is correct
31 Correct 1800 ms 525520 KB Output is correct
32 Correct 164 ms 117712 KB Output is correct
33 Correct 1592 ms 522044 KB Output is correct
34 Correct 1661 ms 522104 KB Output is correct
35 Correct 1680 ms 525536 KB Output is correct
36 Correct 1731 ms 525368 KB Output is correct
37 Correct 1372 ms 520224 KB Output is correct
38 Correct 1605 ms 520108 KB Output is correct
39 Correct 1284 ms 519724 KB Output is correct
40 Correct 1297 ms 519752 KB Output is correct
41 Correct 1214 ms 520192 KB Output is correct
42 Correct 1223 ms 519900 KB Output is correct
43 Correct 669 ms 511084 KB Output is correct
44 Correct 1285 ms 520064 KB Output is correct
45 Correct 1157 ms 519964 KB Output is correct
46 Correct 1243 ms 519864 KB Output is correct
47 Correct 1038 ms 519144 KB Output is correct
48 Correct 1090 ms 519212 KB Output is correct
49 Correct 1175 ms 519480 KB Output is correct
50 Correct 1050 ms 519804 KB Output is correct
51 Correct 1095 ms 519480 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5150 ms 594536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5076 ms 588480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 113016 KB Output is correct
2 Correct 135 ms 113100 KB Output is correct
3 Correct 122 ms 113144 KB Output is correct
4 Correct 1656 ms 483288 KB Output is correct
5 Correct 114 ms 113144 KB Output is correct
6 Correct 857 ms 503440 KB Output is correct
7 Correct 650 ms 503564 KB Output is correct
8 Correct 671 ms 504720 KB Output is correct
9 Correct 650 ms 503956 KB Output is correct
10 Correct 639 ms 504164 KB Output is correct
11 Correct 665 ms 504008 KB Output is correct
12 Correct 667 ms 504596 KB Output is correct
13 Correct 631 ms 503544 KB Output is correct
14 Correct 634 ms 503800 KB Output is correct
15 Correct 617 ms 504420 KB Output is correct
16 Correct 630 ms 504612 KB Output is correct
17 Correct 604 ms 504284 KB Output is correct
18 Correct 611 ms 504716 KB Output is correct
19 Correct 642 ms 503900 KB Output is correct
20 Correct 606 ms 504388 KB Output is correct
21 Correct 656 ms 504760 KB Output is correct
22 Correct 617 ms 504568 KB Output is correct
23 Correct 662 ms 504056 KB Output is correct
24 Correct 638 ms 504424 KB Output is correct
25 Correct 616 ms 504588 KB Output is correct
26 Correct 638 ms 503800 KB Output is correct
27 Correct 111 ms 113144 KB Output is correct
28 Correct 581 ms 504564 KB Output is correct
29 Correct 658 ms 504736 KB Output is correct
30 Correct 648 ms 504728 KB Output is correct
31 Correct 1800 ms 525520 KB Output is correct
32 Correct 164 ms 117712 KB Output is correct
33 Correct 1592 ms 522044 KB Output is correct
34 Correct 1661 ms 522104 KB Output is correct
35 Correct 1680 ms 525536 KB Output is correct
36 Correct 1731 ms 525368 KB Output is correct
37 Correct 1372 ms 520224 KB Output is correct
38 Correct 1605 ms 520108 KB Output is correct
39 Correct 1284 ms 519724 KB Output is correct
40 Correct 1297 ms 519752 KB Output is correct
41 Correct 1214 ms 520192 KB Output is correct
42 Correct 1223 ms 519900 KB Output is correct
43 Correct 669 ms 511084 KB Output is correct
44 Correct 1285 ms 520064 KB Output is correct
45 Correct 1157 ms 519964 KB Output is correct
46 Correct 1243 ms 519864 KB Output is correct
47 Correct 1038 ms 519144 KB Output is correct
48 Correct 1090 ms 519212 KB Output is correct
49 Correct 1175 ms 519480 KB Output is correct
50 Correct 1050 ms 519804 KB Output is correct
51 Correct 1095 ms 519480 KB Output is correct
52 Correct 1441 ms 533984 KB Output is correct
53 Correct 1372 ms 530392 KB Output is correct
54 Correct 1466 ms 528244 KB Output is correct
55 Correct 1506 ms 524908 KB Output is correct
56 Correct 1434 ms 527188 KB Output is correct
57 Correct 1247 ms 521520 KB Output is correct
58 Correct 1348 ms 524908 KB Output is correct
59 Correct 1336 ms 527024 KB Output is correct
60 Correct 1105 ms 521568 KB Output is correct
61 Correct 693 ms 525164 KB Output is correct
62 Correct 1328 ms 534124 KB Output is correct
63 Correct 1321 ms 528868 KB Output is correct
64 Correct 1339 ms 526524 KB Output is correct
65 Correct 1414 ms 522260 KB Output is correct
66 Correct 1278 ms 520376 KB Output is correct
67 Correct 332 ms 120180 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 113016 KB Output is correct
2 Correct 135 ms 113100 KB Output is correct
3 Correct 122 ms 113144 KB Output is correct
4 Correct 1656 ms 483288 KB Output is correct
5 Correct 114 ms 113144 KB Output is correct
6 Correct 857 ms 503440 KB Output is correct
7 Correct 650 ms 503564 KB Output is correct
8 Correct 671 ms 504720 KB Output is correct
9 Correct 650 ms 503956 KB Output is correct
10 Correct 639 ms 504164 KB Output is correct
11 Correct 665 ms 504008 KB Output is correct
12 Correct 667 ms 504596 KB Output is correct
13 Correct 631 ms 503544 KB Output is correct
14 Correct 634 ms 503800 KB Output is correct
15 Correct 617 ms 504420 KB Output is correct
16 Correct 630 ms 504612 KB Output is correct
17 Correct 604 ms 504284 KB Output is correct
18 Correct 611 ms 504716 KB Output is correct
19 Correct 642 ms 503900 KB Output is correct
20 Correct 606 ms 504388 KB Output is correct
21 Correct 656 ms 504760 KB Output is correct
22 Correct 617 ms 504568 KB Output is correct
23 Correct 662 ms 504056 KB Output is correct
24 Correct 638 ms 504424 KB Output is correct
25 Correct 616 ms 504588 KB Output is correct
26 Correct 638 ms 503800 KB Output is correct
27 Correct 111 ms 113144 KB Output is correct
28 Correct 581 ms 504564 KB Output is correct
29 Correct 658 ms 504736 KB Output is correct
30 Correct 648 ms 504728 KB Output is correct
31 Correct 1800 ms 525520 KB Output is correct
32 Correct 164 ms 117712 KB Output is correct
33 Correct 1592 ms 522044 KB Output is correct
34 Correct 1661 ms 522104 KB Output is correct
35 Correct 1680 ms 525536 KB Output is correct
36 Correct 1731 ms 525368 KB Output is correct
37 Correct 1372 ms 520224 KB Output is correct
38 Correct 1605 ms 520108 KB Output is correct
39 Correct 1284 ms 519724 KB Output is correct
40 Correct 1297 ms 519752 KB Output is correct
41 Correct 1214 ms 520192 KB Output is correct
42 Correct 1223 ms 519900 KB Output is correct
43 Correct 669 ms 511084 KB Output is correct
44 Correct 1285 ms 520064 KB Output is correct
45 Correct 1157 ms 519964 KB Output is correct
46 Correct 1243 ms 519864 KB Output is correct
47 Correct 1038 ms 519144 KB Output is correct
48 Correct 1090 ms 519212 KB Output is correct
49 Correct 1175 ms 519480 KB Output is correct
50 Correct 1050 ms 519804 KB Output is correct
51 Correct 1095 ms 519480 KB Output is correct
52 Execution timed out 5150 ms 594536 KB Time limit exceeded
53 Halted 0 ms 0 KB -