Submission #897551
Source Code Expand
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Random;
public class Main {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
int n = ni(), m = ni();
int Q = ni();
int[] a = na(Q);
Node root = null;
Node[] nodes = new Node[m+1];
for(int i = 1;i <= m;i++){
nodes[i] = new Node(i);
root = merge(root, nodes[i]);
}
int dec = 0;
for(int i = 0;i < Q;i++){
int K = index(nodes[a[i]]);
root = erase(root, K);
root = merge(nodes[a[i]], root);
}
for(int i = 1;i <= m;i++){
Node cur = nodes[i];
Node nex = next(cur);
if(nex != null && cur.v >= nex.v){
dec++;
}
}
if(dec == 0){
out.println("Yes");
return;
}
int[] fs = new int[n];
Arrays.fill(fs, Q);
int[][] buc = makeBuckets(a, m);
boolean[] used = new boolean[m+1];
out:
for(int i = Q-1;i >= 0;i--){
if(used[a[i]])continue;
used[a[i]] = true;
if(buc[a[i]].length < n)break;
int j = buc[a[i]].length-1;
for(int k = n-1;k >= 0;k--){
while(j >= 0 && buc[a[i]][j] >= fs[k]){
j--;
}
if(j == -1)break out;
fs[k] = buc[a[i]][j];
j--;
}
Node cur = nodes[a[i]];
Node nex = next(cur);
Node pre = prev(cur);
if(nex != null && cur.v >= nex.v){
dec--;
}
if(pre != null && pre.v >= cur.v){
dec--;
}
if(pre != null && nex != null && pre.v >= cur.v){
dec++;
}
root = erase(root, index(cur));
if(dec == 0){
out.println("Yes");
return;
}
}
out.println("No");
return;
}
public static int[][] makeBuckets(int[] a, int sup)
{
int n = a.length;
int[][] bucket = new int[sup+1][];
int[] bp = new int[sup+1];
for(int i = 0;i < n;i++)bp[a[i]]++;
for(int i = 0;i <= sup;i++)bucket[i] = new int[bp[i]];
for(int i = n-1;i >= 0;i--)bucket[a[i]][--bp[a[i]]] = i;
return bucket;
}
public static Random gen = new Random();
static public class Node
{
public int v; // value
public long priority;
public Node left, right, parent;
public int count;
public Node(int v)
{
this.v = v;
priority = gen.nextLong();
update(this);
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("Node [v=");
builder.append(v);
builder.append(", count=");
builder.append(count);
builder.append(", parent=");
builder.append(parent != null ? parent.v : "null");
builder.append("]");
return builder.toString();
}
}
public static Node update(Node a)
{
if(a == null)return null;
a.count = 1;
if(a.left != null)a.count += a.left.count;
if(a.right != null)a.count += a.right.count;
// TODO
return a;
}
public static void propagate(Node x)
{
for(;x != null;x = x.parent)update(x);
}
public static Node disconnect(Node a)
{
if(a == null)return null;
a.left = a.right = a.parent = null;
return update(a);
}
public static Node root(Node x)
{
if(x == null)return null;
while(x.parent != null)x = x.parent;
return x;
}
public static int count(Node a)
{
return a == null ? 0 : a.count;
}
public static void setParent(Node a, Node par)
{
if(a != null)a.parent = par;
}
public static Node merge(Node a, Node b, Node... c)
{
Node x = merge(a, b);
for(Node n : c)x = merge(x, n);
return x;
}
public static Node merge(Node a, Node b)
{
if(b == null)return a;
if(a == null)return b;
if(a.priority > b.priority){
setParent(a.right, null);
setParent(b, null);
a.right = merge(a.right, b);
setParent(a.right, a);
return update(a);
}else{
setParent(a, null);
setParent(b.left, null);
b.left = merge(a, b.left);
setParent(b.left, b);
return update(b);
}
}
public static Node[] split(Node x)
{
if(x == null)return new Node[]{null, null};
if(x.left != null)x.left.parent = null;
Node[] sp = new Node[]{x.left, x};
x.left = null;
update(x);
while(x.parent != null){
Node p = x.parent;
x.parent = null;
if(x == p.left){
p.left = sp[1];
if(sp[1] != null)sp[1].parent = p;
sp[1] = p;
}else{
p.right = sp[0];
if(sp[0] != null)sp[0].parent = p;
sp[0] = p;
}
update(p);
x = p;
}
return sp;
}
public static Node[] split(Node a, int... ks)
{
int n = ks.length;
if(n == 0)return new Node[]{a};
for(int i = 0;i < n-1;i++){
if(ks[i] > ks[i+1])throw new IllegalArgumentException(Arrays.toString(ks));
}
Node[] ns = new Node[n+1];
Node cur = a;
for(int i = n-1;i >= 0;i--){
Node[] sp = split(cur, ks[i]);
cur = sp[0];
ns[i] = sp[0];
ns[i+1] = sp[1];
}
return ns;
}
// [0,K),[K,N)
public static Node[] split(Node a, int K)
{
if(a == null)return new Node[]{null, null};
if(K <= count(a.left)){
setParent(a.left, null);
Node[] s = split(a.left, K);
a.left = s[1];
setParent(a.left, a);
s[1] = update(a);
return s;
}else{
setParent(a.right, null);
Node[] s = split(a.right, K-count(a.left)-1);
a.right = s[0];
setParent(a.right, a);
s[0] = update(a);
return s;
}
}
public static Node insertb(Node root, Node x)
{
int ind = lowerBound(root, x.v);
return insert(root, ind, x);
}
public static Node insert(Node a, int K, Node b)
{
if(a == null)return b;
if(b.priority < a.priority){
if(K <= count(a.left)){
a.left = insert(a.left, K, b);
setParent(a.left, a);
}else{
a.right = insert(a.right, K-count(a.left)-1, b);
setParent(a.right, a);
}
return update(a);
}else{
Node[] ch = split(a, K);
b.left = ch[0]; b.right = ch[1];
setParent(b.left, b);
setParent(b.right, b);
return update(b);
}
}
// delete K-th
public static Node erase(Node a, int K)
{
if(a == null)return null;
if(K < count(a.left)){
a.left = erase(a.left, K);
setParent(a.left, a);
return update(a);
}else if(K == count(a.left)){
setParent(a.left, null);
setParent(a.right, null);
Node aa = merge(a.left, a.right);
disconnect(a);
return aa;
}else{
a.right = erase(a.right, K-count(a.left)-1);
setParent(a.right, a);
return update(a);
}
}
public static Node get(Node a, int K)
{
while(a != null){
if(K < count(a.left)){
a = a.left;
}else if(K == count(a.left)){
break;
}else{
K = K - count(a.left)-1;
a = a.right;
}
}
return a;
}
public static int index(Node a)
{
if(a == null)return -1;
int ind = count(a.left);
while(a != null){
Node par = a.parent;
if(par != null && par.right == a){
ind += count(par.left) + 1;
}
a = par;
}
return ind;
}
public static Node mergeTechnically(Node x, Node y)
{
if(count(x) > count(y)){
Node d = x; x = y; y = d;
}
// |x|<=|y|
for(Node cur : nodesdfs(x))y = insertb(y, disconnect(cur));
return y;
}
public static int lowerBound(Node a, int q)
{
int lcount = 0;
while(a != null){
if(a.v >= q){
a = a.left;
}else{
lcount += count(a.left) + 1;
a = a.right;
}
}
return lcount;
}
public static int search(Node a, int q)
{
int lcount = 0;
while(a != null){
if(a.v == q){
lcount += count(a.left);
break;
}
if(q < a.v){
a = a.left;
}else{
lcount += count(a.left) + 1;
a = a.right;
}
}
return a == null ? -(lcount+1) : lcount;
}
public static Node next(Node x)
{
if(x == null)return null;
if(x.right != null){
x = x.right;
while(x.left != null)x = x.left;
return x;
}else{
while(true){
Node p = x.parent;
if(p == null)return null;
if(p.left == x)return p;
x = p;
}
}
}
public static Node prev(Node x)
{
if(x == null)return null;
if(x.left != null){
x = x.left;
while(x.right != null)x = x.right;
return x;
}else{
while(true){
Node p = x.parent;
if(p == null)return null;
if(p.right == x)return p;
x = p;
}
}
}
public static Node[] nodes(Node a) { return nodes(a, new Node[a.count], 0, a.count); }
public static Node[] nodes(Node a, Node[] ns, int L, int R)
{
if(a == null)return ns;
nodes(a.left, ns, L, L+count(a.left));
ns[L+count(a.left)] = a;
nodes(a.right, ns, R-count(a.right), R);
return ns;
}
// faster than nodes but inconsistent
public static Node[] nodesdfs(Node a) { return nodesdfs(a, new Node[a.count], new int[]{0}); }
public static Node[] nodesdfs(Node a, Node[] ns, int[] pos)
{
if(a == null)return ns;
ns[pos[0]++] = a;
nodesdfs(a.left, ns, pos);
nodesdfs(a.right, ns, pos);
return ns;
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
// private static boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Submission Info
Submission Time |
|
Task |
E - LRU Puzzle |
User |
uwi |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
1200 |
Code Size |
12182 Byte |
Status |
AC |
Exec Time |
287 ms |
Memory |
19312 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1200 / 1200 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt, 1_55.txt, 1_56.txt, 1_57.txt, 1_58.txt, 1_59.txt, 1_60.txt, 1_61.txt, 1_62.txt, 1_63.txt, 1_64.txt, 1_65.txt, 1_66.txt, 1_67.txt, 1_68.txt, 1_69.txt, 1_70.txt, 1_71.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
95 ms |
8272 KB |
0_01.txt |
AC |
95 ms |
8148 KB |
0_02.txt |
AC |
97 ms |
8144 KB |
0_03.txt |
AC |
102 ms |
8144 KB |
1_00.txt |
AC |
95 ms |
8276 KB |
1_01.txt |
AC |
97 ms |
8144 KB |
1_02.txt |
AC |
180 ms |
14776 KB |
1_03.txt |
AC |
208 ms |
18028 KB |
1_04.txt |
AC |
176 ms |
14768 KB |
1_05.txt |
AC |
206 ms |
17980 KB |
1_06.txt |
AC |
201 ms |
15024 KB |
1_07.txt |
AC |
232 ms |
19312 KB |
1_08.txt |
AC |
212 ms |
15800 KB |
1_09.txt |
AC |
213 ms |
15796 KB |
1_10.txt |
AC |
242 ms |
15316 KB |
1_11.txt |
AC |
245 ms |
16228 KB |
1_12.txt |
AC |
243 ms |
15520 KB |
1_13.txt |
AC |
224 ms |
15540 KB |
1_14.txt |
AC |
261 ms |
15320 KB |
1_15.txt |
AC |
244 ms |
15496 KB |
1_16.txt |
AC |
240 ms |
16180 KB |
1_17.txt |
AC |
226 ms |
15592 KB |
1_18.txt |
AC |
265 ms |
17980 KB |
1_19.txt |
AC |
282 ms |
16012 KB |
1_20.txt |
AC |
266 ms |
17720 KB |
1_21.txt |
AC |
264 ms |
18744 KB |
1_22.txt |
AC |
270 ms |
18744 KB |
1_23.txt |
AC |
280 ms |
17060 KB |
1_24.txt |
AC |
255 ms |
18724 KB |
1_25.txt |
AC |
287 ms |
16204 KB |
1_26.txt |
AC |
179 ms |
12004 KB |
1_27.txt |
AC |
187 ms |
11832 KB |
1_28.txt |
AC |
194 ms |
12068 KB |
1_29.txt |
AC |
199 ms |
12068 KB |
1_30.txt |
AC |
242 ms |
16972 KB |
1_31.txt |
AC |
219 ms |
16808 KB |
1_32.txt |
AC |
229 ms |
16368 KB |
1_33.txt |
AC |
239 ms |
16964 KB |
1_34.txt |
AC |
234 ms |
13888 KB |
1_35.txt |
AC |
231 ms |
15292 KB |
1_36.txt |
AC |
224 ms |
13496 KB |
1_37.txt |
AC |
244 ms |
15164 KB |
1_38.txt |
AC |
274 ms |
16936 KB |
1_39.txt |
AC |
279 ms |
17332 KB |
1_40.txt |
AC |
240 ms |
18492 KB |
1_41.txt |
AC |
278 ms |
18852 KB |
1_42.txt |
AC |
194 ms |
11704 KB |
1_43.txt |
AC |
192 ms |
12088 KB |
1_44.txt |
AC |
195 ms |
12088 KB |
1_45.txt |
AC |
192 ms |
11712 KB |
1_46.txt |
AC |
217 ms |
12988 KB |
1_47.txt |
AC |
221 ms |
14520 KB |
1_48.txt |
AC |
226 ms |
14276 KB |
1_49.txt |
AC |
246 ms |
17588 KB |
1_50.txt |
AC |
201 ms |
11968 KB |
1_51.txt |
AC |
197 ms |
11844 KB |
1_52.txt |
AC |
210 ms |
12472 KB |
1_53.txt |
AC |
202 ms |
11972 KB |
1_54.txt |
AC |
220 ms |
14904 KB |
1_55.txt |
AC |
222 ms |
14748 KB |
1_56.txt |
AC |
241 ms |
18364 KB |
1_57.txt |
AC |
239 ms |
17592 KB |
1_58.txt |
AC |
162 ms |
11616 KB |
1_59.txt |
AC |
175 ms |
11964 KB |
1_60.txt |
AC |
165 ms |
11704 KB |
1_61.txt |
AC |
170 ms |
11968 KB |
1_62.txt |
AC |
209 ms |
14392 KB |
1_63.txt |
AC |
202 ms |
17804 KB |
1_64.txt |
AC |
171 ms |
11916 KB |
1_65.txt |
AC |
222 ms |
17064 KB |
1_66.txt |
AC |
154 ms |
11876 KB |
1_67.txt |
AC |
175 ms |
12356 KB |
1_68.txt |
AC |
162 ms |
11708 KB |
1_69.txt |
AC |
173 ms |
12352 KB |
1_70.txt |
AC |
200 ms |
15536 KB |
1_71.txt |
AC |
209 ms |
17308 KB |