oj.uz

Submission #104120

# Submission time Handle Problem Language Result Execution time Memory
104120 2019-04-04T06:41:10 Z dimash241 New Home (APIO18_new_home) C++14
12 / 100
 5000 ms 162368 KB 
# include <stdio.h>
# include <bits/stdc++.h>


#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define For(i,x,y)  for (int i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (int i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

using namespace std;
inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; } 
inline bool isvowel (char c) {
	c = tolower(c);
    if (c == 'a' || c == 'e' || c == 'i' || c == 'y' || c == 'o' || c == 'u') return 1;
    return 0;
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, q, k;
int x[N], t[N], a[N], b[N];
int l[N], y[N];
int ans[N];
vector < int > pp;
map < int, int > M;

int get(int x) {
    auto it = M.lower_bound(x);
    int m = 0;
    if (it != M.end()) m = max(m,it->second-(it->first-x));
    if (it != M.begin()) it--,m = max(m,it->second-(x-it->first));
    return m;
}
void ins(int x,int h) {
    if (get(x) >= h) return ;
    auto it = M.lower_bound(x);
    while (it != M.end()) {
        if (it->second > h-(it->first-x)) break;
        else it = M.erase(it);
    }
    M[x] = h;
    it = M.find(x);
    while (1) {
        if (it == M.begin()) break;
        it--;
        if (it->second > h-(x-it->first)) break;
        else it = M.erase(it);
    }
}

inline void solve () {
	for (int i = 1; i <= n; i ++)
		pp.pb(a[i]), pp.pb(b[i]);
	for (int i = 1; i <= q; i ++) {
		pp.pb(y[i]);
	}
	sort(every(pp));
	pp.resize(unique(every(pp)) - pp.begin());
	vector < vector < pair < int, int > > > add(pp.size() + 2);
	vector < vector < pair < int, int > > > del(pp.size() + 2);
	vector < vector < pair < int, int > > > query(pp.size() + 2);
	multiset < int > bl[k + 1];
	for (int i = 1; i <= k; i ++)
		bl[i].clear();
	for (int i = 1; i <= n; i ++) {
		a[i] = lower_bound(every(pp), a[i]) - pp.begin();
		b[i] = lower_bound(every(pp), b[i]) - pp.begin();
		add[a[i]].pb(mp(x[i], t[i]));
		del[b[i]].pb(mp(x[i], t[i]));
	}

	for (int i = 1; i <= q; i ++) {
		y[i] = lower_bound(every(pp), y[i]) - pp.begin();
		query[y[i]].pb(mp(l[i], i));
	}

	for (int vv = 0; vv < pp.size(); vv ++) {

		for (auto it : add[vv]) bl[it.S].insert(it.F);

		for (auto q : query[vv]) {
			int res = 0;
			for (int w = 1; w <= k; w ++) {
				if (bl[w].empty()) {
					res = -1;
					break;
				}

				int cur = inf;
				auto l = bl[w].upper_bound(q.F);
				if (l != bl[w].end()) {
					cur = min(cur, *l - q.F); 
				}
				if (l != bl[w].begin()) {
					--l;
					cur = min(cur, q.F - *l);
				}
		//		cout << cur << ' ' << w << '\n';
				res = max(res, cur);
			}
			ans[q.S] = res;
		}

		for (auto it : del[vv]) bl[it.S].erase(bl[it.S].find(it.F));
	}
	for (int i = 1; i <= q; i ++)
		cout << ans[i] << '\n';
}
vector < pair < int, int > > add[N], del[N], query[N];
multiset < int > bl[N];

int main () {
	scanf("%d%d%d", &n, &k, &q);
    for (int i = 1; i <= n; ++i) {
    	scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]);
    }
    for (int i = 1; i <= q; ++i) {
    	scanf("%d%d", &l[i], &y[i]);
    }
    if (k < 500) {
    	solve();
    	exit(0);
    }
    for (int i = 1; i <= n; ++i)
		pp.pb(a[i]), pp.pb(b[i]);
	for (int i = 1; i <= q; ++i) {
		pp.pb(y[i]);
	}
	sort(every(pp));
	pp.resize(unique(every(pp)) - pp.begin());
	for (int i = 1; i <= n; i ++) {
		a[i] = lower_bound(every(pp), a[i]) - pp.begin();
		b[i] = lower_bound(every(pp), b[i]) - pp.begin();
		add[a[i]].pb(mp(x[i], t[i]));
		del[b[i]].pb(mp(x[i], t[i]));
	}

	for (int i = 1; i <= q; i ++) {
		y[i] = lower_bound(every(pp), y[i]) - pp.begin();
		query[y[i]].pb(mp(l[i], i));
	}
	
	bool f = 0;
    for (int i = 0; i < pp.size(); ++i) {
    	for (auto it : add[i]) bl[it.S].insert(it.F); 
        if (!f) {
           for (int j = 1; j <= k; ++j) {
                bl[j].insert(-3e8);
                bl[j].insert(3e8);
                for (auto it = ++bl[j].begin(); it != bl[j].end(); it++) {
               		auto it2 = it;
                    it2 --;
                    ins(*it + *it2,*it - *it2);
           		}
           }         
           f = 1;
      	}
      	for (auto it : query[i])
      		ans[it.S] = get(2 * it.F) / 2;
      	for (auto id : del[i]) {
        	int p = id.S;
            auto it = bl[p].find(id.F);
            auto it2 = it;
            it++,it2--;
            ins(*it+*it2,*it-*it2);
            bl[p].erase(bl[p].find(id.F));
                
    	}
    }
	for (int i = 1; i <= q; ++i) {
		if (ans[i] > 1e8) ans[i] = -1;
		printf("%d\n", ans[i]);
	}
    return Accepted;
}

