oj.uz

Submission #106937

# Submission time Handle Problem Language Result Execution time Memory
106937 2019-04-21T09:25:36 Z polyfish New Home (APIO18_new_home) C++14
47 / 100
 5000 ms 217648 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)
            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];
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);
		L.push_back(s[i].x);
	}

	for (int i=1; i<=nQueries; ++i) {
		T.push_back(Q[i].y);
		L.push_back(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);
		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
}

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+1].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());
}

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 = 2e8;

	for (int mid=(l+r)/2; mid!=l && r!=mid; mid=(l+r)/2) {
		if (tr.get(1, get_id(x-mid-1), get_id(x+mid)))
			r = mid;
		else
			l = mid;
	}

	for (int i=l; i<=r; ++i) {
		if (tr.get(1, get_id(x-i-1), get_id(x+i)))
			return i;
	}

	return -1;
}

void solve() {

	for (int i=1; i<=T.size(); ++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:163:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<=L.size(); ++i)
                ~^~~~~~~~~~
new_home.cpp: In function 'void solve()':
new_home.cpp:237:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<=T.size(); ++i) {
                ~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 113016 KB Output is correct
2 Correct 108 ms 113144 KB Output is correct
3 Correct 111 ms 113144 KB Output is correct
4 Correct 108 ms 113160 KB Output is correct
5 Correct 107 ms 113180 KB Output is correct
6 Correct 112 ms 113144 KB Output is correct
7 Correct 117 ms 113308 KB Output is correct
8 Correct 104 ms 113188 KB Output is correct
9 Correct 106 ms 113276 KB Output is correct
10 Correct 111 ms 113196 KB Output is correct
11 Correct 114 ms 113276 KB Output is correct
12 Correct 114 ms 113144 KB Output is correct
13 Correct 113 ms 113148 KB Output is correct
14 Correct 116 ms 113232 KB Output is correct
15 Correct 115 ms 113280 KB Output is correct
16 Correct 118 ms 113320 KB Output is correct
17 Correct 115 ms 113272 KB Output is correct
18 Correct 121 ms 113272 KB Output is correct
19 Correct 115 ms 113272 KB Output is correct
20 Correct 125 ms 113272 KB Output is correct
21 Correct 109 ms 113144 KB Output is correct
22 Correct 124 ms 113276 KB Output is correct
23 Correct 114 ms 113400 KB Output is correct
24 Correct 120 ms 113192 KB Output is correct
25 Correct 119 ms 113236 KB Output is correct
26 Correct 135 ms 113256 KB Output is correct
27 Correct 121 ms 113144 KB Output is correct
28 Correct 119 ms 113312 KB Output is correct
29 Correct 122 ms 113360 KB Output is correct
30 Correct 119 ms 113240 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 113016 KB Output is correct
2 Correct 108 ms 113144 KB Output is correct
3 Correct 111 ms 113144 KB Output is correct
4 Correct 108 ms 113160 KB Output is correct
5 Correct 107 ms 113180 KB Output is correct
6 Correct 112 ms 113144 KB Output is correct
7 Correct 117 ms 113308 KB Output is correct
8 Correct 104 ms 113188 KB Output is correct
9 Correct 106 ms 113276 KB Output is correct
10 Correct 111 ms 113196 KB Output is correct
11 Correct 114 ms 113276 KB Output is correct
12 Correct 114 ms 113144 KB Output is correct
13 Correct 113 ms 113148 KB Output is correct
14 Correct 116 ms 113232 KB Output is correct
15 Correct 115 ms 113280 KB Output is correct
16 Correct 118 ms 113320 KB Output is correct
17 Correct 115 ms 113272 KB Output is correct
18 Correct 121 ms 113272 KB Output is correct
19 Correct 115 ms 113272 KB Output is correct
20 Correct 125 ms 113272 KB Output is correct
21 Correct 109 ms 113144 KB Output is correct
22 Correct 124 ms 113276 KB Output is correct
23 Correct 114 ms 113400 KB Output is correct
24 Correct 120 ms 113192 KB Output is correct
25 Correct 119 ms 113236 KB Output is correct
26 Correct 135 ms 113256 KB Output is correct
27 Correct 121 ms 113144 KB Output is correct
28 Correct 119 ms 113312 KB Output is correct
29 Correct 122 ms 113360 KB Output is correct
30 Correct 119 ms 113240 KB Output is correct
31 Correct 1285 ms 138404 KB Output is correct
32 Correct 217 ms 117864 KB Output is correct
33 Correct 1399 ms 134068 KB Output is correct
34 Correct 1198 ms 134212 KB Output is correct
35 Correct 1326 ms 138068 KB Output is correct
36 Correct 1245 ms 138088 KB Output is correct
37 Correct 1034 ms 132456 KB Output is correct
38 Correct 1069 ms 132428 KB Output is correct
39 Correct 781 ms 131988 KB Output is correct
40 Correct 925 ms 131808 KB Output is correct
41 Correct 791 ms 132204 KB Output is correct
42 Correct 755 ms 131900 KB Output is correct
43 Correct 167 ms 119784 KB Output is correct
44 Correct 806 ms 132032 KB Output is correct
45 Correct 773 ms 132068 KB Output is correct
46 Correct 881 ms 131816 KB Output is correct
47 Correct 560 ms 131176 KB Output is correct
48 Correct 653 ms 131260 KB Output is correct
49 Correct 704 ms 131536 KB Output is correct
50 Correct 669 ms 131884 KB Output is correct
51 Correct 740 ms 131476 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4453 ms 217648 KB Output is correct
2 Execution timed out 5044 ms 206016 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5090 ms 214784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 113016 KB Output is correct
2 Correct 108 ms 113144 KB Output is correct
3 Correct 111 ms 113144 KB Output is correct
4 Correct 108 ms 113160 KB Output is correct
5 Correct 107 ms 113180 KB Output is correct
6 Correct 112 ms 113144 KB Output is correct
7 Correct 117 ms 113308 KB Output is correct
8 Correct 104 ms 113188 KB Output is correct
9 Correct 106 ms 113276 KB Output is correct
10 Correct 111 ms 113196 KB Output is correct
11 Correct 114 ms 113276 KB Output is correct
12 Correct 114 ms 113144 KB Output is correct
13 Correct 113 ms 113148 KB Output is correct
14 Correct 116 ms 113232 KB Output is correct
15 Correct 115 ms 113280 KB Output is correct
16 Correct 118 ms 113320 KB Output is correct
17 Correct 115 ms 113272 KB Output is correct
18 Correct 121 ms 113272 KB Output is correct
19 Correct 115 ms 113272 KB Output is correct
20 Correct 125 ms 113272 KB Output is correct
21 Correct 109 ms 113144 KB Output is correct
22 Correct 124 ms 113276 KB Output is correct
23 Correct 114 ms 113400 KB Output is correct
24 Correct 120 ms 113192 KB Output is correct
25 Correct 119 ms 113236 KB Output is correct
26 Correct 135 ms 113256 KB Output is correct
27 Correct 121 ms 113144 KB Output is correct
28 Correct 119 ms 113312 KB Output is correct
29 Correct 122 ms 113360 KB Output is correct
30 Correct 119 ms 113240 KB Output is correct
31 Correct 1285 ms 138404 KB Output is correct
32 Correct 217 ms 117864 KB Output is correct
33 Correct 1399 ms 134068 KB Output is correct
34 Correct 1198 ms 134212 KB Output is correct
35 Correct 1326 ms 138068 KB Output is correct
36 Correct 1245 ms 138088 KB Output is correct
37 Correct 1034 ms 132456 KB Output is correct
38 Correct 1069 ms 132428 KB Output is correct
39 Correct 781 ms 131988 KB Output is correct
40 Correct 925 ms 131808 KB Output is correct
41 Correct 791 ms 132204 KB Output is correct
42 Correct 755 ms 131900 KB Output is correct
43 Correct 167 ms 119784 KB Output is correct
44 Correct 806 ms 132032 KB Output is correct
45 Correct 773 ms 132068 KB Output is correct
46 Correct 881 ms 131816 KB Output is correct
47 Correct 560 ms 131176 KB Output is correct
48 Correct 653 ms 131260 KB Output is correct
49 Correct 704 ms 131536 KB Output is correct
50 Correct 669 ms 131884 KB Output is correct
51 Correct 740 ms 131476 KB Output is correct
52 Correct 958 ms 146432 KB Output is correct
53 Correct 972 ms 142480 KB Output is correct
54 Correct 891 ms 140900 KB Output is correct
55 Correct 846 ms 137048 KB Output is correct
56 Correct 880 ms 139524 KB Output is correct
57 Correct 874 ms 133716 KB Output is correct
58 Correct 875 ms 136876 KB Output is correct
59 Correct 892 ms 139324 KB Output is correct
60 Correct 674 ms 133468 KB Output is correct
61 Correct 300 ms 133860 KB Output is correct
62 Correct 878 ms 146576 KB Output is correct
63 Correct 968 ms 141432 KB Output is correct
64 Correct 905 ms 138876 KB Output is correct
65 Correct 829 ms 134244 KB Output is correct
66 Correct 747 ms 132284 KB Output is correct
67 Correct 444 ms 120552 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 113016 KB Output is correct
2 Correct 108 ms 113144 KB Output is correct
3 Correct 111 ms 113144 KB Output is correct
4 Correct 108 ms 113160 KB Output is correct
5 Correct 107 ms 113180 KB Output is correct
6 Correct 112 ms 113144 KB Output is correct
7 Correct 117 ms 113308 KB Output is correct
8 Correct 104 ms 113188 KB Output is correct
9 Correct 106 ms 113276 KB Output is correct
10 Correct 111 ms 113196 KB Output is correct
11 Correct 114 ms 113276 KB Output is correct
12 Correct 114 ms 113144 KB Output is correct
13 Correct 113 ms 113148 KB Output is correct
14 Correct 116 ms 113232 KB Output is correct
15 Correct 115 ms 113280 KB Output is correct
16 Correct 118 ms 113320 KB Output is correct
17 Correct 115 ms 113272 KB Output is correct
18 Correct 121 ms 113272 KB Output is correct
19 Correct 115 ms 113272 KB Output is correct
20 Correct 125 ms 113272 KB Output is correct
21 Correct 109 ms 113144 KB Output is correct
22 Correct 124 ms 113276 KB Output is correct
23 Correct 114 ms 113400 KB Output is correct
24 Correct 120 ms 113192 KB Output is correct
25 Correct 119 ms 113236 KB Output is correct
26 Correct 135 ms 113256 KB Output is correct
27 Correct 121 ms 113144 KB Output is correct
28 Correct 119 ms 113312 KB Output is correct
29 Correct 122 ms 113360 KB Output is correct
30 Correct 119 ms 113240 KB Output is correct
31 Correct 1285 ms 138404 KB Output is correct
32 Correct 217 ms 117864 KB Output is correct
33 Correct 1399 ms 134068 KB Output is correct
34 Correct 1198 ms 134212 KB Output is correct
35 Correct 1326 ms 138068 KB Output is correct
36 Correct 1245 ms 138088 KB Output is correct
37 Correct 1034 ms 132456 KB Output is correct
38 Correct 1069 ms 132428 KB Output is correct
39 Correct 781 ms 131988 KB Output is correct
40 Correct 925 ms 131808 KB Output is correct
41 Correct 791 ms 132204 KB Output is correct
42 Correct 755 ms 131900 KB Output is correct
43 Correct 167 ms 119784 KB Output is correct
44 Correct 806 ms 132032 KB Output is correct
45 Correct 773 ms 132068 KB Output is correct
46 Correct 881 ms 131816 KB Output is correct
47 Correct 560 ms 131176 KB Output is correct
48 Correct 653 ms 131260 KB Output is correct
49 Correct 704 ms 131536 KB Output is correct
50 Correct 669 ms 131884 KB Output is correct
51 Correct 740 ms 131476 KB Output is correct
52 Correct 4453 ms 217648 KB Output is correct
53 Execution timed out 5044 ms 206016 KB Time limit exceeded
54 Halted 0 ms 0 KB -