oj.uz

Submission #587786

# Submission time Handle Problem Language Result Execution time Memory
587786 2022-07-02T11:17:30 Z LastRonin Team Contest (JOI22_team) C++14
73 / 100
 2000 ms 919592 KB 
#pragma GCC optimize("O3")

#include <bits/stdc++.h> 
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define pill pair<ll, ll>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

const int N = 2e5 + 1;
const int M = 5E5 + 1;
const ll hsh[2] = {1555555699, 1222222763};
const ll P = 113;

int n;    
int a[N], b[N], c[N];
int sa[N], sb[N], sc[N];


struct node {
	node *l = nullptr, *r = nullptr;
	int val = 0;
} *Brt = new node(), *Crt = new node();

struct tdnode {
	tdnode *l = nullptr, *r = nullptr;
	node *val = nullptr;
	tdnode() {
		val = new node();
	}
} *tdrt = new tdnode();

vector<ll> scan[M];

void upd(int p, int z, node *v, ll tl = 0, ll tr = 1e8 + 1) {
	if(tl == tr) {
		v->val = max(v->val, z);
		return;
	}
	ll m = (tl + tr) >> 1ll;
	if(p <= m) {
		if(!v->l)v->l = new node();
		upd(p, z, v->l, tl, m);
	} else {
		if(!v->r)v->r = new node();
		upd(p, z, v->r, m + 1, tr);
	}
	v->val = max(v->val, z);
}
int get(int l, int r, node *v, ll tl = 0, ll tr = 1e8 + 1) {
	if(l > tr || tl > r || !v) 
		return 0;
	if(l <= tl && tr <= r) 
		return v->val;
	ll m = (tl + tr) >> 1ll;
	return max(get(l, r, v->l, tl, m), get(l, r, v->r, m + 1, tr));
}

void upd2(ll x, ll y, ll z, tdnode *v, ll tl = 0, ll tr = 1e8 + 1) {
	if(tl == tr) {
		upd(y, z, v->val);
		return;
	}
	ll m = (tl + tr) >> 1ll;
	if(x <= m) {
		if(!v->l)v->l = new tdnode();
		upd2(x, y, z, v->l, tl, m);
	} else {
		if(!v->r)v->r = new tdnode();
		upd2(x, y, z, v->r, m + 1, tr);
	}
	upd(y, z, v->val);
}

int get2(int lx, int rx, int ly, int ry, tdnode *v, ll tl = 0, ll  tr = 1e8 + 1) {
	if(lx > tr || rx < tl || !v)return 0;
	if(lx <= tl && tr <= rx) {
		return get(ly, ry, v->val);
	}
	ll m = (tl + tr) >> 1ll;
	return max(get2(lx, rx, ly, ry, v->l, tl , m), get2(lx, rx, ly, ry, v->r, m + 1, tr));
}


bool comp2(int i, int j) {
	return b[i] < b[j];
}

bool comp1(int i, int j) {
	return c[i] < c[j];
}

int main() {
	speed;
	cin >> n;
	vector<int> g;
	for(int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i] >> c[i];
		g.pb(a[i]);
		g.pb(b[i]);
		g.pb(c[i]);
	}
	sort(g.begin(), g.end());
	g.erase(unique(g.begin(), g.end()), g.end());
	for(int j = 1; j <= n; j++) {
		sa[j] = lower_bound(g.begin(), g.end(), a[j]) - g.begin() + 1;
		scan[sa[j]].pb(j);		
	}
	ll sum = -1;
	for(int i = 1; i <= g.size(); i++) {
		for(auto u : scan[i]) {
			ll z = get2(b[u] + 1, 1e8, c[u] + 1, 1e8, tdrt);		
			if(z)sum = max(sum, a[u] + z);
		}
		vector<pill> aa;
		sort(scan[i].begin(), scan[i].end(), comp1);
		for(auto u : scan[i]) {
			upd(c[u], b[u], Crt);	
			ll gt2 = get(0, c[u] - 1, Crt);
			if(gt2 > b[u])aa.pb(mp(gt2, c[u]));								
		}
		sort(scan[i].begin(), scan[i].end(), comp2);
		for(auto u : scan[i]) {
			upd(b[u], c[u], Brt);
			ll gt = get(0, b[u] - 1, Brt);
			if(gt > c[u])aa.pb(mp(b[u], gt));
		}
		for(auto u : aa) {
			upd2(u.f, u.s, u.f + u.s, tdrt);
		}
	}
	cout << sum;
}

