# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
819312 |
2023-08-10T09:18:10 Z |
sentheta |
Tourism (JOI23_tourism) |
C++17 |
|
2724 ms |
33400 KB |
// author : sentheta aka vanwij
#ifdef VANWIJ
#include"/home/user/code/bits/stdc++.h"
#define DBG 1
#else
#include"bits/stdc++.h"
#define DBG 0
#endif
using namespace std;
#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second
static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))
#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}
// #define int long long
// const Int MOD = 1e9+7;
const Int MOD = 998244353;
Int bpow(Int a,Int b){
Int ret = 1;
for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}
void solve(); int TC, ALLTC;
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(7);
// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
solve();
}
const int N = 1e5+69;
const int LN = 18;
const int SN = 600;
int hilbert(int x, int y){
int d = 0;
for(int s=1LL<<(LN-1); s; s>>=1){
bool rx=x&s, ry=y&s;
d = d<<2 | rx*3^ry;
if(!ry){ if(rx){
x = (1<<LN)-x; y = (1<<LN)-y;
} swap(x,y); }
} return d;
}
int n, m, q;
int a[N];
// tree utilities
V<int> adj[N];
int d[N], p[N];
int getMinDepth(int x,int y){
return d[x]<d[y] ? x : y;
}
int getMaxDepth(int x,int y){
return d[x]>d[y] ? x : y;
}
struct Stable{
int v[2*N][LN];
void build(){
rep(lg,1,LN) for(int i=0; i+(1<<lg)-1<2*N; i++)
v[i][lg] = getMinDepth(v[i][lg-1], v[i+(1<<(lg-1))][lg-1]);
}
int qry(int l,int r){
int lg = __lg(r-l+1);
return getMinDepth(v[l][lg], v[r-(1<<lg)+1][lg]);
}
} stable;
int t[N], tim;
int getLca(int x,int y){
if(!(t[x]<t[y])) swap(x,y);
return stable.qry(t[x],t[y]);
}
void dfs_init(int x=1){
t[x] = tim;
stable.v[tim++][0] = x;
for(int y : adj[x]) if(y!=p[x]){
d[y] = d[x]+1;
p[y] = x;
dfs_init(y);
stable.v[tim++][0] = x;
}
}
// s = {t[nodes]}
// multiset<int> s;
#define ull unsigned long long
// van Emde Boas tree. Maintains a set of integers in range [0, 2^B) and supports operations
// findNext(i): returns minimum j >= i in set, or 2^B if none exist
// findPrev(i): returns maximum j <= i in set, or -1 if none exist
// insert(i), erase(i): insert/erase i into the set
// empty(): returns TRUE if the set is empty
// clear(): empties the set
// init(bts): inits the set, after the call i will be in the set if bts[i] = 1. bts should be a bitset, but can be a vector of 0/1
// All operations except empty, clear and init are O(log B) = O(log log 2^B) with good constants
template<int B, typename ENABLE = void>
class VEBTree {
private:
const static int K = B / 2, R = (B + 1) / 2, M = (1 << B);
const static int S = 1 << K, MASK = (1 << R) - 1;
array<VEBTree<R>, S> ch;
VEBTree<K> act;
int mi, ma;
public:
bool empty() const { return ma < mi; }
int findNext(int i) const {
if (i <= mi) return mi;
if (i > ma) return M;
int j = i >> R, x = i & MASK;
int res = ch[j].findNext(x);
if (res <= MASK) return (j << R) + res;
j = act.findNext(j + 1);
return (j >= S) ? ma : ((j << R) + ch[j].findNext(0));
}
int findPrev(int i) const {
if (i >= ma) return ma;
if (i < mi) return -1;
int j = i >> R, x = i & MASK;
int res = ch[j].findPrev(x);
if (res >= 0) return (j << R) + res;
j = act.findPrev(j - 1);
return (j < 0) ? mi : ((j << R) + ch[j].findPrev(MASK));
}
void insert(int i) {
if (i <= mi) {
if (i == mi) return;
swap(mi, i);
if (i == M) ma = mi; // we were empty
if (i >= ma) return; // we had mi == ma
} else if (i >= ma) {
if (i == ma) return;
swap(ma, i);
if (i <= mi) return; // we had mi == ma
}
int j = i >> R;
if (ch[j].empty()) act.insert(j);
ch[j].insert(i & MASK);
}
void erase(int i) {
if (i <= mi) {
if (i < mi) return;
i = mi = findNext(mi + 1);
if (i >= ma) {
if (i > ma) ma = -1; // we had mi == ma
return; // after erase we have mi == ma
}
} else if (i >= ma) {
if (i > ma) return;
i = ma = findPrev(ma - 1);
if (i <= mi) return; // after erase we have mi == ma
}
int j = i >> R;
ch[j].erase(i & MASK);
if (ch[j].empty()) act.erase(j);
}
void clear() {
mi = M, ma = -1;
act.clear();
for (int i = 0; i < S; ++i) ch[i].clear();
}
template<class T>
void init(const T& bts, int shift = 0, int s0 = 0, int s1 = 0) {
s0 = -shift + bts.findNext(shift + s0, shift + M-1 - s1);
s1 = M-1 - (-shift + bts.findPrev(shift + M-1-s1, shift + s0));
if (s0 + s1 >= M) clear();
else {
act.clear();
mi = s0, ma = M-1 - s1;
++s0; ++s1;
for (int j = 0; j < S; ++j) {
ch[j].init(bts, shift + (j << R), max(0, s0 - (j << R)), max(0, s1 - ((S-1-j) << R)));
if (! ch[j].empty()) act.insert(j);
}
}
}
};
template<int B>
class VEBTree<B, enable_if_t<(B <= 6)>> {
private:
const static int M = (1 << B);
ull act;
public:
bool empty() const { return !act; }
void clear() { act = 0; }
int findNext(int i) const {
return ((i < M) && (act >> i)) ? i + __builtin_ctzll(act >> i) : M;
}
int findPrev(int i) const {
return ((i != -1) && (act << (63 - i))) ? i - __builtin_clzll(act << (63 - i)) : -1;
}
void insert(int i) { act |= 1ull << i; }
void erase(int i) { act &= ~(1ull << i); }
template<class T>
void init(const T& bts, int shift = 0, int s0 = 0, int s1 = 0) {
if (s0 + s1 >= M) act = 0;
else act = bts.getRange(shift + s0, shift + M-1-s1) << s0;
}
};
#undef ull
VEBTree<LN> s;
int cnt[2*N];
int pathlen = 0;
int getSemipath(int i,int j){
return d[stable.v[j][0]] - d[stable.qry(i,j)];
// assert(i <= j);
// int u = stable.v[i][0];
// int v = stable.v[j][0];
// return d[v] - d[getLca(u,v)];
}
void insert(int i){
cnt[i]++;
// assert(cnt[i]>=0);
if(cnt[i] > 1) return;
int prvi = s.findPrev(i);
int nxti = s.findNext(i);
s.insert(i);
// remove prv-nxt
if(prvi!=-1 && nxti!=(1<<LN)){
pathlen -= getSemipath(prvi, nxti);
}
// connect prv-i
if(prvi!=-1){
pathlen += getSemipath(prvi, i);
}
// connect i-nxt
if(nxti!=(1<<LN)){
pathlen += getSemipath(i, nxti);
}
}
void erase(int i){
cnt[i]--;
// assert(cnt[i]>=0);
if(cnt[i] >= 1) return;
s.erase(i);
int prvi = s.findPrev(i);
int nxti = s.findNext(i);
// remove prv-i
if(prvi!=-1){
pathlen -= getSemipath(prvi, i);
}
// remove i-nxt
if(nxti!=(1<<LN)){
pathlen -= getSemipath(i, nxti);
}
// connect prv-nxt
if(prvi!=-1 && nxti!=(1<<LN)){
pathlen += getSemipath(prvi, nxti);
}
}
int ql[N], qr[N], qans[N];
int qhsh[N];
void solve(){
cin >> n >> m >> q;
rep(i,0,n-1){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs_init();
stable.build();
// rep(i,1,n+1) cerr << t[i] << " ";
// cerr << nl;
rep(i,1,m+1){
cin >> a[i];
}
V<int> ord;
rep(i,1,q+1){
cin >> ql[i] >> qr[i];
ord.push_back(i);
// qhsh[i] = hilbert(ql[i], qr[i]);
}
sort(all(ord),[&](int i,int j){
// return qhsh[i] < qhsh[j];
if(ql[i]/SN==ql[j]/SN) return qr[i] < qr[j];
return ql[i]/SN < ql[j]/SN;
});
int l=1, r=1;
s.clear();
insert(t[a[1]]);
for(int i : ord){
while(ql[i] < l) insert(t[a[--l]]);
while(r < qr[i]) insert(t[a[++r]]);
while(l < ql[i]) erase(t[a[l++]]);
while(qr[i] < r) erase(t[a[r--]]);
// assert(l==ql[i] && r==qr[i]);
// leftmost and rightmost node
int li = s.findNext(0);
int ri = s.findPrev((1<<LN)-1);
int u = stable.v[li][0];
int v = stable.v[ri][0];
int lca = getLca(u,v);
// dbg(pathlen);
int ans = pathlen + d[u]-d[lca];
// int ans = pathlen + d[stable.v[li][0]]-d[stable.qry(li,ri)];
qans[i] = ans;
}
rep(i,1,q+1){
cout << qans[i]+1 << nl;
}
}
Compilation message
tourism.cpp: In function 'int hilbert(int, int)':
tourism.cpp:68:18: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
68 | d = d<<2 | rx*3^ry;
| ~~~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
16784 KB |
Output is correct |
2 |
Correct |
19 ms |
16864 KB |
Output is correct |
3 |
Correct |
23 ms |
16796 KB |
Output is correct |
4 |
Correct |
18 ms |
16800 KB |
Output is correct |
5 |
Correct |
19 ms |
16864 KB |
Output is correct |
6 |
Correct |
20 ms |
16796 KB |
Output is correct |
7 |
Correct |
23 ms |
16812 KB |
Output is correct |
8 |
Correct |
30 ms |
16800 KB |
Output is correct |
9 |
Correct |
24 ms |
16852 KB |
Output is correct |
10 |
Correct |
20 ms |
16852 KB |
Output is correct |
11 |
Correct |
23 ms |
16824 KB |
Output is correct |
12 |
Correct |
21 ms |
16872 KB |
Output is correct |
13 |
Correct |
24 ms |
16844 KB |
Output is correct |
14 |
Correct |
21 ms |
16812 KB |
Output is correct |
15 |
Correct |
20 ms |
16820 KB |
Output is correct |
16 |
Correct |
19 ms |
16844 KB |
Output is correct |
17 |
Correct |
21 ms |
16820 KB |
Output is correct |
18 |
Correct |
21 ms |
16816 KB |
Output is correct |
19 |
Correct |
20 ms |
16820 KB |
Output is correct |
20 |
Correct |
19 ms |
16852 KB |
Output is correct |
21 |
Correct |
19 ms |
16852 KB |
Output is correct |
22 |
Correct |
18 ms |
16844 KB |
Output is correct |
23 |
Correct |
19 ms |
16852 KB |
Output is correct |
24 |
Correct |
21 ms |
16808 KB |
Output is correct |
25 |
Correct |
19 ms |
16824 KB |
Output is correct |
26 |
Correct |
24 ms |
17016 KB |
Output is correct |
27 |
Correct |
18 ms |
16800 KB |
Output is correct |
28 |
Correct |
18 ms |
16808 KB |
Output is correct |
29 |
Correct |
18 ms |
16816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
16784 KB |
Output is correct |
2 |
Correct |
19 ms |
16864 KB |
Output is correct |
3 |
Correct |
23 ms |
16796 KB |
Output is correct |
4 |
Correct |
18 ms |
16800 KB |
Output is correct |
5 |
Correct |
19 ms |
16864 KB |
Output is correct |
6 |
Correct |
20 ms |
16796 KB |
Output is correct |
7 |
Correct |
23 ms |
16812 KB |
Output is correct |
8 |
Correct |
30 ms |
16800 KB |
Output is correct |
9 |
Correct |
24 ms |
16852 KB |
Output is correct |
10 |
Correct |
20 ms |
16852 KB |
Output is correct |
11 |
Correct |
23 ms |
16824 KB |
Output is correct |
12 |
Correct |
21 ms |
16872 KB |
Output is correct |
13 |
Correct |
24 ms |
16844 KB |
Output is correct |
14 |
Correct |
21 ms |
16812 KB |
Output is correct |
15 |
Correct |
20 ms |
16820 KB |
Output is correct |
16 |
Correct |
19 ms |
16844 KB |
Output is correct |
17 |
Correct |
21 ms |
16820 KB |
Output is correct |
18 |
Correct |
21 ms |
16816 KB |
Output is correct |
19 |
Correct |
20 ms |
16820 KB |
Output is correct |
20 |
Correct |
19 ms |
16852 KB |
Output is correct |
21 |
Correct |
19 ms |
16852 KB |
Output is correct |
22 |
Correct |
18 ms |
16844 KB |
Output is correct |
23 |
Correct |
19 ms |
16852 KB |
Output is correct |
24 |
Correct |
21 ms |
16808 KB |
Output is correct |
25 |
Correct |
19 ms |
16824 KB |
Output is correct |
26 |
Correct |
24 ms |
17016 KB |
Output is correct |
27 |
Correct |
18 ms |
16800 KB |
Output is correct |
28 |
Correct |
18 ms |
16808 KB |
Output is correct |
29 |
Correct |
18 ms |
16816 KB |
Output is correct |
30 |
Correct |
28 ms |
16992 KB |
Output is correct |
31 |
Correct |
28 ms |
16920 KB |
Output is correct |
32 |
Correct |
31 ms |
17012 KB |
Output is correct |
33 |
Correct |
30 ms |
17016 KB |
Output is correct |
34 |
Correct |
35 ms |
17004 KB |
Output is correct |
35 |
Correct |
28 ms |
17012 KB |
Output is correct |
36 |
Correct |
28 ms |
17000 KB |
Output is correct |
37 |
Correct |
21 ms |
16980 KB |
Output is correct |
38 |
Correct |
29 ms |
17096 KB |
Output is correct |
39 |
Correct |
29 ms |
17096 KB |
Output is correct |
40 |
Correct |
32 ms |
17112 KB |
Output is correct |
41 |
Correct |
21 ms |
17120 KB |
Output is correct |
42 |
Correct |
20 ms |
17108 KB |
Output is correct |
43 |
Correct |
23 ms |
17072 KB |
Output is correct |
44 |
Correct |
32 ms |
17088 KB |
Output is correct |
45 |
Correct |
31 ms |
17036 KB |
Output is correct |
46 |
Correct |
32 ms |
17068 KB |
Output is correct |
47 |
Correct |
20 ms |
17044 KB |
Output is correct |
48 |
Correct |
24 ms |
17036 KB |
Output is correct |
49 |
Correct |
19 ms |
17048 KB |
Output is correct |
50 |
Correct |
28 ms |
17040 KB |
Output is correct |
51 |
Correct |
34 ms |
17012 KB |
Output is correct |
52 |
Correct |
28 ms |
16968 KB |
Output is correct |
53 |
Correct |
28 ms |
17028 KB |
Output is correct |
54 |
Correct |
28 ms |
17024 KB |
Output is correct |
55 |
Correct |
29 ms |
17020 KB |
Output is correct |
56 |
Correct |
23 ms |
16928 KB |
Output is correct |
57 |
Correct |
19 ms |
17020 KB |
Output is correct |
58 |
Correct |
21 ms |
16956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
16792 KB |
Output is correct |
2 |
Correct |
20 ms |
16792 KB |
Output is correct |
3 |
Correct |
26 ms |
16848 KB |
Output is correct |
4 |
Correct |
1036 ms |
24984 KB |
Output is correct |
5 |
Correct |
978 ms |
29500 KB |
Output is correct |
6 |
Correct |
1166 ms |
30676 KB |
Output is correct |
7 |
Correct |
1783 ms |
33328 KB |
Output is correct |
8 |
Correct |
1643 ms |
33284 KB |
Output is correct |
9 |
Correct |
1623 ms |
33276 KB |
Output is correct |
10 |
Correct |
1667 ms |
33400 KB |
Output is correct |
11 |
Correct |
1687 ms |
33280 KB |
Output is correct |
12 |
Correct |
183 ms |
33084 KB |
Output is correct |
13 |
Correct |
199 ms |
33060 KB |
Output is correct |
14 |
Correct |
194 ms |
33040 KB |
Output is correct |
15 |
Correct |
68 ms |
30868 KB |
Output is correct |
16 |
Correct |
85 ms |
32844 KB |
Output is correct |
17 |
Correct |
147 ms |
20420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
16852 KB |
Output is correct |
2 |
Correct |
42 ms |
19968 KB |
Output is correct |
3 |
Correct |
53 ms |
20292 KB |
Output is correct |
4 |
Correct |
54 ms |
20672 KB |
Output is correct |
5 |
Correct |
59 ms |
22440 KB |
Output is correct |
6 |
Correct |
60 ms |
22376 KB |
Output is correct |
7 |
Correct |
74 ms |
22460 KB |
Output is correct |
8 |
Correct |
76 ms |
22340 KB |
Output is correct |
9 |
Correct |
69 ms |
22444 KB |
Output is correct |
10 |
Correct |
73 ms |
22348 KB |
Output is correct |
11 |
Correct |
80 ms |
22460 KB |
Output is correct |
12 |
Correct |
68 ms |
22456 KB |
Output is correct |
13 |
Correct |
84 ms |
22760 KB |
Output is correct |
14 |
Correct |
74 ms |
23112 KB |
Output is correct |
15 |
Correct |
84 ms |
24260 KB |
Output is correct |
16 |
Correct |
68 ms |
22644 KB |
Output is correct |
17 |
Correct |
80 ms |
22596 KB |
Output is correct |
18 |
Correct |
81 ms |
22656 KB |
Output is correct |
19 |
Correct |
65 ms |
22464 KB |
Output is correct |
20 |
Correct |
67 ms |
22404 KB |
Output is correct |
21 |
Correct |
62 ms |
22340 KB |
Output is correct |
22 |
Correct |
64 ms |
22344 KB |
Output is correct |
23 |
Correct |
65 ms |
22376 KB |
Output is correct |
24 |
Correct |
68 ms |
22336 KB |
Output is correct |
25 |
Correct |
67 ms |
22316 KB |
Output is correct |
26 |
Correct |
68 ms |
22364 KB |
Output is correct |
27 |
Correct |
68 ms |
22464 KB |
Output is correct |
28 |
Correct |
73 ms |
22432 KB |
Output is correct |
29 |
Correct |
80 ms |
22476 KB |
Output is correct |
30 |
Correct |
75 ms |
22576 KB |
Output is correct |
31 |
Correct |
77 ms |
22632 KB |
Output is correct |
32 |
Correct |
73 ms |
22900 KB |
Output is correct |
33 |
Correct |
72 ms |
23420 KB |
Output is correct |
34 |
Correct |
82 ms |
24300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
16852 KB |
Output is correct |
2 |
Correct |
18 ms |
16844 KB |
Output is correct |
3 |
Correct |
20 ms |
16920 KB |
Output is correct |
4 |
Correct |
1292 ms |
22212 KB |
Output is correct |
5 |
Correct |
1350 ms |
24452 KB |
Output is correct |
6 |
Correct |
1813 ms |
26376 KB |
Output is correct |
7 |
Correct |
2562 ms |
27468 KB |
Output is correct |
8 |
Correct |
2724 ms |
27448 KB |
Output is correct |
9 |
Correct |
2388 ms |
27412 KB |
Output is correct |
10 |
Correct |
2149 ms |
27396 KB |
Output is correct |
11 |
Correct |
2283 ms |
27372 KB |
Output is correct |
12 |
Correct |
2243 ms |
27400 KB |
Output is correct |
13 |
Correct |
2233 ms |
27428 KB |
Output is correct |
14 |
Correct |
158 ms |
20432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
16784 KB |
Output is correct |
2 |
Correct |
19 ms |
16864 KB |
Output is correct |
3 |
Correct |
23 ms |
16796 KB |
Output is correct |
4 |
Correct |
18 ms |
16800 KB |
Output is correct |
5 |
Correct |
19 ms |
16864 KB |
Output is correct |
6 |
Correct |
20 ms |
16796 KB |
Output is correct |
7 |
Correct |
23 ms |
16812 KB |
Output is correct |
8 |
Correct |
30 ms |
16800 KB |
Output is correct |
9 |
Correct |
24 ms |
16852 KB |
Output is correct |
10 |
Correct |
20 ms |
16852 KB |
Output is correct |
11 |
Correct |
23 ms |
16824 KB |
Output is correct |
12 |
Correct |
21 ms |
16872 KB |
Output is correct |
13 |
Correct |
24 ms |
16844 KB |
Output is correct |
14 |
Correct |
21 ms |
16812 KB |
Output is correct |
15 |
Correct |
20 ms |
16820 KB |
Output is correct |
16 |
Correct |
19 ms |
16844 KB |
Output is correct |
17 |
Correct |
21 ms |
16820 KB |
Output is correct |
18 |
Correct |
21 ms |
16816 KB |
Output is correct |
19 |
Correct |
20 ms |
16820 KB |
Output is correct |
20 |
Correct |
19 ms |
16852 KB |
Output is correct |
21 |
Correct |
19 ms |
16852 KB |
Output is correct |
22 |
Correct |
18 ms |
16844 KB |
Output is correct |
23 |
Correct |
19 ms |
16852 KB |
Output is correct |
24 |
Correct |
21 ms |
16808 KB |
Output is correct |
25 |
Correct |
19 ms |
16824 KB |
Output is correct |
26 |
Correct |
24 ms |
17016 KB |
Output is correct |
27 |
Correct |
18 ms |
16800 KB |
Output is correct |
28 |
Correct |
18 ms |
16808 KB |
Output is correct |
29 |
Correct |
18 ms |
16816 KB |
Output is correct |
30 |
Correct |
28 ms |
16992 KB |
Output is correct |
31 |
Correct |
28 ms |
16920 KB |
Output is correct |
32 |
Correct |
31 ms |
17012 KB |
Output is correct |
33 |
Correct |
30 ms |
17016 KB |
Output is correct |
34 |
Correct |
35 ms |
17004 KB |
Output is correct |
35 |
Correct |
28 ms |
17012 KB |
Output is correct |
36 |
Correct |
28 ms |
17000 KB |
Output is correct |
37 |
Correct |
21 ms |
16980 KB |
Output is correct |
38 |
Correct |
29 ms |
17096 KB |
Output is correct |
39 |
Correct |
29 ms |
17096 KB |
Output is correct |
40 |
Correct |
32 ms |
17112 KB |
Output is correct |
41 |
Correct |
21 ms |
17120 KB |
Output is correct |
42 |
Correct |
20 ms |
17108 KB |
Output is correct |
43 |
Correct |
23 ms |
17072 KB |
Output is correct |
44 |
Correct |
32 ms |
17088 KB |
Output is correct |
45 |
Correct |
31 ms |
17036 KB |
Output is correct |
46 |
Correct |
32 ms |
17068 KB |
Output is correct |
47 |
Correct |
20 ms |
17044 KB |
Output is correct |
48 |
Correct |
24 ms |
17036 KB |
Output is correct |
49 |
Correct |
19 ms |
17048 KB |
Output is correct |
50 |
Correct |
28 ms |
17040 KB |
Output is correct |
51 |
Correct |
34 ms |
17012 KB |
Output is correct |
52 |
Correct |
28 ms |
16968 KB |
Output is correct |
53 |
Correct |
28 ms |
17028 KB |
Output is correct |
54 |
Correct |
28 ms |
17024 KB |
Output is correct |
55 |
Correct |
29 ms |
17020 KB |
Output is correct |
56 |
Correct |
23 ms |
16928 KB |
Output is correct |
57 |
Correct |
19 ms |
17020 KB |
Output is correct |
58 |
Correct |
21 ms |
16956 KB |
Output is correct |
59 |
Correct |
19 ms |
16792 KB |
Output is correct |
60 |
Correct |
20 ms |
16792 KB |
Output is correct |
61 |
Correct |
26 ms |
16848 KB |
Output is correct |
62 |
Correct |
1036 ms |
24984 KB |
Output is correct |
63 |
Correct |
978 ms |
29500 KB |
Output is correct |
64 |
Correct |
1166 ms |
30676 KB |
Output is correct |
65 |
Correct |
1783 ms |
33328 KB |
Output is correct |
66 |
Correct |
1643 ms |
33284 KB |
Output is correct |
67 |
Correct |
1623 ms |
33276 KB |
Output is correct |
68 |
Correct |
1667 ms |
33400 KB |
Output is correct |
69 |
Correct |
1687 ms |
33280 KB |
Output is correct |
70 |
Correct |
183 ms |
33084 KB |
Output is correct |
71 |
Correct |
199 ms |
33060 KB |
Output is correct |
72 |
Correct |
194 ms |
33040 KB |
Output is correct |
73 |
Correct |
68 ms |
30868 KB |
Output is correct |
74 |
Correct |
85 ms |
32844 KB |
Output is correct |
75 |
Correct |
147 ms |
20420 KB |
Output is correct |
76 |
Correct |
18 ms |
16852 KB |
Output is correct |
77 |
Correct |
42 ms |
19968 KB |
Output is correct |
78 |
Correct |
53 ms |
20292 KB |
Output is correct |
79 |
Correct |
54 ms |
20672 KB |
Output is correct |
80 |
Correct |
59 ms |
22440 KB |
Output is correct |
81 |
Correct |
60 ms |
22376 KB |
Output is correct |
82 |
Correct |
74 ms |
22460 KB |
Output is correct |
83 |
Correct |
76 ms |
22340 KB |
Output is correct |
84 |
Correct |
69 ms |
22444 KB |
Output is correct |
85 |
Correct |
73 ms |
22348 KB |
Output is correct |
86 |
Correct |
80 ms |
22460 KB |
Output is correct |
87 |
Correct |
68 ms |
22456 KB |
Output is correct |
88 |
Correct |
84 ms |
22760 KB |
Output is correct |
89 |
Correct |
74 ms |
23112 KB |
Output is correct |
90 |
Correct |
84 ms |
24260 KB |
Output is correct |
91 |
Correct |
68 ms |
22644 KB |
Output is correct |
92 |
Correct |
80 ms |
22596 KB |
Output is correct |
93 |
Correct |
81 ms |
22656 KB |
Output is correct |
94 |
Correct |
65 ms |
22464 KB |
Output is correct |
95 |
Correct |
67 ms |
22404 KB |
Output is correct |
96 |
Correct |
62 ms |
22340 KB |
Output is correct |
97 |
Correct |
64 ms |
22344 KB |
Output is correct |
98 |
Correct |
65 ms |
22376 KB |
Output is correct |
99 |
Correct |
68 ms |
22336 KB |
Output is correct |
100 |
Correct |
67 ms |
22316 KB |
Output is correct |
101 |
Correct |
68 ms |
22364 KB |
Output is correct |
102 |
Correct |
68 ms |
22464 KB |
Output is correct |
103 |
Correct |
73 ms |
22432 KB |
Output is correct |
104 |
Correct |
80 ms |
22476 KB |
Output is correct |
105 |
Correct |
75 ms |
22576 KB |
Output is correct |
106 |
Correct |
77 ms |
22632 KB |
Output is correct |
107 |
Correct |
73 ms |
22900 KB |
Output is correct |
108 |
Correct |
72 ms |
23420 KB |
Output is correct |
109 |
Correct |
82 ms |
24300 KB |
Output is correct |
110 |
Correct |
17 ms |
16852 KB |
Output is correct |
111 |
Correct |
18 ms |
16844 KB |
Output is correct |
112 |
Correct |
20 ms |
16920 KB |
Output is correct |
113 |
Correct |
1292 ms |
22212 KB |
Output is correct |
114 |
Correct |
1350 ms |
24452 KB |
Output is correct |
115 |
Correct |
1813 ms |
26376 KB |
Output is correct |
116 |
Correct |
2562 ms |
27468 KB |
Output is correct |
117 |
Correct |
2724 ms |
27448 KB |
Output is correct |
118 |
Correct |
2388 ms |
27412 KB |
Output is correct |
119 |
Correct |
2149 ms |
27396 KB |
Output is correct |
120 |
Correct |
2283 ms |
27372 KB |
Output is correct |
121 |
Correct |
2243 ms |
27400 KB |
Output is correct |
122 |
Correct |
2233 ms |
27428 KB |
Output is correct |
123 |
Correct |
158 ms |
20432 KB |
Output is correct |
124 |
Correct |
2113 ms |
27328 KB |
Output is correct |
125 |
Correct |
1317 ms |
25576 KB |
Output is correct |
126 |
Correct |
2299 ms |
27524 KB |
Output is correct |
127 |
Correct |
2258 ms |
27520 KB |
Output is correct |
128 |
Correct |
2349 ms |
27524 KB |
Output is correct |
129 |
Correct |
2201 ms |
27524 KB |
Output is correct |
130 |
Correct |
2264 ms |
27516 KB |
Output is correct |
131 |
Correct |
1816 ms |
32340 KB |
Output is correct |
132 |
Correct |
1679 ms |
33200 KB |
Output is correct |
133 |
Correct |
1920 ms |
30160 KB |
Output is correct |
134 |
Correct |
2586 ms |
27584 KB |
Output is correct |
135 |
Correct |
2702 ms |
27532 KB |
Output is correct |
136 |
Correct |
2045 ms |
27520 KB |
Output is correct |
137 |
Correct |
2254 ms |
27812 KB |
Output is correct |
138 |
Correct |
2106 ms |
27812 KB |
Output is correct |
139 |
Correct |
2328 ms |
27828 KB |
Output is correct |
140 |
Correct |
2066 ms |
27816 KB |
Output is correct |
141 |
Correct |
2182 ms |
27844 KB |
Output is correct |
142 |
Correct |
2229 ms |
27812 KB |
Output is correct |
143 |
Correct |
65 ms |
24744 KB |
Output is correct |
144 |
Correct |
95 ms |
27172 KB |
Output is correct |