oj.uz

Submission #104121

# Submission time Handle Problem Language Result Execution time Memory
104121 2019-04-04T06:43:53 Z dimash241 New Home (APIO18_new_home) C++17
12 / 100
 5000 ms 169224 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));
	}
}
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 > 400) {
    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 (auto it : add[0]) bl[it.S].insert(it.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);
           		}
    }    
    for (int i = 0; i < pp.size(); ++i) {
    	
      	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));
                
    	}
    }
    } else solve();
	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:172:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < pp.size(); ++i) {
                     ~~^~~~~~~~~~~
new_home.cpp:161:7: warning: unused variable 'f' [-Wunused-variable]
  bool f = 0;
       ^
new_home.cpp:134: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:136: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:139: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 72 ms 71032 KB Output is correct
2 Correct 73 ms 70904 KB Output is correct
3 Correct 74 ms 70776 KB Output is correct
4 Correct 69 ms 70904 KB Output is correct
5 Correct 78 ms 70904 KB Output is correct
6 Correct 76 ms 71004 KB Output is correct
7 Correct 76 ms 71032 KB Output is correct
8 Correct 73 ms 71032 KB Output is correct
9 Correct 73 ms 71160 KB Output is correct
10 Correct 71 ms 71160 KB Output is correct
11 Correct 66 ms 70972 KB Output is correct
12 Correct 70 ms 71032 KB Output is correct
13 Correct 69 ms 71032 KB Output is correct
14 Correct 68 ms 71032 KB Output is correct
15 Correct 79 ms 71032 KB Output is correct
16 Correct 71 ms 71032 KB Output is correct
17 Correct 73 ms 71032 KB Output is correct
18 Correct 88 ms 71004 KB Output is correct
19 Correct 78 ms 71032 KB Output is correct
20 Correct 77 ms 71032 KB Output is correct
21 Correct 71 ms 70904 KB Output is correct
22 Correct 80 ms 71032 KB Output is correct
23 Correct 73 ms 71032 KB Output is correct
24 Correct 75 ms 70980 KB Output is correct
25 Correct 74 ms 71160 KB Output is correct
26 Correct 77 ms 70904 KB Output is correct
27 Correct 71 ms 70904 KB Output is correct
28 Correct 71 ms 71032 KB Output is correct
29 Correct 76 ms 71004 KB Output is correct
30 Correct 68 ms 70928 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 71032 KB Output is correct
2 Correct 73 ms 70904 KB Output is correct
3 Correct 74 ms 70776 KB Output is correct
4 Correct 69 ms 70904 KB Output is correct
5 Correct 78 ms 70904 KB Output is correct
6 Correct 76 ms 71004 KB Output is correct
7 Correct 76 ms 71032 KB Output is correct
8 Correct 73 ms 71032 KB Output is correct
9 Correct 73 ms 71160 KB Output is correct
10 Correct 71 ms 71160 KB Output is correct
11 Correct 66 ms 70972 KB Output is correct
12 Correct 70 ms 71032 KB Output is correct
13 Correct 69 ms 71032 KB Output is correct
14 Correct 68 ms 71032 KB Output is correct
15 Correct 79 ms 71032 KB Output is correct
16 Correct 71 ms 71032 KB Output is correct
17 Correct 73 ms 71032 KB Output is correct
18 Correct 88 ms 71004 KB Output is correct
19 Correct 78 ms 71032 KB Output is correct
20 Correct 77 ms 71032 KB Output is correct
21 Correct 71 ms 70904 KB Output is correct
22 Correct 80 ms 71032 KB Output is correct
23 Correct 73 ms 71032 KB Output is correct
24 Correct 75 ms 70980 KB Output is correct
25 Correct 74 ms 71160 KB Output is correct
26 Correct 77 ms 70904 KB Output is correct
27 Correct 71 ms 70904 KB Output is correct
28 Correct 71 ms 71032 KB Output is correct
29 Correct 76 ms 71004 KB Output is correct
30 Correct 68 ms 70928 KB Output is correct
31 Correct 3240 ms 94832 KB Output is correct
32 Correct 169 ms 76228 KB Output is correct
33 Correct 394 ms 92904 KB Output is correct
34 Correct 2304 ms 93076 KB Output is correct
35 Correct 1361 ms 94752 KB Output is correct
36 Correct 452 ms 94572 KB Output is correct
37 Correct 352 ms 91948 KB Output is correct
38 Correct 286 ms 92008 KB Output is correct
39 Correct 245 ms 91880 KB Output is correct
40 Correct 255 ms 91880 KB Output is correct
41 Correct 498 ms 91752 KB Output is correct
42 Correct 419 ms 91752 KB Output is correct
43 Correct 457 ms 77860 KB Output is correct
44 Correct 409 ms 91984 KB Output is correct
45 Correct 311 ms 91752 KB Output is correct
46 Correct 249 ms 91912 KB Output is correct
47 Correct 217 ms 91256 KB Output is correct
48 Correct 208 ms 91120 KB Output is correct
49 Correct 219 ms 91372 KB Output is correct
50 Correct 410 ms 91808 KB Output is correct
51 Correct 211 ms 91240 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 974 ms 119384 KB Output is correct
2 Correct 4091 ms 132148 KB Output is correct
3 Correct 807 ms 141816 KB Output is correct
4 Correct 914 ms 123024 KB Output is correct
5 Correct 1626 ms 132044 KB Output is correct
6 Correct 2455 ms 132216 KB Output is correct
7 Correct 699 ms 141848 KB Output is correct
8 Correct 731 ms 122980 KB Output is correct
9 Correct 649 ms 116320 KB Output is correct
10 Execution timed out 5085 ms 132148 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1597 ms 121032 KB Output is correct
2 Correct 902 ms 104192 KB Output is correct
3 Correct 4018 ms 160252 KB Output is correct
4 Correct 1312 ms 147088 KB Output is correct
5 Correct 1427 ms 124664 KB Output is correct
6 Correct 1376 ms 128220 KB Output is correct
7 Correct 1745 ms 160092 KB Output is correct
8 Correct 2591 ms 160300 KB Output is correct
9 Correct 1135 ms 148288 KB Output is correct
10 Correct 1129 ms 127324 KB Output is correct
11 Correct 1187 ms 121972 KB Output is correct
12 Execution timed out 5051 ms 160148 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 71032 KB Output is correct
2 Correct 73 ms 70904 KB Output is correct
3 Correct 74 ms 70776 KB Output is correct
4 Correct 69 ms 70904 KB Output is correct
5 Correct 78 ms 70904 KB Output is correct
6 Correct 76 ms 71004 KB Output is correct
7 Correct 76 ms 71032 KB Output is correct
8 Correct 73 ms 71032 KB Output is correct
9 Correct 73 ms 71160 KB Output is correct
10 Correct 71 ms 71160 KB Output is correct
11 Correct 66 ms 70972 KB Output is correct
12 Correct 70 ms 71032 KB Output is correct
13 Correct 69 ms 71032 KB Output is correct
14 Correct 68 ms 71032 KB Output is correct
15 Correct 79 ms 71032 KB Output is correct
16 Correct 71 ms 71032 KB Output is correct
17 Correct 73 ms 71032 KB Output is correct
18 Correct 88 ms 71004 KB Output is correct
19 Correct 78 ms 71032 KB Output is correct
20 Correct 77 ms 71032 KB Output is correct
21 Correct 71 ms 70904 KB Output is correct
22 Correct 80 ms 71032 KB Output is correct
23 Correct 73 ms 71032 KB Output is correct
24 Correct 75 ms 70980 KB Output is correct
25 Correct 74 ms 71160 KB Output is correct
26 Correct 77 ms 70904 KB Output is correct
27 Correct 71 ms 70904 KB Output is correct
28 Correct 71 ms 71032 KB Output is correct
29 Correct 76 ms 71004 KB Output is correct
30 Correct 68 ms 70928 KB Output is correct
31 Correct 3240 ms 94832 KB Output is correct
32 Correct 169 ms 76228 KB Output is correct
33 Correct 394 ms 92904 KB Output is correct
34 Correct 2304 ms 93076 KB Output is correct
35 Correct 1361 ms 94752 KB Output is correct
36 Correct 452 ms 94572 KB Output is correct
37 Correct 352 ms 91948 KB Output is correct
38 Correct 286 ms 92008 KB Output is correct
39 Correct 245 ms 91880 KB Output is correct
40 Correct 255 ms 91880 KB Output is correct
41 Correct 498 ms 91752 KB Output is correct
42 Correct 419 ms 91752 KB Output is correct
43 Correct 457 ms 77860 KB Output is correct
44 Correct 409 ms 91984 KB Output is correct
45 Correct 311 ms 91752 KB Output is correct
46 Correct 249 ms 91912 KB Output is correct
47 Correct 217 ms 91256 KB Output is correct
48 Correct 208 ms 91120 KB Output is correct
49 Correct 219 ms 91372 KB Output is correct
50 Correct 410 ms 91808 KB Output is correct
51 Correct 211 ms 91240 KB Output is correct
52 Runtime error 328 ms 169224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 71032 KB Output is correct
2 Correct 73 ms 70904 KB Output is correct
3 Correct 74 ms 70776 KB Output is correct
4 Correct 69 ms 70904 KB Output is correct
5 Correct 78 ms 70904 KB Output is correct
6 Correct 76 ms 71004 KB Output is correct
7 Correct 76 ms 71032 KB Output is correct
8 Correct 73 ms 71032 KB Output is correct
9 Correct 73 ms 71160 KB Output is correct
10 Correct 71 ms 71160 KB Output is correct
11 Correct 66 ms 70972 KB Output is correct
12 Correct 70 ms 71032 KB Output is correct
13 Correct 69 ms 71032 KB Output is correct
14 Correct 68 ms 71032 KB Output is correct
15 Correct 79 ms 71032 KB Output is correct
16 Correct 71 ms 71032 KB Output is correct
17 Correct 73 ms 71032 KB Output is correct
18 Correct 88 ms 71004 KB Output is correct
19 Correct 78 ms 71032 KB Output is correct
20 Correct 77 ms 71032 KB Output is correct
21 Correct 71 ms 70904 KB Output is correct
22 Correct 80 ms 71032 KB Output is correct
23 Correct 73 ms 71032 KB Output is correct
24 Correct 75 ms 70980 KB Output is correct
25 Correct 74 ms 71160 KB Output is correct
26 Correct 77 ms 70904 KB Output is correct
27 Correct 71 ms 70904 KB Output is correct
28 Correct 71 ms 71032 KB Output is correct
29 Correct 76 ms 71004 KB Output is correct
30 Correct 68 ms 70928 KB Output is correct
31 Correct 3240 ms 94832 KB Output is correct
32 Correct 169 ms 76228 KB Output is correct
33 Correct 394 ms 92904 KB Output is correct
34 Correct 2304 ms 93076 KB Output is correct
35 Correct 1361 ms 94752 KB Output is correct
36 Correct 452 ms 94572 KB Output is correct
37 Correct 352 ms 91948 KB Output is correct
38 Correct 286 ms 92008 KB Output is correct
39 Correct 245 ms 91880 KB Output is correct
40 Correct 255 ms 91880 KB Output is correct
41 Correct 498 ms 91752 KB Output is correct
42 Correct 419 ms 91752 KB Output is correct
43 Correct 457 ms 77860 KB Output is correct
44 Correct 409 ms 91984 KB Output is correct
45 Correct 311 ms 91752 KB Output is correct
46 Correct 249 ms 91912 KB Output is correct
47 Correct 217 ms 91256 KB Output is correct
48 Correct 208 ms 91120 KB Output is correct
49 Correct 219 ms 91372 KB Output is correct
50 Correct 410 ms 91808 KB Output is correct
51 Correct 211 ms 91240 KB Output is correct
52 Correct 974 ms 119384 KB Output is correct
53 Correct 4091 ms 132148 KB Output is correct
54 Correct 807 ms 141816 KB Output is correct
55 Correct 914 ms 123024 KB Output is correct
56 Correct 1626 ms 132044 KB Output is correct
57 Correct 2455 ms 132216 KB Output is correct
58 Correct 699 ms 141848 KB Output is correct
59 Correct 731 ms 122980 KB Output is correct
60 Correct 649 ms 116320 KB Output is correct
61 Execution timed out 5085 ms 132148 KB Time limit exceeded
62 Halted 0 ms 0 KB -