Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit7ed6245

Browse files
authored
Improved tasks 3161, 3327
1 parent89649d4 commit7ed6245

File tree

2 files changed

+148
-139
lines changed
  • src/main/java

2 files changed

+148
-139
lines changed
Lines changed: 84 additions & 79 deletions
Original file line numberDiff line numberDiff line change
@@ -1,107 +1,112 @@
11
packageg3101_3200.s3161_block_placement_queries;
22

33
// #Hard #Array #Binary_Search #Segment_Tree #Binary_Indexed_Tree
4-
// #2024_05_30_Time_137_ms_(99.38%)_Space_143.7_MB_(54.52%)
4+
// #2025_03_16_Time_47_ms_(100.00%)_Space_144.38_MB_(56.41%)
55

6-
importjava.util.ArrayList;
6+
importjava.util.Arrays;
77
importjava.util.List;
88

99
publicclassSolution {
10-
privatestaticclassSeg {
11-
privatefinalintstart;
12-
privatefinalintend;
13-
privateintmin;
14-
privateintmax;
15-
privateintlen;
16-
privatebooleanobstacle;
17-
privateSegleft;
18-
privateSegright;
19-
20-
publicstaticSeginit(intn) {
21-
returnnewSeg(0,n);
22-
}
23-
24-
privateSeg(intstart,intend) {
25-
this.start =start;
26-
this.end =end;
27-
if (start >=end) {
28-
return;
10+
publicList<Boolean>getResults(int[][]queries) {
11+
intm =queries.length;
12+
int[]pos =newint[m +1];
13+
intsize =0;
14+
pos[size++] =0;
15+
intmax =0;
16+
for (int[]q :queries) {
17+
max =Math.max(max,q[1]);
18+
if (q[0] ==1) {
19+
pos[size++] =q[1];
2920
}
30-
intmid =start + ((end -start) >>1);
31-
left =newSeg(start,mid);
32-
right =newSeg(mid +1,end);
33-
refresh();
3421
}
22+
Arrays.sort(pos,0,size);
23+
max++;
24+
UnionFindleft =newUnionFind(max +1);
25+
UnionFindright =newUnionFind(max +1);
26+
BITbit =newBIT(max);
27+
initializePositions(size,pos,bit,left,right,max);
28+
returnList.of(getBooleans(queries,m,size,left,right,bit));
29+
}
3530

36-
publicvoidset(inti) {
37-
if (i <start ||i >end) {
38-
return;
39-
}elseif (i ==start &&i ==end) {
40-
obstacle =true;
41-
min =max =start;
42-
return;
31+
privatevoidinitializePositions(
32+
intsize,int[]pos,BITbit,UnionFindleft,UnionFindright,intmax) {
33+
for (inti =1;i <size;i++) {
34+
intpre =pos[i -1];
35+
intcur =pos[i];
36+
bit.update(cur,cur -pre);
37+
for (intj =pre +1;j <cur;j++) {
38+
left.parent[j] =pre;
39+
right.parent[j] =cur;
4340
}
44-
left.set(i);
45-
right.set(i);
46-
refresh();
4741
}
42+
for (intj =pos[size -1] +1;j <max;j++) {
43+
left.parent[j] =pos[size -1];
44+
right.parent[j] =max;
45+
}
46+
}
4847

49-
privatevoidrefresh() {
50-
if (left.obstacle) {
51-
min =left.min;
52-
if (right.obstacle) {
53-
max =right.max;
54-
len =Math.max(right.min -left.max,Math.max(left.len,right.len));
55-
}else {
56-
max =left.max;
57-
len =Math.max(left.len,right.end -left.max);
58-
}
59-
obstacle =true;
60-
}elseif (right.obstacle) {
61-
min =right.min;
62-
max =right.max;
63-
len =Math.max(right.len,right.min -left.start);
64-
obstacle =true;
48+
privateBoolean[]getBooleans(
49+
int[][]queries,intm,intsize,UnionFindleft,UnionFindright,BITbit) {
50+
Boolean[]ans =newBoolean[m -size +1];
51+
intindex =ans.length -1;
52+
for (inti =m -1;i >=0;i--) {
53+
int[]q =queries[i];
54+
intx =q[1];
55+
intpre =left.find(x -1);
56+
if (q[0] ==1) {
57+
intnext =right.find(x +1);
58+
left.parent[x] =pre;
59+
right.parent[x] =next;
60+
bit.update(next,next -pre);
6561
}else {
66-
len =end -start;
62+
intmaxGap =Math.max(bit.query(pre),x -pre);
63+
ans[index--] =maxGap >=q[2];
6764
}
6865
}
66+
returnans;
67+
}
68+
69+
privatestaticfinalclassBIT {
70+
intn;
71+
int[]tree;
6972

70-
publicvoidmax(intn,int[]t) {
71-
if (end <=n) {
72-
t[0] =Math.max(t[0],len);
73-
if (obstacle) {
74-
t[1] =max;
75-
}
76-
return;
73+
publicBIT(intn) {
74+
this.n =n;
75+
tree =newint[n];
76+
}
77+
78+
publicvoidupdate(inti,intv) {
79+
while (i <n) {
80+
tree[i] =Math.max(tree[i],v);
81+
i +=i & -i;
7782
}
78-
left.max(n,t);
79-
if (!right.obstacle ||right.min >=n) {
80-
return;
83+
}
84+
85+
publicintquery(inti) {
86+
intresult =0;
87+
while (i >0) {
88+
result =Math.max(result,tree[i]);
89+
i &=i -1;
8190
}
82-
t[0] =Math.max(t[0],right.min -t[1]);
83-
right.max(n,t);
91+
returnresult;
8492
}
8593
}
8694

87-
publicList<Boolean>getResults(int[][]queries) {
88-
intmax =0;
89-
for (int[]i :queries) {
90-
max =Math.max(max,i[1]);
95+
privatestaticfinalclassUnionFind {
96+
privatefinalint[]parent;
97+
98+
publicUnionFind(intn) {
99+
parent =newint[n];
100+
for (inti =1;i <n;i++) {
101+
parent[i] =i;
102+
}
91103
}
92-
Segroot =Seg.init(max);
93-
root.set(0);
94104

95-
List<Boolean>res =newArrayList<>(queries.length);
96-
for (int[]i :queries) {
97-
if (i[0] ==1) {
98-
root.set(i[1]);
99-
}else {
100-
int[]t =newint[2];
101-
root.max(i[1],t);
102-
res.add(Math.max(t[0],i[1] -t[1]) >=i[2]);
105+
publicintfind(intx) {
106+
if (parent[x] !=x) {
107+
parent[x] =find(parent[x]);
103108
}
109+
returnparent[x];
104110
}
105-
returnres;
106111
}
107112
}
Lines changed: 64 additions & 60 deletions
Original file line numberDiff line numberDiff line change
@@ -1,76 +1,80 @@
11
packageg3301_3400.s3327_check_if_dfs_strings_are_palindromes;
22

33
// #Hard #Array #String #Hash_Table #Depth_First_Search #Tree #Hash_Function
4-
// #2024_10_22_Time_159_ms_(90.40%)_Space_93.9_MB_(80.80%)
5-
6-
importjava.util.ArrayList;
7-
importjava.util.List;
4+
// #2025_03_16_Time_70_ms_(100.00%)_Space_75.50_MB_(96.67%)
85

96
publicclassSolution {
10-
privatefinalList<List<Integer>>e =newArrayList<>();
11-
privatefinalStringBuilderstringBuilder =newStringBuilder();
12-
privateStrings;
13-
privateintnow;
14-
privateintn;
15-
privateint[]l;
16-
privateint[]r;
17-
privateint[]p;
18-
privatechar[]c;
7+
privateinttime =0;
8+
privatebyte[]cs;
9+
privateint[][]graph;
1910

20-
privatevoiddfs(intx) {
21-
l[x] =now +1;
22-
for (intv :e.get(x)) {
23-
dfs(v);
11+
publicboolean[]findAnswer(int[]parent,Strings) {
12+
intn =s.length();
13+
cs =s.getBytes();
14+
graph =newint[n][];
15+
finalint[]childCount =newint[n];
16+
for (inti =1;i <n;i++) {
17+
childCount[parent[i]]++;
2418
}
25-
stringBuilder.append(s.charAt(x));
26-
r[x] = ++now;
27-
}
28-
29-
privatevoidmatcher() {
30-
c[0] ='~';
31-
c[1] ='#';
32-
for (inti =1;i <=n; ++i) {
33-
c[2 *i +1] ='#';
34-
c[2 *i] =stringBuilder.charAt(i -1);
19+
for (inti =0;i <n;i++) {
20+
graph[i] =newint[childCount[i]];
21+
childCount[i] =0;
3522
}
36-
intj =1;
37-
intmid =0;
38-
intlocalR =0;
39-
while (j <=2 *n +1) {
40-
if (j <=localR) {
41-
p[j] =Math.min(p[(mid <<1) -j],localR -j +1);
42-
}
43-
while (c[j -p[j]] ==c[j +p[j]]) {
44-
++p[j];
45-
}
46-
if (p[j] +j >localR) {
47-
localR =p[j] +j -1;
48-
mid =j;
49-
}
50-
++j;
23+
for (inti =1;i <n;i++) {
24+
graph[parent[i]][childCount[parent[i]]++] =i;
25+
}
26+
byte[]dfsStr =newbyte[n];
27+
int[]start =newint[n];
28+
int[]end =newint[n];
29+
dfs(0,dfsStr,start,end);
30+
int[]lens =getRadius(dfsStr);
31+
boolean[]ans =newboolean[n];
32+
for (inti =0;i <n;i++) {
33+
intl =start[i];
34+
intr =end[i];
35+
intcenter =l +r +2;
36+
ans[i] =lens[center] >=r -l +1;
5137
}
38+
returnans;
5239
}
5340

54-
publicboolean[]findAnswer(int[]parent,Strings) {
55-
n =parent.length;
56-
this.s =s;
57-
for (inti =0;i <n; ++i) {
58-
e.add(newArrayList<>());
41+
privatevoiddfs(intu,byte[]dfsStr,int[]start,int[]end) {
42+
start[u] =time;
43+
for (intv :graph[u]) {
44+
dfs(v,dfsStr,start,end);
5945
}
60-
for (inti =1;i <n; ++i) {
61-
e.get(parent[i]).add(i);
46+
dfsStr[time] =cs[u];
47+
end[u] =time++;
48+
}
49+
50+
privateint[]getRadius(byte[]cs) {
51+
intn =cs.length;
52+
byte[]t =newbyte[2 *n +3];
53+
intm =0;
54+
t[m++] ='@';
55+
t[m++] ='#';
56+
for (bytec :cs) {
57+
t[m++] =c;
58+
t[m++] ='#';
6259
}
63-
l =newint[n];
64-
r =newint[n];
65-
dfs(0);
66-
c =newchar[2 *n +10];
67-
p =newint[2 *n +10];
68-
matcher();
69-
boolean[]ans =newboolean[n];
70-
for (inti =0;i <n; ++i) {
71-
intmid = (2 *r[i] -2 *l[i] +1) /2 +2 *l[i];
72-
ans[i] =p[mid] -1 >=r[i] -l[i] +1;
60+
t[m++] ='$';
61+
int[]lens =newint[m];
62+
intcenter =0;
63+
intright =0;
64+
for (inti =2;i <m -2;i++) {
65+
intlen =0;
66+
if (i <right) {
67+
len =Math.min(lens[2 *center -i],right -i);
68+
}
69+
while (t[i +len +1] ==t[i -len -1]) {
70+
len++;
71+
}
72+
if (right <i +len) {
73+
right =i +len;
74+
center =i;
75+
}
76+
lens[i] =len;
7377
}
74-
returnans;
78+
returnlens;
7579
}
7680
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp