oj.uz

Submission #506092

# Submission time Handle Problem Language Result Execution time Memory
506092 2022-01-11T15:09:13 Z mmaxio Street Lamps (APIO19_street_lamps) Java 11
100 / 100
 2646 ms 288656 KB 
import java.io.*;
import java.math.*;
import java.util.*;
import java.util.stream.*;

public class street_lamps {

	int n;
	ArrayList<Integer>[] fensPtsALs;
	int[][] fensPts;
	int[][] fens;
	
	int[] qLog = new int[300_000 * 3 * 19];
	int qPtr = 0;
	
	int[] outp;
	
	void modify(int l, int r, int val) {
		r = n - 1 - r;
		qLog[qPtr++] = l;
		qLog[qPtr++] = r;
		qLog[qPtr++] = val;
	}
	
	void query(int l, int r, int qIdx) {
		// sum over points with L <= l, R >= r
		r = n - 1 - r;
		for (int i = l; i >= 0; i = (i & (i + 1)) - 1) {
			fensPtsALs[i].add(r);
		}
		qLog[qPtr++] = ~l;
		qLog[qPtr++] = r;
		qLog[qPtr++] = qIdx;
	}
	
	void prepareQs() {
		for (int i = 0; i < n; i++) {
			ArrayList<Integer> lst = fensPtsALs[i];
			Collections.sort(lst);
			int sz = 0;
			for (int j = 0; j < lst.size(); j++) {
				if (j == 0 || !lst.get(j).equals(lst.get(j - 1))) {
					sz++;
				}
			}
			int[] arr = fensPts[i] = new int[sz];
			for (int j = 0, k = 0; j < lst.size(); j++) {
				if (j == 0 || !lst.get(j).equals(lst.get(j - 1))) {
					arr[k++] = lst.get(j);
				}
			}
			fens[i] = new int[sz];
		}
	}
	
	void executeQs() {
		for (int z = 0; z < qPtr; z += 3) {
			int l = qLog[z];
			int r = qLog[z + 1];
			int val = qLog[z + 2];
			if (l >= 0) {
				for (int i = l; i < n; i |= i + 1) {
					int[] f = fens[i];
					int compR = Arrays.binarySearch(fensPts[i], r);
					if (compR < 0) {
						compR = -compR - 1;
					}
					for (int j = compR; j < f.length; j |= j + 1) {
						f[j] += val;
					}
				}
			} else {
				l = ~l;
				int result = outp[val];
				for (int i = l; i >= 0; i = (i & (i + 1)) - 1) {
					int[] f = fens[i];
					int compR = Arrays.binarySearch(fensPts[i], r);
					if (compR < 0) {
						throw new AssertionError();
					}
					for (int j = compR; j >= 0; j = (j & (j + 1)) - 1) {
						result += f[j];
					}
				}
				out.println(result);
			}
		}
	}

	void submit() {
		n = nextInt();
		
		fensPtsALs = new ArrayList[n];
		fensPts = new int[n][];
		fens = new int[n][];
		for (int i = 0; i < n; i++) {
			fensPtsALs[i] = new ArrayList<>();
		}
		
		int q = nextInt();
		outp = new int[q];
		String ss = nextToken();
		int[] s = new int[n];
		for (int i = 0; i < n; i++) {
			s[i] = ss.charAt(i) - '0';
		}
		int[] jump = new int[n];
		int[] from = new int[n];
		
		TreeSet<Integer> lefts = new TreeSet<>();
		
		for (int i = 0; i < n; i++) {
			if (s[i] == 1) {
				int j = i + 1;
				while (j < n && s[j] == 1) {
					j++;
				}
				jump[i] = j - 1;
				jump[j - 1] = i;
				lefts.add(i);
				from[i] = 0;
				i = j;
			}
		}

		for (int i = 1; i <= q; i++) {
			String cmd = nextToken();
			if (cmd.equals("toggle")) {
				int idx = nextInt() - 1;
				if (s[idx] == 0) {
					int newL;
					if (idx - 1 >= 0 && s[idx - 1] == 1) {
						int r = idx - 1;
						int l = jump[r];
						modify(l, r, i - from[l]);
						
						newL = l;
						if (!lefts.remove(l)) {
							throw new AssertionError();
						}
					} else {
						newL = idx;
					}
					
					int newR;
					if (idx + 1 < n && s[idx + 1] == 1) {
						int l = idx + 1;
						int r = jump[l];
						modify(l, r, i - from[l]);
						
						newR = r;
						if (!lefts.remove(l)) {
							throw new AssertionError();
						}
					} else {
						newR = idx;
					}
					
					if (!lefts.add(newL)) {
						throw new AssertionError();
					}
					jump[newL] = newR;
					jump[newR] = newL;
					from[newL] = i;
				} else {
					int l = lefts.floor(idx);
					int r = jump[l];
					modify(l, r, i - from[l]);
					
					if (!lefts.remove(l)) {
						throw new AssertionError();
					}
					
					if (idx != l) {
						int newL = l;
						int newR = idx - 1;
						if (!lefts.add(newL)) {
							throw new AssertionError();
						}
						jump[newL] = newR;
						jump[newR] = newL;
						from[newL] = i;
					}
					
					if (idx != r) {
						int newL = idx + 1;
						int newR = r;
						if (!lefts.add(newL)) {
							throw new AssertionError();
						}
						jump[newL] = newR;
						jump[newR] = newL;
						from[newL] = i;
					}
				}
				s[idx] ^= 1;
			} else if (cmd.equals("query")) {
				int l = nextInt() - 1;
				int r = nextInt() - 2;
				if (s[l] == 1) {
					int left = lefts.floor(l); // can't be null because we check if it's active
					int right = jump[left];
					if (right >= r) {
						outp[i - 1] += i - from[left];
					}
				}
				query(l, r, i - 1);
			}
		}
		prepareQs();
		executeQs();
	}

	void test() {

	}

	void stress() {
		for (int tst = 0;; tst++) {
			if (false) {
				throw new AssertionError();
			}
			System.err.println(tst);
		}
	}

	street_lamps() throws IOException {
		is = System.in;
		out = new PrintWriter(System.out);
		submit();
		// stress();
		// test();
		out.close();
	}

	static final Random rng = new Random();
	static final int C = 5;

	static int rand(int l, int r) {
		return l + rng.nextInt(r - l + 1);
	}

	public static void main(String[] args) throws IOException {
		new street_lamps();
	}

	private InputStream is;
	PrintWriter out;

	private byte[] buf = new byte[1 << 14];
	private int bufSz = 0, bufPtr = 0;

	private int readByte() {
		if (bufSz == -1)
			throw new RuntimeException("Reading past EOF");
		if (bufPtr >= bufSz) {
			bufPtr = 0;
			try {
				bufSz = is.read(buf);
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
			if (bufSz <= 0)
				return -1;
		}
		return buf[bufPtr++];
	}

	private boolean isTrash(int c) {
		return c < 33 || c > 126;
	}

	private int skip() {
		int b;
		while ((b = readByte()) != -1 && isTrash(b))
			;
		return b;
	}

	String nextToken() {
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!isTrash(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	String nextString() {
		int b = readByte();
		StringBuilder sb = new StringBuilder();
		while (!isTrash(b) || b == ' ') {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	double nextDouble() {
		return Double.parseDouble(nextToken());
	}

	char nextChar() {
		return (char) skip();
	}

	int nextInt() {
		int ret = 0;
		int b = skip();
		if (b != '-' && (b < '0' || b > '9')) {
			throw new InputMismatchException();
		}
		boolean neg = false;
		if (b == '-') {
			neg = true;
			b = readByte();
		}
		while (true) {
			if (b >= '0' && b <= '9') {
				ret = ret * 10 + (b - '0');
			} else {
				if (b != -1 && !isTrash(b)) {
					throw new InputMismatchException();
				}
				return neg ? -ret : ret;
			}
			b = readByte();
		}
	}

	long nextLong() {
		long ret = 0;
		int b = skip();
		if (b != '-' && (b < '0' || b > '9')) {
			throw new InputMismatchException();
		}
		boolean neg = false;
		if (b == '-') {
			neg = true;
			b = readByte();
		}
		while (true) {
			if (b >= '0' && b <= '9') {
				ret = ret * 10 + (b - '0');
			} else {
				if (b != -1 && !isTrash(b)) {
					throw new InputMismatchException();
				}
				return neg ? -ret : ret;
			}
			b = readByte();
		}
	}
}

Compilation message

Note: street_lamps.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 76664 KB Output is correct
2 Correct 102 ms 76308 KB Output is correct
3 Correct 114 ms 76332 KB Output is correct
4 Correct 98 ms 76284 KB Output is correct
5 Correct 94 ms 76428 KB Output is correct
6 Correct 95 ms 76496 KB Output is correct
7 Correct 111 ms 76436 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 112648 KB Output is correct
2 Correct 1174 ms 135048 KB Output is correct
3 Correct 1588 ms 162288 KB Output is correct
4 Correct 1946 ms 209156 KB Output is correct
5 Correct 2307 ms 206660 KB Output is correct
6 Correct 1904 ms 200920 KB Output is correct
7 Correct 2286 ms 227848 KB Output is correct
8 Correct 2360 ms 232208 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 76484 KB Output is correct
2 Correct 130 ms 76452 KB Output is correct
3 Correct 144 ms 76488 KB Output is correct
4 Correct 156 ms 77096 KB Output is correct
5 Correct 1120 ms 156500 KB Output is correct
6 Correct 2031 ms 198880 KB Output is correct
7 Correct 2297 ms 204632 KB Output is correct
8 Correct 2511 ms 288656 KB Output is correct
9 Correct 872 ms 117648 KB Output is correct
10 Correct 1022 ms 121160 KB Output is correct
11 Correct 940 ms 123608 KB Output is correct
12 Correct 2209 ms 229028 KB Output is correct
13 Correct 2646 ms 288596 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 76988 KB Output is correct
2 Correct 164 ms 76548 KB Output is correct
3 Correct 146 ms 76504 KB Output is correct
4 Correct 133 ms 78136 KB Output is correct
5 Correct 2495 ms 241888 KB Output is correct
6 Correct 2491 ms 243808 KB Output is correct
7 Correct 2082 ms 201868 KB Output is correct
8 Correct 1358 ms 163260 KB Output is correct
9 Correct 1125 ms 105600 KB Output is correct
10 Correct 723 ms 93324 KB Output is correct
11 Correct 1077 ms 105576 KB Output is correct
12 Correct 679 ms 93408 KB Output is correct
13 Correct 1132 ms 105456 KB Output is correct
14 Correct 820 ms 97300 KB Output is correct
15 Correct 2157 ms 228848 KB Output is correct
16 Correct 2508 ms 288372 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 76664 KB Output is correct
2 Correct 102 ms 76308 KB Output is correct
3 Correct 114 ms 76332 KB Output is correct
4 Correct 98 ms 76284 KB Output is correct
5 Correct 94 ms 76428 KB Output is correct
6 Correct 95 ms 76496 KB Output is correct
7 Correct 111 ms 76436 KB Output is correct
8 Correct 1022 ms 112648 KB Output is correct
9 Correct 1174 ms 135048 KB Output is correct
10 Correct 1588 ms 162288 KB Output is correct
11 Correct 1946 ms 209156 KB Output is correct
12 Correct 2307 ms 206660 KB Output is correct
13 Correct 1904 ms 200920 KB Output is correct
14 Correct 2286 ms 227848 KB Output is correct
15 Correct 2360 ms 232208 KB Output is correct
16 Correct 123 ms 76484 KB Output is correct
17 Correct 130 ms 76452 KB Output is correct
18 Correct 144 ms 76488 KB Output is correct
19 Correct 156 ms 77096 KB Output is correct
20 Correct 1120 ms 156500 KB Output is correct
21 Correct 2031 ms 198880 KB Output is correct
22 Correct 2297 ms 204632 KB Output is correct
23 Correct 2511 ms 288656 KB Output is correct
24 Correct 872 ms 117648 KB Output is correct
25 Correct 1022 ms 121160 KB Output is correct
26 Correct 940 ms 123608 KB Output is correct
27 Correct 2209 ms 229028 KB Output is correct
28 Correct 2646 ms 288596 KB Output is correct
29 Correct 160 ms 76988 KB Output is correct
30 Correct 164 ms 76548 KB Output is correct
31 Correct 146 ms 76504 KB Output is correct
32 Correct 133 ms 78136 KB Output is correct
33 Correct 2495 ms 241888 KB Output is correct
34 Correct 2491 ms 243808 KB Output is correct
35 Correct 2082 ms 201868 KB Output is correct
36 Correct 1358 ms 163260 KB Output is correct
37 Correct 1125 ms 105600 KB Output is correct
38 Correct 723 ms 93324 KB Output is correct
39 Correct 1077 ms 105576 KB Output is correct
40 Correct 679 ms 93408 KB Output is correct
41 Correct 1132 ms 105456 KB Output is correct
42 Correct 820 ms 97300 KB Output is correct
43 Correct 2157 ms 228848 KB Output is correct
44 Correct 2508 ms 288372 KB Output is correct
45 Correct 937 ms 98600 KB Output is correct
46 Correct 939 ms 94948 KB Output is correct
47 Correct 1721 ms 167836 KB Output is correct
48 Correct 2066 ms 208756 KB Output is correct
49 Correct 886 ms 128012 KB Output is correct
50 Correct 892 ms 127700 KB Output is correct
51 Correct 913 ms 130764 KB Output is correct
52 Correct 890 ms 154372 KB Output is correct
53 Correct 928 ms 153852 KB Output is correct
54 Correct 918 ms 155152 KB Output is correct