Compilation message

team.cpp: In function 'int main()':
team.cpp:113:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |  for(int i = 1; i <= g.size(); i++) {
      |                 ~~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 7 ms 12024 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 12012 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 6 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 10 ms 12052 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 7 ms 11984 KB Output is correct
13 Correct 6 ms 12068 KB Output is correct
14 Correct 20 ms 22732 KB Output is correct
15 Correct 10 ms 14932 KB Output is correct
16 Correct 13 ms 17620 KB Output is correct
17 Correct 10 ms 14652 KB Output is correct
18 Correct 9 ms 12756 KB Output is correct
19 Correct 8 ms 12372 KB Output is correct
20 Correct 7 ms 12116 KB Output is correct
21 Correct 8 ms 12116 KB Output is correct
22 Correct 7 ms 12372 KB Output is correct
23 Correct 7 ms 12108 KB Output is correct
24 Correct 7 ms 12092 KB Output is correct
25 Correct 7 ms 12116 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 7 ms 12024 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 12012 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 6 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 10 ms 12052 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 7 ms 11984 KB Output is correct
13 Correct 6 ms 12068 KB Output is correct
14 Correct 20 ms 22732 KB Output is correct
15 Correct 10 ms 14932 KB Output is correct
16 Correct 13 ms 17620 KB Output is correct
17 Correct 10 ms 14652 KB Output is correct
18 Correct 9 ms 12756 KB Output is correct
19 Correct 8 ms 12372 KB Output is correct
20 Correct 7 ms 12116 KB Output is correct
21 Correct 8 ms 12116 KB Output is correct
22 Correct 7 ms 12372 KB Output is correct
23 Correct 7 ms 12108 KB Output is correct
24 Correct 7 ms 12092 KB Output is correct
25 Correct 7 ms 12116 KB Output is correct
26 Correct 189 ms 134556 KB Output is correct
27 Correct 129 ms 86604 KB Output is correct
28 Correct 147 ms 82260 KB Output is correct
29 Correct 53 ms 42708 KB Output is correct
30 Correct 27 ms 18580 KB Output is correct
31 Correct 44 ms 16904 KB Output is correct
32 Correct 23 ms 13980 KB Output is correct
33 Correct 15 ms 13364 KB Output is correct
34 Correct 16 ms 16200 KB Output is correct
35 Correct 7 ms 12116 KB Output is correct
36 Correct 7 ms 12112 KB Output is correct
37 Correct 10 ms 12372 KB Output is correct
38 Correct 11 ms 12380 KB Output is correct
39 Correct 17 ms 12284 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 8 ms 12040 KB Output is correct
3 Correct 8 ms 11988 KB Output is correct
4 Correct 7 ms 12060 KB Output is correct
5 Correct 9 ms 11996 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 8 ms 12116 KB Output is correct
9 Correct 7 ms 11976 KB Output is correct
10 Correct 7 ms 11988 KB Output is correct
11 Correct 659 ms 19176 KB Output is correct
12 Correct 318 ms 16660 KB Output is correct
13 Correct 108 ms 17708 KB Output is correct
14 Correct 387 ms 20916 KB Output is correct
15 Correct 253 ms 21860 KB Output is correct
16 Correct 100 ms 20076 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 8 ms 12040 KB Output is correct
3 Correct 8 ms 11988 KB Output is correct
4 Correct 7 ms 12060 KB Output is correct
5 Correct 9 ms 11996 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 8 ms 12116 KB Output is correct
9 Correct 7 ms 11976 KB Output is correct
10 Correct 7 ms 11988 KB Output is correct
11 Correct 659 ms 19176 KB Output is correct
12 Correct 318 ms 16660 KB Output is correct
13 Correct 108 ms 17708 KB Output is correct
14 Correct 387 ms 20916 KB Output is correct
15 Correct 253 ms 21860 KB Output is correct
16 Correct 100 ms 20076 KB Output is correct
17 Correct 9 ms 11988 KB Output is correct
18 Correct 9 ms 11988 KB Output is correct
19 Correct 7 ms 12080 KB Output is correct
20 Correct 9 ms 12116 KB Output is correct
21 Correct 18 ms 12300 KB Output is correct
22 Correct 797 ms 19112 KB Output is correct
23 Correct 609 ms 19244 KB Output is correct
24 Correct 381 ms 17712 KB Output is correct
25 Correct 464 ms 19888 KB Output is correct
26 Correct 261 ms 21692 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 8 ms 12040 KB Output is correct
3 Correct 8 ms 11988 KB Output is correct
4 Correct 7 ms 12060 KB Output is correct
5 Correct 9 ms 11996 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 8 ms 12116 KB Output is correct
9 Correct 7 ms 11976 KB Output is correct
10 Correct 7 ms 11988 KB Output is correct
11 Correct 659 ms 19176 KB Output is correct
12 Correct 318 ms 16660 KB Output is correct
13 Correct 108 ms 17708 KB Output is correct
14 Correct 387 ms 20916 KB Output is correct
15 Correct 253 ms 21860 KB Output is correct
16 Correct 100 ms 20076 KB Output is correct
17 Correct 9 ms 11988 KB Output is correct
18 Correct 9 ms 11988 KB Output is correct
19 Correct 7 ms 12080 KB Output is correct
20 Correct 9 ms 12116 KB Output is correct
21 Correct 18 ms 12300 KB Output is correct
22 Correct 797 ms 19112 KB Output is correct
23 Correct 609 ms 19244 KB Output is correct
24 Correct 381 ms 17712 KB Output is correct
25 Correct 464 ms 19888 KB Output is correct
26 Correct 261 ms 21692 KB Output is correct
27 Correct 13 ms 12712 KB Output is correct
28 Correct 11 ms 12332 KB Output is correct
29 Correct 8 ms 12116 KB Output is correct
30 Correct 9 ms 12116 KB Output is correct
31 Correct 24 ms 13976 KB Output is correct
32 Correct 8 ms 12116 KB Output is correct
33 Correct 9 ms 12212 KB Output is correct
34 Correct 977 ms 20032 KB Output is correct
35 Correct 761 ms 23356 KB Output is correct
36 Correct 825 ms 24364 KB Output is correct
37 Correct 595 ms 25292 KB Output is correct
38 Correct 291 ms 22468 KB Output is correct
39 Correct 553 ms 22900 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 8 ms 12040 KB Output is correct
3 Correct 8 ms 11988 KB Output is correct
4 Correct 7 ms 12060 KB Output is correct
5 Correct 9 ms 11996 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 8 ms 12116 KB Output is correct
9 Correct 7 ms 11976 KB Output is correct
10 Correct 7 ms 11988 KB Output is correct
11 Correct 659 ms 19176 KB Output is correct
12 Correct 318 ms 16660 KB Output is correct
13 Correct 108 ms 17708 KB Output is correct
14 Correct 387 ms 20916 KB Output is correct
15 Correct 253 ms 21860 KB Output is correct
16 Correct 100 ms 20076 KB Output is correct
17 Correct 9 ms 11988 KB Output is correct
18 Correct 9 ms 11988 KB Output is correct
19 Correct 7 ms 12080 KB Output is correct
20 Correct 9 ms 12116 KB Output is correct
21 Correct 18 ms 12300 KB Output is correct
22 Correct 797 ms 19112 KB Output is correct
23 Correct 609 ms 19244 KB Output is correct
24 Correct 381 ms 17712 KB Output is correct
25 Correct 464 ms 19888 KB Output is correct
26 Correct 261 ms 21692 KB Output is correct
27 Correct 13 ms 12712 KB Output is correct
28 Correct 11 ms 12332 KB Output is correct
29 Correct 8 ms 12116 KB Output is correct
30 Correct 9 ms 12116 KB Output is correct
31 Correct 24 ms 13976 KB Output is correct
32 Correct 8 ms 12116 KB Output is correct
33 Correct 9 ms 12212 KB Output is correct
34 Correct 977 ms 20032 KB Output is correct
35 Correct 761 ms 23356 KB Output is correct
36 Correct 825 ms 24364 KB Output is correct
37 Correct 595 ms 25292 KB Output is correct
38 Correct 291 ms 22468 KB Output is correct
39 Correct 553 ms 22900 KB Output is correct
40 Correct 32 ms 18568 KB Output is correct
41 Correct 55 ms 16972 KB Output is correct
42 Correct 13 ms 12408 KB Output is correct
43 Correct 14 ms 12476 KB Output is correct
44 Correct 1782 ms 37224 KB Output is correct
45 Correct 1026 ms 93524 KB Output is correct
46 Correct 1215 ms 84600 KB Output is correct
47 Correct 875 ms 99572 KB Output is correct
48 Correct 382 ms 22544 KB Output is correct

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 7 ms 12024 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 12012 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 6 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 10 ms 12052 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 7 ms 11984 KB Output is correct
13 Correct 6 ms 12068 KB Output is correct
14 Correct 20 ms 22732 KB Output is correct
15 Correct 10 ms 14932 KB Output is correct
16 Correct 13 ms 17620 KB Output is correct
17 Correct 10 ms 14652 KB Output is correct
18 Correct 9 ms 12756 KB Output is correct
19 Correct 8 ms 12372 KB Output is correct
20 Correct 7 ms 12116 KB Output is correct
21 Correct 8 ms 12116 KB Output is correct
22 Correct 7 ms 12372 KB Output is correct
23 Correct 7 ms 12108 KB Output is correct
24 Correct 7 ms 12092 KB Output is correct
25 Correct 7 ms 12116 KB Output is correct
26 Correct 189 ms 134556 KB Output is correct
27 Correct 129 ms 86604 KB Output is correct
28 Correct 147 ms 82260 KB Output is correct
29 Correct 53 ms 42708 KB Output is correct
30 Correct 27 ms 18580 KB Output is correct
31 Correct 44 ms 16904 KB Output is correct
32 Correct 23 ms 13980 KB Output is correct
33 Correct 15 ms 13364 KB Output is correct
34 Correct 16 ms 16200 KB Output is correct
35 Correct 7 ms 12116 KB Output is correct
36 Correct 7 ms 12112 KB Output is correct
37 Correct 10 ms 12372 KB Output is correct
38 Correct 11 ms 12380 KB Output is correct
39 Correct 17 ms 12284 KB Output is correct
40 Correct 7 ms 12116 KB Output is correct
41 Correct 8 ms 12040 KB Output is correct
42 Correct 8 ms 11988 KB Output is correct
43 Correct 7 ms 12060 KB Output is correct
44 Correct 9 ms 11996 KB Output is correct
45 Correct 7 ms 11988 KB Output is correct
46 Correct 7 ms 12116 KB Output is correct
47 Correct 8 ms 12116 KB Output is correct
48 Correct 7 ms 11976 KB Output is correct
49 Correct 7 ms 11988 KB Output is correct
50 Correct 659 ms 19176 KB Output is correct
51 Correct 318 ms 16660 KB Output is correct
52 Correct 108 ms 17708 KB Output is correct
53 Correct 387 ms 20916 KB Output is correct
54 Correct 253 ms 21860 KB Output is correct
55 Correct 100 ms 20076 KB Output is correct
56 Correct 9 ms 11988 KB Output is correct
57 Correct 9 ms 11988 KB Output is correct
58 Correct 7 ms 12080 KB Output is correct
59 Correct 9 ms 12116 KB Output is correct
60 Correct 18 ms 12300 KB Output is correct
61 Correct 797 ms 19112 KB Output is correct
62 Correct 609 ms 19244 KB Output is correct
63 Correct 381 ms 17712 KB Output is correct
64 Correct 464 ms 19888 KB Output is correct
65 Correct 261 ms 21692 KB Output is correct
66 Correct 13 ms 12712 KB Output is correct
67 Correct 11 ms 12332 KB Output is correct
68 Correct 8 ms 12116 KB Output is correct
69 Correct 9 ms 12116 KB Output is correct
70 Correct 24 ms 13976 KB Output is correct
71 Correct 8 ms 12116 KB Output is correct
72 Correct 9 ms 12212 KB Output is correct
73 Correct 977 ms 20032 KB Output is correct
74 Correct 761 ms 23356 KB Output is correct
75 Correct 825 ms 24364 KB Output is correct
76 Correct 595 ms 25292 KB Output is correct
77 Correct 291 ms 22468 KB Output is correct
78 Correct 553 ms 22900 KB Output is correct
79 Correct 32 ms 18568 KB Output is correct
80 Correct 55 ms 16972 KB Output is correct
81 Correct 13 ms 12408 KB Output is correct
82 Correct 14 ms 12476 KB Output is correct
83 Correct 1782 ms 37224 KB Output is correct
84 Correct 1026 ms 93524 KB Output is correct
85 Correct 1215 ms 84600 KB Output is correct
86 Correct 875 ms 99572 KB Output is correct
87 Correct 382 ms 22544 KB Output is correct
88 Execution timed out 2119 ms 919592 KB Time limit exceeded
89 Halted 0 ms 0 KB -