Submission #506092

#	Time	Username	Problem	Language	Result	Execution time	Memory
506092		mmaxio	Street Lamps (APIO19_street_lamps)	Java	100 / 100	2646 ms	288656 KiB

street_lamps

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 (stderr)

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

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20