Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- public class Main {
- private static int[] t;
- private static int[] flags;
- // 0 - not modified
- // 1 - нужно обновить минимум
- private static int[] toSet;
- private static int INF = 2_000_000_000;
- private static void push(int v) {
- if (flags[v] == 1) {
- t[v] = toSet[v];
- flags[v] = 0;
- int left = v * 2 + 1;
- if (left + 1 < t.length) { // если v - не лист
- if ((flags[left] == 1 && toSet[left] < t[v]) || (flags[left] == 0 && t[left] < t[v])) {
- toSet[left] = t[v];
- flags[left] = 1;
- }
- left++; // стал правым
- if ((flags[left] == 1 && toSet[left] < t[v]) || (flags[left] == 0 && t[left] < t[v])) {
- toSet[left] = t[v];
- flags[left] = 1;
- }
- }
- }
- }
- private static void setMin(int i) {
- if (2 * i + 2 < t.length) {
- push(i * 2 + 1);
- push(i * 2 + 2);
- t[i] = Math.min(t[i * 2 + 1], t[i * 2 + 2]);
- }
- }
- private static int[] getMin(int v, int left, int right, int a, int b) {
- if (a > right || b < left) return new int[]{INF, 0};
- push(v);
- if (a == left && b == right) {
- return new int[]{t[v], v};
- }
- int mid = (left + right) / 2;
- int x[] = getMin(v * 2 + 1, left, mid, a, Math.min(b, mid));
- int y[] = getMin(v * 2 + 2, mid + 1, right, Math.max(a, mid + 1), b);
- if (x[0] < y[0]) return x;
- return y;
- }
- private static void actionInRange(int v, int left, int right, int a, int b, int value) {
- if (a > b) return;
- if (a == left && right == b) {
- if (t[v] >= value) return;
- if (flags[v] == 1 && toSet[v] >= value){
- push(v);
- return;
- }
- flags[v] = 1;
- toSet[v] = value;
- push(v);
- } else {
- push(v);
- int mid = (left + right) / 2;
- actionInRange(v * 2 + 1, left, mid, a, Math.min(b, mid), value);
- actionInRange(v * 2 + 2, mid + 1, right, Math.max(a, mid + 1), b, value);
- setMin(v);
- }
- }
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- int n = in.nextInt();
- in.nextInt();
- int newN = getTrueN(n);
- int length = newN * 2 - 1;
- t = new int[length];
- flags = new int[length];
- // build
- for (int i = 0; i < length; i++)
- t[i] = INF;
- for (int i = 0; i < n; i++)
- t[newN - 1 + i] = 0;
- for (int i = newN - 2; i >= 0; i--)
- setMin(i);
- //
- toSet = new int[length];
- while (in.hasNext()) {
- String str = in.next();
- switch (str) {
- case "attack":
- int left = in.nextInt() - 1;
- int right = in.nextInt() - 1;
- int min[] = getMin(0, 0, newN - 1, left, right);
- System.out.println(min[0] + " " + (getPosOfMinByV(min[1]) - newN + 2));
- break;
- default:
- actionInRange(0, 0, newN - 1, in.nextInt() - 1, in.nextInt() - 1, in.nextInt());
- break;
- }
- }
- }
- private static int getPosOfMinByV(int v) {
- int left = v * 2 + 1;
- if (left + 1 < t.length) {
- push(left);
- push(left + 1);
- // setMin(v);
- if (t[left] < t[left + 1]) return getPosOfMinByV(left);
- return getPosOfMinByV(left + 1);
- }
- return v;
- }
- private static int getTrueN(int n) {
- int res = 1;
- while (res < n)
- res <<= 1;
- return res;
- }
- }
Add Comment
Please, Sign In to add comment