// B...a D....

Compilation message

new_home.cpp: In function 'void solve()':
new_home.cpp:100:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int vv = 0; vv < pp.size(); vv ++) {
                   ~~~^~~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:167:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < pp.size(); ++i) {
                     ~~^~~~~~~~~~~
new_home.cpp:136:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &k, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:138:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]);
      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:141:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d%d", &l[i], &y[i]);
      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 70904 KB Output is correct
2 Correct 69 ms 70776 KB Output is correct
3 Correct 72 ms 70904 KB Output is correct
4 Correct 69 ms 70776 KB Output is correct
5 Correct 83 ms 70904 KB Output is correct
6 Correct 75 ms 71160 KB Output is correct
7 Correct 80 ms 71032 KB Output is correct
8 Correct 70 ms 71004 KB Output is correct
9 Correct 83 ms 71120 KB Output is correct
10 Correct 76 ms 71032 KB Output is correct
11 Correct 71 ms 71032 KB Output is correct
12 Correct 77 ms 71032 KB Output is correct
13 Correct 71 ms 70924 KB Output is correct
14 Correct 73 ms 71032 KB Output is correct
15 Correct 80 ms 71032 KB Output is correct
16 Correct 71 ms 71004 KB Output is correct
17 Correct 74 ms 71032 KB Output is correct
18 Correct 76 ms 71032 KB Output is correct
19 Correct 71 ms 71032 KB Output is correct
20 Correct 77 ms 71032 KB Output is correct
21 Correct 70 ms 70904 KB Output is correct
22 Correct 86 ms 71036 KB Output is correct
23 Correct 73 ms 71032 KB Output is correct
24 Correct 72 ms 71032 KB Output is correct
25 Correct 77 ms 70988 KB Output is correct
26 Correct 73 ms 71032 KB Output is correct
27 Correct 74 ms 70904 KB Output is correct
28 Correct 72 ms 70908 KB Output is correct
29 Correct 72 ms 71032 KB Output is correct
30 Correct 78 ms 70904 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 70904 KB Output is correct
2 Correct 69 ms 70776 KB Output is correct
3 Correct 72 ms 70904 KB Output is correct
4 Correct 69 ms 70776 KB Output is correct
5 Correct 83 ms 70904 KB Output is correct
6 Correct 75 ms 71160 KB Output is correct
7 Correct 80 ms 71032 KB Output is correct
8 Correct 70 ms 71004 KB Output is correct
9 Correct 83 ms 71120 KB Output is correct
10 Correct 76 ms 71032 KB Output is correct
11 Correct 71 ms 71032 KB Output is correct
12 Correct 77 ms 71032 KB Output is correct
13 Correct 71 ms 70924 KB Output is correct
14 Correct 73 ms 71032 KB Output is correct
15 Correct 80 ms 71032 KB Output is correct
16 Correct 71 ms 71004 KB Output is correct
17 Correct 74 ms 71032 KB Output is correct
18 Correct 76 ms 71032 KB Output is correct
19 Correct 71 ms 71032 KB Output is correct
20 Correct 77 ms 71032 KB Output is correct
21 Correct 70 ms 70904 KB Output is correct
22 Correct 86 ms 71036 KB Output is correct
23 Correct 73 ms 71032 KB Output is correct
24 Correct 72 ms 71032 KB Output is correct
25 Correct 77 ms 70988 KB Output is correct
26 Correct 73 ms 71032 KB Output is correct
27 Correct 74 ms 70904 KB Output is correct
28 Correct 72 ms 70908 KB Output is correct
29 Correct 72 ms 71032 KB Output is correct
30 Correct 78 ms 70904 KB Output is correct
31 Correct 3133 ms 96336 KB Output is correct
32 Correct 184 ms 76908 KB Output is correct
33 Correct 458 ms 94572 KB Output is correct
34 Correct 2203 ms 94624 KB Output is correct
35 Correct 1517 ms 96436 KB Output is correct
36 Correct 497 ms 96360 KB Output is correct
37 Correct 374 ms 93712 KB Output is correct
38 Correct 270 ms 93548 KB Output is correct
39 Correct 232 ms 93476 KB Output is correct
40 Correct 246 ms 93532 KB Output is correct
41 Correct 454 ms 93672 KB Output is correct
42 Correct 431 ms 93488 KB Output is correct
43 Correct 483 ms 79468 KB Output is correct
44 Correct 418 ms 93804 KB Output is correct
45 Correct 337 ms 93568 KB Output is correct
46 Correct 228 ms 93544 KB Output is correct
47 Correct 272 ms 92652 KB Output is correct
48 Correct 195 ms 92636 KB Output is correct
49 Correct 233 ms 92908 KB Output is correct
50 Correct 324 ms 93288 KB Output is correct
51 Correct 192 ms 92904 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 120588 KB Output is correct
2 Correct 3637 ms 134188 KB Output is correct
3 Correct 904 ms 142584 KB Output is correct
4 Correct 911 ms 123664 KB Output is correct
5 Correct 1465 ms 133816 KB Output is correct
6 Correct 2673 ms 134188 KB Output is correct
7 Correct 690 ms 142460 KB Output is correct
8 Correct 686 ms 123640 KB Output is correct
9 Correct 723 ms 117200 KB Output is correct
10 Execution timed out 5086 ms 132860 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1549 ms 122164 KB Output is correct
2 Correct 956 ms 105556 KB Output is correct
3 Correct 4027 ms 162368 KB Output is correct
4 Correct 1423 ms 147588 KB Output is correct
5 Correct 1419 ms 125048 KB Output is correct
6 Correct 1480 ms 128768 KB Output is correct
7 Correct 1911 ms 161884 KB Output is correct
8 Correct 2977 ms 161920 KB Output is correct
9 Correct 1168 ms 148428 KB Output is correct
10 Correct 1224 ms 127432 KB Output is correct
11 Correct 1214 ms 122076 KB Output is correct
12 Execution timed out 5058 ms 160212 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 70904 KB Output is correct
2 Correct 69 ms 70776 KB Output is correct
3 Correct 72 ms 70904 KB Output is correct
4 Correct 69 ms 70776 KB Output is correct
5 Correct 83 ms 70904 KB Output is correct
6 Correct 75 ms 71160 KB Output is correct
7 Correct 80 ms 71032 KB Output is correct
8 Correct 70 ms 71004 KB Output is correct
9 Correct 83 ms 71120 KB Output is correct
10 Correct 76 ms 71032 KB Output is correct
11 Correct 71 ms 71032 KB Output is correct
12 Correct 77 ms 71032 KB Output is correct
13 Correct 71 ms 70924 KB Output is correct
14 Correct 73 ms 71032 KB Output is correct
15 Correct 80 ms 71032 KB Output is correct
16 Correct 71 ms 71004 KB Output is correct
17 Correct 74 ms 71032 KB Output is correct
18 Correct 76 ms 71032 KB Output is correct
19 Correct 71 ms 71032 KB Output is correct
20 Correct 77 ms 71032 KB Output is correct
21 Correct 70 ms 70904 KB Output is correct
22 Correct 86 ms 71036 KB Output is correct
23 Correct 73 ms 71032 KB Output is correct
24 Correct 72 ms 71032 KB Output is correct
25 Correct 77 ms 70988 KB Output is correct
26 Correct 73 ms 71032 KB Output is correct
27 Correct 74 ms 70904 KB Output is correct
28 Correct 72 ms 70908 KB Output is correct
29 Correct 72 ms 71032 KB Output is correct
30 Correct 78 ms 70904 KB Output is correct
31 Correct 3133 ms 96336 KB Output is correct
32 Correct 184 ms 76908 KB Output is correct
33 Correct 458 ms 94572 KB Output is correct
34 Correct 2203 ms 94624 KB Output is correct
35 Correct 1517 ms 96436 KB Output is correct
36 Correct 497 ms 96360 KB Output is correct
37 Correct 374 ms 93712 KB Output is correct
38 Correct 270 ms 93548 KB Output is correct
39 Correct 232 ms 93476 KB Output is correct
40 Correct 246 ms 93532 KB Output is correct
41 Correct 454 ms 93672 KB Output is correct
42 Correct 431 ms 93488 KB Output is correct
43 Correct 483 ms 79468 KB Output is correct
44 Correct 418 ms 93804 KB Output is correct
45 Correct 337 ms 93568 KB Output is correct
46 Correct 228 ms 93544 KB Output is correct
47 Correct 272 ms 92652 KB Output is correct
48 Correct 195 ms 92636 KB Output is correct
49 Correct 233 ms 92908 KB Output is correct
50 Correct 324 ms 93288 KB Output is correct
51 Correct 192 ms 92904 KB Output is correct
52 Correct 321 ms 87824 KB Output is correct
53 Correct 319 ms 85996 KB Output is correct
54 Incorrect 293 ms 83944 KB Output isn't correct
55 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 70904 KB Output is correct
2 Correct 69 ms 70776 KB Output is correct
3 Correct 72 ms 70904 KB Output is correct
4 Correct 69 ms 70776 KB Output is correct
5 Correct 83 ms 70904 KB Output is correct
6 Correct 75 ms 71160 KB Output is correct
7 Correct 80 ms 71032 KB Output is correct
8 Correct 70 ms 71004 KB Output is correct
9 Correct 83 ms 71120 KB Output is correct
10 Correct 76 ms 71032 KB Output is correct
11 Correct 71 ms 71032 KB Output is correct
12 Correct 77 ms 71032 KB Output is correct
13 Correct 71 ms 70924 KB Output is correct
14 Correct 73 ms 71032 KB Output is correct
15 Correct 80 ms 71032 KB Output is correct
16 Correct 71 ms 71004 KB Output is correct
17 Correct 74 ms 71032 KB Output is correct
18 Correct 76 ms 71032 KB Output is correct
19 Correct 71 ms 71032 KB Output is correct
20 Correct 77 ms 71032 KB Output is correct
21 Correct 70 ms 70904 KB Output is correct
22 Correct 86 ms 71036 KB Output is correct
23 Correct 73 ms 71032 KB Output is correct
24 Correct 72 ms 71032 KB Output is correct
25 Correct 77 ms 70988 KB Output is correct
26 Correct 73 ms 71032 KB Output is correct
27 Correct 74 ms 70904 KB Output is correct
28 Correct 72 ms 70908 KB Output is correct
29 Correct 72 ms 71032 KB Output is correct
30 Correct 78 ms 70904 KB Output is correct
31 Correct 3133 ms 96336 KB Output is correct
32 Correct 184 ms 76908 KB Output is correct
33 Correct 458 ms 94572 KB Output is correct
34 Correct 2203 ms 94624 KB Output is correct
35 Correct 1517 ms 96436 KB Output is correct
36 Correct 497 ms 96360 KB Output is correct
37 Correct 374 ms 93712 KB Output is correct
38 Correct 270 ms 93548 KB Output is correct
39 Correct 232 ms 93476 KB Output is correct
40 Correct 246 ms 93532 KB Output is correct
41 Correct 454 ms 93672 KB Output is correct
42 Correct 431 ms 93488 KB Output is correct
43 Correct 483 ms 79468 KB Output is correct
44 Correct 418 ms 93804 KB Output is correct
45 Correct 337 ms 93568 KB Output is correct
46 Correct 228 ms 93544 KB Output is correct
47 Correct 272 ms 92652 KB Output is correct
48 Correct 195 ms 92636 KB Output is correct
49 Correct 233 ms 92908 KB Output is correct
50 Correct 324 ms 93288 KB Output is correct
51 Correct 192 ms 92904 KB Output is correct
52 Correct 899 ms 120588 KB Output is correct
53 Correct 3637 ms 134188 KB Output is correct
54 Correct 904 ms 142584 KB Output is correct
55 Correct 911 ms 123664 KB Output is correct
56 Correct 1465 ms 133816 KB Output is correct
57 Correct 2673 ms 134188 KB Output is correct
58 Correct 690 ms 142460 KB Output is correct
59 Correct 686 ms 123640 KB Output is correct
60 Correct 723 ms 117200 KB Output is correct
61 Execution timed out 5086 ms 132860 KB Time limit exceeded
62 Halted 0 ms 0 KB -