Submission #213311

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
213311	2020-03-25 13:16:43	keko37	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	612 ms	54008 KiB

constellation3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
typedef long long llint;
typedef pair <int, int> pi;
const int MAXN = 200005;
llint n, m, ofs = 1, sum;
llint h[MAXN], x[MAXN], y[MAXN], cost[MAXN], val[MAXN];
llint mx[MAXN * 4], star[MAXN * 4], t[MAXN * 4], prop[MAXN * 4];
vector <int> v[MAXN];
inline int spoji_mx (int a, int b) {return h[a] >= h[b] ? a : b;}
inline int spoji_star (int a, int b) {return val[a] >= val[b] ? a : b;}
void tour_init () {
    for (int i = 0; i < 2*ofs; i++) {
        mx[i] = star[i] = n;
    }
    for (int i = 0; i < n; i++) {
        mx[i + ofs] = star[i + ofs] = i;
        if (v[i].empty()) val[i] = 0; else val[i] = y[v[i].back()];
    }
    for (int i = ofs-1; i > 0; i--) {
        mx[i] = spoji_mx(mx[i * 2], mx[i * 2 + 1]);
        star[i] = spoji_star(star[i * 2], star[i * 2 + 1]);
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65