Submission #2600704
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.Comparator;
import java.util.InputMismatchException;
import java.util.Random;
public class Main {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static long D;
static void solve()
{
long Y = ni();
long W = ni();
int n = ni(), m = ni();
D = nl() + 1;
long[] a = new long[n];
for(int i = 0;i < n;i++)a[i] = nl()-1;
int[][] bc = new int[m][];
for(int i = 0;i < m;i++){
bc[i] = new int[]{ni()-1, ni()-1};
}
Arrays.sort(bc, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[1] - b[1];
}
});
Node root = null;
long ans = 0;
Node[] bcs = new Node[m];
for(int i = 0;i < m;i++){
int[] x = bc[i];
Node y = new Node(x[0]*W+x[1]);
bcs[i] = y;
root = insertb(root, y);
ans += delta(y);
}
Node[] as = new Node[n];
for(int i = 0;i < n;i++){
as[i] = new Node(a[i]);
root = insertb(root, as[i]);
ans += delta(as[i]);
}
out.println(ans);
int p = 0;
for(int i = 0;i < W-1;i++){
while(p < m && bc[p][1] == i){
int ind = index(bcs[p]);
Node tar = get(root, ind);
assert tar != null;
ans -= delta(tar);
root = erase(root, ind);
tar.v += W;
root = insertb(root, tar);
ans += delta(tar);
p++;
}
for(int j = 0;j < n;j++){
int ind = index(as[j]);
ans -= delta(as[j]);
root = erase(root, ind);
as[j].v++;
root = insertb(root, as[j]);
ans += delta(as[j]);
}
out.println(ans);
}
}
static long delta(Node y)
{
Node p = prev(y);
Node n = next(y);
if(p != null && n != null && n.v - p.v <= D){
return 0;
}
long ret = 1;
if(p != null && y.v - p.v <= D){
ret += y.v - p.v - 1;
}
if(n != null && n.v - y.v <= D){
ret += n.v - y.v - 1;
}
return ret;
}
public static Random gen = new Random();
static public class Node
{
public long v; // value
public long priority;
public Node left, right, parent;
public int count;
public Node(long 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, long 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, long 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 build(int[] a, int l, int r)
{
if(l >= r)return null;
int h = l+r>>1;
Node root = new Node(a[h]);
Node L = build(a, l, h);
root.left = L;
if(L != null)L.parent = root;
Node R = build(a, h+1, r);
root.right = R;
if(R != null)R.parent = root;
return update(root);
}
public static Node[] nodes(Node a) { return nodes(a, new Node[count(a)], 0, count(a)); }
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 String toString(Node a, String indent)
{
if(a == null)return "";
StringBuilder sb = new StringBuilder();
sb.append(toString(a.left, indent + " "));
sb.append(indent).append(a).append("\n");
sb.append(toString(a.right, indent + " "));
return sb.toString();
}
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 - 祝日 |
User |
uwi |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
700 |
Code Size |
12770 Byte |
Status |
AC |
Exec Time |
4574 ms |
Memory |
71488 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
600 / 600 |
100 / 100 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt |
Subtask1 |
01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, sample-01.txt, sample-02.txt |
All |
01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 02-20.txt, 02-21.txt, 02-22.txt, 02-23.txt, 02-24.txt, 02-25.txt, 02-26.txt, 02-27.txt, 02-28.txt, 02-29.txt, 02-30.txt, 02-31.txt, 02-32.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
657 ms |
51588 KB |
01-02.txt |
AC |
583 ms |
51220 KB |
01-03.txt |
AC |
439 ms |
36468 KB |
01-04.txt |
AC |
255 ms |
29356 KB |
01-05.txt |
AC |
522 ms |
36296 KB |
01-06.txt |
AC |
519 ms |
40084 KB |
01-07.txt |
AC |
377 ms |
34348 KB |
01-08.txt |
AC |
204 ms |
24688 KB |
01-09.txt |
AC |
565 ms |
40608 KB |
01-10.txt |
AC |
198 ms |
26784 KB |
01-11.txt |
AC |
531 ms |
51236 KB |
01-12.txt |
AC |
485 ms |
46016 KB |
01-13.txt |
AC |
555 ms |
50076 KB |
01-14.txt |
AC |
301 ms |
30616 KB |
01-15.txt |
AC |
521 ms |
35956 KB |
01-16.txt |
AC |
120 ms |
23464 KB |
01-17.txt |
AC |
279 ms |
25868 KB |
01-18.txt |
AC |
468 ms |
35580 KB |
01-19.txt |
AC |
620 ms |
49080 KB |
01-20.txt |
AC |
606 ms |
52980 KB |
02-01.txt |
AC |
2304 ms |
69604 KB |
02-02.txt |
AC |
1048 ms |
51168 KB |
02-03.txt |
AC |
1370 ms |
59412 KB |
02-04.txt |
AC |
1534 ms |
63196 KB |
02-05.txt |
AC |
2363 ms |
69404 KB |
02-06.txt |
AC |
1455 ms |
53064 KB |
02-07.txt |
AC |
350 ms |
34172 KB |
02-08.txt |
AC |
606 ms |
33544 KB |
02-09.txt |
AC |
1736 ms |
65872 KB |
02-10.txt |
AC |
440 ms |
30044 KB |
02-11.txt |
AC |
1669 ms |
71488 KB |
02-12.txt |
AC |
1073 ms |
49724 KB |
02-13.txt |
AC |
1060 ms |
53996 KB |
02-14.txt |
AC |
360 ms |
32208 KB |
02-15.txt |
AC |
898 ms |
46788 KB |
02-16.txt |
AC |
223 ms |
27200 KB |
02-17.txt |
AC |
362 ms |
26596 KB |
02-18.txt |
AC |
583 ms |
36876 KB |
02-19.txt |
AC |
2479 ms |
66276 KB |
02-20.txt |
AC |
211 ms |
34496 KB |
02-21.txt |
AC |
709 ms |
42276 KB |
02-22.txt |
AC |
90 ms |
18516 KB |
02-23.txt |
AC |
4574 ms |
61988 KB |
02-24.txt |
AC |
2460 ms |
58776 KB |
02-25.txt |
AC |
1560 ms |
50516 KB |
02-26.txt |
AC |
87 ms |
19284 KB |
02-27.txt |
AC |
336 ms |
31708 KB |
02-28.txt |
AC |
699 ms |
43480 KB |
02-29.txt |
AC |
470 ms |
34296 KB |
02-30.txt |
AC |
470 ms |
34984 KB |
02-31.txt |
AC |
467 ms |
36436 KB |
02-32.txt |
AC |
529 ms |
39244 KB |
sample-01.txt |
AC |
70 ms |
19412 KB |
sample-02.txt |
AC |
70 ms |
19412 KB |
sample-03.txt |
AC |
73 ms |
16980 KB |
sample-04.txt |
AC |
70 ms |
19412 KB |