IzhanVarsky

Untitled

Mar 24th, 2019
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.96 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.             if (flags[v] == 1 && toSet[v] >= value){
  56.                 push(v);
  57.                 return;
  58.             }
  59.             flags[v] = 1;
  60.             toSet[v] = value;
  61.             push(v);
  62.         } else {
  63.             push(v);
  64.             int mid = (left + right) / 2;
  65.             actionInRange(v * 2 + 1, left, mid, a, Math.min(b, mid), value);
  66.             actionInRange(v * 2 + 2, mid + 1, right, Math.max(a, mid + 1), b, value);
  67.             setMin(v);
  68.         }
  69.     }
  70.  
  71.     public static void main(String[] args) {
  72.         Scanner in = new Scanner(System.in);
  73.         int n = in.nextInt();
  74.         in.nextInt();
  75.         int newN = getTrueN(n);
  76.         int length = newN * 2 - 1;
  77.         t = new int[length];
  78.         flags = new int[length];
  79.         // build
  80.         for (int i = 0; i < length; i++)
  81.             t[i] = INF;
  82.         for (int i = 0; i < n; i++)
  83.             t[newN - 1 + i] = 0;
  84.         for (int i = newN - 2; i >= 0; i--)
  85.             setMin(i);
  86.         //
  87.         toSet = new int[length];
  88.         while (in.hasNext()) {
  89.             String str = in.next();
  90.             switch (str) {
  91.                 case "attack":
  92.                     int left = in.nextInt() - 1;
  93.                     int right = in.nextInt() - 1;
  94.                     int min[] = getMin(0, 0, newN - 1, left, right);
  95.                     System.out.println(min[0] + " " + (getPosOfMinByV(min[1]) - newN + 2));
  96.                     break;
  97.                 default:
  98.                     actionInRange(0, 0, newN - 1, in.nextInt() - 1, in.nextInt() - 1, in.nextInt());
  99.                     break;
  100.             }
  101.         }
  102.     }
  103.  
  104.     private static int getPosOfMinByV(int v) {
  105.         int left = v * 2 + 1;
  106.         if (left + 1 < t.length) {
  107.             push(left);
  108.             push(left + 1);
  109. //            setMin(v);
  110.             if (t[left] < t[left + 1]) return getPosOfMinByV(left);
  111.             return getPosOfMinByV(left + 1);
  112.         }
  113.         return v;
  114.     }
  115.  
  116.     private static int getTrueN(int n) {
  117.         int res = 1;
  118.         while (res < n)
  119.             res <<= 1;
  120.         return res;
  121.     }
  122. }
Add Comment
Please, Sign In to add comment