Submission #538035

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
538035	2022-03-16 03:36:35	fhvirus	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	320 ms	47336 KiB

long_mansion

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
// rama_pang orz
// solution and codestyle adapted from his/her submission
#include<bits/stdc++.h>
using namespace std;
struct DisjointSet {
  int n;
  vector<int> f;
  DisjointSet () = default;
  DisjointSet (const int& _n): n(_n), f(n) { iota(begin(f), end(f), 0); }
  int F(int u) { return u == f[u] ? u : f[u] = F(f[u]); }
  bool M(int u, int v) {
    u = F(u); v = F(v);
    if (u != v) f[v] = u;
    return u != v;
  }
};
const int kN = 500005;
int N, Q, C[kN];
vector<int> key_pos[kN];
bool can_unlock(int l, int r, int c) {
  return *lower_bound(begin(key_pos[c]), end(key_pos[c]), l) <= r;
}
pair<int, int> memo[kN];
bool in_stack[kN];
DisjointSet dsu(kN);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75