Advertisement
IzhanVarsky

Untitled

Mar 24th, 2019
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.84 KB | None | 0 0
  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.     private static int[] t;
  5.     private static int[] flags;
  6.     // 0 - not modified
  7.     // 1 - нужно обновить минимум
  8.     private static int[] toSet;
  9.     private static int INF = 2_000_000_000;
  10.  
  11.     private static void push(int v) {
  12.         if (flags[v] == 1) {
  13.             t[v] = toSet[v];
  14.             flags[v] = 0;
  15.             int left = v * 2 + 1;
  16.             if (left + 1 < t.length) { // если v - не лист
  17.                 if ((flags[left] == 1 && toSet[left] < t[v]) || (flags[left] == 0 && t[left] < t[v])) {
  18.                     toSet[left] = t[v];
  19.                     flags[left] = 1;
  20.                 }
  21.                 left++; // стал правым
  22.                 if ((flags[left] == 1 && toSet[left] < t[v]) || (flags[left] == 0 && t[left] < t[v])) {
  23.                     toSet[left] = t[v];
  24.                     flags[left] = 1;
  25.                 }
  26.             }
  27.         }
  28.     }
  29.  
  30.     private static void setMin(int i) {
  31.         if (2 * i + 2 < t.length) {
  32.             push(i * 2 + 1);
  33.             push(i * 2 + 2);
  34.             t[i] = Math.min(t[i * 2 + 1], t[i * 2 + 2]);
  35.         }
  36.     }
  37.  
  38.     private static int[] getMin(int v, int left, int right, int a, int b) {
  39.         if (a > right || b < left) return new int[]{INF, 0};
  40.         push(v);
  41.         if (a == left && b == right) {
  42.             return new int[]{t[v], v};
  43.         }
  44.         int mid = (left + right) / 2;
  45.         int x[] = getMin(v * 2 + 1, left, mid, a, Math.min(b, mid));
  46.         int y[] = getMin(v * 2 + 2, mid + 1, right, Math.max(a, mid + 1), b);
  47.         if (x[0] < y[0]) return x;
  48.         return y;
  49.     }
  50.  
  51.     private static void actionInRange(int v, int left, int right, int a, int b, int value) {
  52.         if (a > b) return;
  53.         if (a == left && right == b) {
  54.             if (t[v] >= value) return;
  55.             flags[v] = 1;
  56.             toSet[v] = value;
  57.             push(v);
  58.         } else {
  59.             push(v);
  60.             int mid = (left + right) / 2;
  61.             actionInRange(v * 2 + 1, left, mid, a, Math.min(b, mid), value);
  62.             actionInRange(v * 2 + 2, mid + 1, right, Math.max(a, mid + 1), b, value);
  63.             setMin(v);
  64.         }
  65.     }
  66.  
  67.     public static void main(String[] args) {
  68.         Scanner in = new Scanner(System.in);
  69.         int n = in.nextInt();
  70.         in.nextInt();
  71.         int newN = getTrueN(n);
  72.         int length = newN * 2 - 1;
  73.         t = new int[length];
  74.         flags = new int[length];
  75.         // build
  76.         for (int i = 0; i < length; i++)
  77.             t[i] = INF;
  78.         for (int i = 0; i < n; i++)
  79.             t[newN - 1 + i] = 0;
  80.         for (int i = newN - 2; i >= 0; i--)
  81.             setMin(i);
  82.         //
  83.         toSet = new int[length];
  84.         while (in.hasNext()) {
  85.             String str = in.next();
  86.             switch (str) {
  87.                 case "attack":
  88.                     int left = in.nextInt() - 1;
  89.                     int right = in.nextInt() - 1;
  90.                     int min[] = getMin(0, 0, newN - 1, left, right);
  91.                     System.out.println(min[0] + " " + (getPosOfMinByV(min[1]) - newN + 2));
  92.                     break;
  93.                 default:
  94.                     actionInRange(0, 0, newN - 1, in.nextInt() - 1, in.nextInt() - 1, in.nextInt());
  95.                     break;
  96.             }
  97.         }
  98.     }
  99.  
  100.     private static int getPosOfMinByV(int v) {
  101.         int left = v * 2 + 1;
  102.         if (left + 1 < t.length) {
  103.             push(left);
  104.             push(left + 1);
  105.             setMin(v);
  106.             if (t[left] < t[left + 1]) return getPosOfMinByV(left);
  107.             return getPosOfMinByV(left + 1);
  108.         }
  109.         return v;
  110.     }
  111.  
  112.     private static int getTrueN(int n) {
  113.         int res = 1;
  114.         while (res < n)
  115.             res <<= 1;
  116.         return res;
  117.     }
  118. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement