oj.uz

Submission #106941

# Submission time Handle Problem Language Result Execution time Memory
106941 2019-04-21T09:38:39 Z polyfish New Home (APIO18_new_home) C++14
47 / 100
 5000 ms 216592 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+1);
		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+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
}

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());
}

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() {
    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: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:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i=1; i<=nQueries; ++i)
     ^~~
new_home.cpp:240: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

# Verdict Execution time Memory Grader output
1 Correct 108 ms 113144 KB Output is correct
2 Correct 105 ms 113272 KB Output is correct
3 Correct 105 ms 113144 KB Output is correct
4 Correct 109 ms 113272 KB Output is correct
5 Correct 105 ms 113176 KB Output is correct
6 Correct 118 ms 113144 KB Output is correct
7 Correct 112 ms 113372 KB Output is correct
8 Correct 137 ms 113244 KB Output is correct
9 Correct 114 ms 113272 KB Output is correct
10 Correct 116 ms 113228 KB Output is correct
11 Correct 114 ms 113272 KB Output is correct
12 Correct 115 ms 113208 KB Output is correct
13 Correct 118 ms 113184 KB Output is correct
14 Correct 113 ms 113240 KB Output is correct
15 Correct 107 ms 113316 KB Output is correct
16 Correct 107 ms 113272 KB Output is correct
17 Correct 116 ms 113252 KB Output is correct
18 Correct 120 ms 113468 KB Output is correct
19 Correct 111 ms 113248 KB Output is correct
20 Correct 116 ms 113220 KB Output is correct
21 Correct 106 ms 113256 KB Output is correct
22 Correct 108 ms 113284 KB Output is correct
23 Correct 117 ms 113244 KB Output is correct
24 Correct 109 ms 113372 KB Output is correct
25 Correct 128 ms 113272 KB Output is correct
26 Correct 118 ms 113248 KB Output is correct
27 Correct 103 ms 113116 KB Output is correct
28 Correct 109 ms 113144 KB Output is correct
29 Correct 108 ms 113144 KB Output is correct
30 Correct 184 ms 113156 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 113144 KB Output is correct
2 Correct 105 ms 113272 KB Output is correct
3 Correct 105 ms 113144 KB Output is correct
4 Correct 109 ms 113272 KB Output is correct
5 Correct 105 ms 113176 KB Output is correct
6 Correct 118 ms 113144 KB Output is correct
7 Correct 112 ms 113372 KB Output is correct
8 Correct 137 ms 113244 KB Output is correct
9 Correct 114 ms 113272 KB Output is correct
10 Correct 116 ms 113228 KB Output is correct
11 Correct 114 ms 113272 KB Output is correct
12 Correct 115 ms 113208 KB Output is correct
13 Correct 118 ms 113184 KB Output is correct
14 Correct 113 ms 113240 KB Output is correct
15 Correct 107 ms 113316 KB Output is correct
16 Correct 107 ms 113272 KB Output is correct
17 Correct 116 ms 113252 KB Output is correct
18 Correct 120 ms 113468 KB Output is correct
19 Correct 111 ms 113248 KB Output is correct
20 Correct 116 ms 113220 KB Output is correct
21 Correct 106 ms 113256 KB Output is correct
22 Correct 108 ms 113284 KB Output is correct
23 Correct 117 ms 113244 KB Output is correct
24 Correct 109 ms 113372 KB Output is correct
25 Correct 128 ms 113272 KB Output is correct
26 Correct 118 ms 113248 KB Output is correct
27 Correct 103 ms 113116 KB Output is correct
28 Correct 109 ms 113144 KB Output is correct
29 Correct 108 ms 113144 KB Output is correct
30 Correct 184 ms 113156 KB Output is correct
31 Correct 1340 ms 135360 KB Output is correct
32 Correct 203 ms 117096 KB Output is correct
33 Correct 1289 ms 131604 KB Output is correct
34 Correct 1151 ms 131852 KB Output is correct
35 Correct 1238 ms 135248 KB Output is correct
36 Correct 1331 ms 135136 KB Output is correct
37 Correct 1055 ms 130024 KB Output is correct
38 Correct 985 ms 129892 KB Output is correct
39 Correct 818 ms 129512 KB Output is correct
40 Correct 892 ms 129604 KB Output is correct
41 Correct 751 ms 129640 KB Output is correct
42 Correct 840 ms 129600 KB Output is correct
43 Correct 171 ms 117476 KB Output is correct
44 Correct 835 ms 129884 KB Output is correct
45 Correct 697 ms 129764 KB Output is correct
46 Correct 714 ms 129684 KB Output is correct
47 Correct 658 ms 129004 KB Output is correct
48 Correct 699 ms 129096 KB Output is correct
49 Correct 658 ms 129252 KB Output is correct
50 Correct 618 ms 129476 KB Output is correct
51 Correct 671 ms 129352 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3782 ms 216592 KB Output is correct
2 Execution timed out 5068 ms 205632 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 5051 ms 213728 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 113144 KB Output is correct
2 Correct 105 ms 113272 KB Output is correct
3 Correct 105 ms 113144 KB Output is correct
4 Correct 109 ms 113272 KB Output is correct
5 Correct 105 ms 113176 KB Output is correct
6 Correct 118 ms 113144 KB Output is correct
7 Correct 112 ms 113372 KB Output is correct
8 Correct 137 ms 113244 KB Output is correct
9 Correct 114 ms 113272 KB Output is correct
10 Correct 116 ms 113228 KB Output is correct
11 Correct 114 ms 113272 KB Output is correct
12 Correct 115 ms 113208 KB Output is correct
13 Correct 118 ms 113184 KB Output is correct
14 Correct 113 ms 113240 KB Output is correct
15 Correct 107 ms 113316 KB Output is correct
16 Correct 107 ms 113272 KB Output is correct
17 Correct 116 ms 113252 KB Output is correct
18 Correct 120 ms 113468 KB Output is correct
19 Correct 111 ms 113248 KB Output is correct
20 Correct 116 ms 113220 KB Output is correct
21 Correct 106 ms 113256 KB Output is correct
22 Correct 108 ms 113284 KB Output is correct
23 Correct 117 ms 113244 KB Output is correct
24 Correct 109 ms 113372 KB Output is correct
25 Correct 128 ms 113272 KB Output is correct
26 Correct 118 ms 113248 KB Output is correct
27 Correct 103 ms 113116 KB Output is correct
28 Correct 109 ms 113144 KB Output is correct
29 Correct 108 ms 113144 KB Output is correct
30 Correct 184 ms 113156 KB Output is correct
31 Correct 1340 ms 135360 KB Output is correct
32 Correct 203 ms 117096 KB Output is correct
33 Correct 1289 ms 131604 KB Output is correct
34 Correct 1151 ms 131852 KB Output is correct
35 Correct 1238 ms 135248 KB Output is correct
36 Correct 1331 ms 135136 KB Output is correct
37 Correct 1055 ms 130024 KB Output is correct
38 Correct 985 ms 129892 KB Output is correct
39 Correct 818 ms 129512 KB Output is correct
40 Correct 892 ms 129604 KB Output is correct
41 Correct 751 ms 129640 KB Output is correct
42 Correct 840 ms 129600 KB Output is correct
43 Correct 171 ms 117476 KB Output is correct
44 Correct 835 ms 129884 KB Output is correct
45 Correct 697 ms 129764 KB Output is correct
46 Correct 714 ms 129684 KB Output is correct
47 Correct 658 ms 129004 KB Output is correct
48 Correct 699 ms 129096 KB Output is correct
49 Correct 658 ms 129252 KB Output is correct
50 Correct 618 ms 129476 KB Output is correct
51 Correct 671 ms 129352 KB Output is correct
52 Correct 944 ms 143360 KB Output is correct
53 Correct 883 ms 140004 KB Output is correct
54 Correct 891 ms 137800 KB Output is correct
55 Correct 845 ms 134500 KB Output is correct
56 Correct 835 ms 136988 KB Output is correct
57 Correct 888 ms 131208 KB Output is correct
58 Correct 857 ms 134344 KB Output is correct
59 Correct 920 ms 136704 KB Output is correct
60 Correct 870 ms 131048 KB Output is correct
61 Correct 259 ms 131300 KB Output is correct
62 Correct 835 ms 143648 KB Output is correct
63 Correct 838 ms 138468 KB Output is correct
64 Correct 926 ms 136168 KB Output is correct
65 Correct 916 ms 131788 KB Output is correct
66 Correct 781 ms 129892 KB Output is correct
67 Correct 382 ms 119168 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 113144 KB Output is correct
2 Correct 105 ms 113272 KB Output is correct
3 Correct 105 ms 113144 KB Output is correct
4 Correct 109 ms 113272 KB Output is correct
5 Correct 105 ms 113176 KB Output is correct
6 Correct 118 ms 113144 KB Output is correct
7 Correct 112 ms 113372 KB Output is correct
8 Correct 137 ms 113244 KB Output is correct
9 Correct 114 ms 113272 KB Output is correct
10 Correct 116 ms 113228 KB Output is correct
11 Correct 114 ms 113272 KB Output is correct
12 Correct 115 ms 113208 KB Output is correct
13 Correct 118 ms 113184 KB Output is correct
14 Correct 113 ms 113240 KB Output is correct
15 Correct 107 ms 113316 KB Output is correct
16 Correct 107 ms 113272 KB Output is correct
17 Correct 116 ms 113252 KB Output is correct
18 Correct 120 ms 113468 KB Output is correct
19 Correct 111 ms 113248 KB Output is correct
20 Correct 116 ms 113220 KB Output is correct
21 Correct 106 ms 113256 KB Output is correct
22 Correct 108 ms 113284 KB Output is correct
23 Correct 117 ms 113244 KB Output is correct
24 Correct 109 ms 113372 KB Output is correct
25 Correct 128 ms 113272 KB Output is correct
26 Correct 118 ms 113248 KB Output is correct
27 Correct 103 ms 113116 KB Output is correct
28 Correct 109 ms 113144 KB Output is correct
29 Correct 108 ms 113144 KB Output is correct
30 Correct 184 ms 113156 KB Output is correct
31 Correct 1340 ms 135360 KB Output is correct
32 Correct 203 ms 117096 KB Output is correct
33 Correct 1289 ms 131604 KB Output is correct
34 Correct 1151 ms 131852 KB Output is correct
35 Correct 1238 ms 135248 KB Output is correct
36 Correct 1331 ms 135136 KB Output is correct
37 Correct 1055 ms 130024 KB Output is correct
38 Correct 985 ms 129892 KB Output is correct
39 Correct 818 ms 129512 KB Output is correct
40 Correct 892 ms 129604 KB Output is correct
41 Correct 751 ms 129640 KB Output is correct
42 Correct 840 ms 129600 KB Output is correct
43 Correct 171 ms 117476 KB Output is correct
44 Correct 835 ms 129884 KB Output is correct
45 Correct 697 ms 129764 KB Output is correct
46 Correct 714 ms 129684 KB Output is correct
47 Correct 658 ms 129004 KB Output is correct
48 Correct 699 ms 129096 KB Output is correct
49 Correct 658 ms 129252 KB Output is correct
50 Correct 618 ms 129476 KB Output is correct
51 Correct 671 ms 129352 KB Output is correct
52 Correct 3782 ms 216592 KB Output is correct
53 Execution timed out 5068 ms 205632 KB Time limit exceeded
54 Halted 0 ms 0 KB -