結果
| 問題 | No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ |
| ユーザー |
 ぴろず
|
| 提出日時 | 2015-11-27 12:45:12 |
| 言語 | Java (openjdk 23) |
| 結果 |
MLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 8,741 bytes |
| コンパイル時間 | 2,920 ms |
| コンパイル使用メモリ | 84,620 KB |
| 実行使用メモリ | 264,964 KB |
| 最終ジャッジ日時 | 2024-10-12 19:32:42 |
| 合計ジャッジ時間 | 43,017 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 1 MLE * 9 |
ソースコード
package waruagaki;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.ArrayList;import java.util.HashMap;import java.util.InputMismatchException;import java.util.NoSuchElementException;import java.util.TreeSet;public class Main {public static final long MOD = 1000000000000000009L;public static long[] solve(long n,int q,int[] x,long[] l,long[] r) {TreeSet<Long> ts = new TreeSet<>();for(int i=0;i<q;i++) {ts.add(l[i]);ts.add(r[i]);}HashMap<Long, Integer> map = new HashMap<>();ArrayList<Long> weight = new ArrayList<>();int ind = 0;long bef = -1;for(Long lg:ts) {map.put(lg, ind++);if (bef != -1) {weight.add(lg - bef);}bef = lg;}weight.add(0L);//System.out.println(map);// System.out.println(weight);int m = weight.size();Splarrraaay[] sp = new Splarrraaay[5];for(int i=0;i<5;i++) {// if (i == 0) {sp[i] = new Splarrraaay(m, weight);// }else{// sp[i] = new Splarrraaay(m, sp[0].weight);// }}long[] ans = new long[5];for(int qq=0;qq<q;qq++) {if (x[qq] == 0) {long[] point = new long[5];for(int i=0;i<5;i++) {point[i] = sp[i].sum(map.get(l[qq]), map.get(r[qq]));}long max = -1;int maxi = -1;for(int i=0;i<5;i++) {if (point[i] > max) {max = point[i];maxi = i;}else if(point[i] == max) {maxi = -1;}}if (maxi >= 0) {ans[maxi] += max;if (ans[maxi] >= MOD) {ans[maxi] -= MOD;}}// System.out.println(Arrays.toString(point));// System.out.println(maxi + " gain " + max + " points");}else{// System.out.println("----");for(int i=0;i<5;i++) {if (x[qq] - 1 == i) {sp[i].add(map.get(l[qq]), map.get(r[qq]), 1);}else{sp[i].set(map.get(l[qq]), map.get(r[qq]), 0);}// System.out.println(sp[i]);}}}for(int i=0;i<5;i++) {ans[i] += sp[i].sum(0, m);if (ans[i] >= MOD) {ans[i] -= MOD;}}return ans;}public static void main(String[] args) {IO io = new IO();long n = io.nextLong();int q = io.nextInt();int[] x = new int[q];long[] l = new long[q];long[] r = new long[q];for(int i=0;i<q;i++) {x[i] = io.nextInt();l[i] = io.nextLong();r[i] = io.nextLong() + 1;}long[] ans = solve(n,q,x,l,r);for(int i=0;i<5;i++) {if (i > 0) {io.print(" ");}io.print(ans[i]);}io.println();io.flush();}}class Splarrraaay {private int size,n;private long[] sum;long[] weight;private byte[] lazy;private int[] lazyValue;public Splarrraaay(int size,ArrayList<Long> w) {this.size = size;n = 1;while(n<this.size) {n*=2;}sum = new long[n*2-1];lazy = new byte[n*2-1];lazyValue = new int[n*2-1];weight = new long[n*2-1];for(int k=0;k<size;k++) {weight[n-1+k] = w.get(k);}for(int k=n-2;k>=0;k--) {weight[k] = weight[k*2+1] + weight[k*2+2];}}public Splarrraaay(int size,long[] w) {this.size = size;n = 1;while(n<this.size) {n*=2;}sum = new long[n*2-1];lazy = new byte[n*2-1];lazyValue = new int[n*2-1];weight = w;}private void propagate(int k) {if (k < n - 1) {if (lazy[k] == 1) { //setfor(int i=k*2+1;i<=k*2+2;i++) {sum[i] = weight[i] * lazyValue[k];lazy[i] = 1;lazyValue[i] = lazyValue[k];}}else if(lazy[k] == 2) { //addfor(int i=k*2+1;i<=k*2+2;i++) {sum[i] += weight[i] * lazyValue[k];if (lazy[i] == 0) {lazy[i] = 2;lazyValue[i] = lazyValue[k];}else if(lazy[i] == 1) {//lazy[i] = 1;lazyValue[i] += lazyValue[k];}else{//lazy[i] = 2;lazyValue[i] += lazyValue[k];}}}}lazy[k] = 0;}public void set(int begin,int end,int x) {set(begin,end,x,0,0,n);}private void set(int begin,int end,int x,int k,int l,int r) {propagate(k);if (r <= begin || end <= l) {return;}if (begin <= l && r <= end) {sum[k] = x * weight[k];lazy[k] = 1;lazyValue[k] = x;propagate(k);return;}set(begin,end,x,k*2+1,l,(l+r)>>>1);set(begin,end,x,k*2+2,(l+r)>>>1,r);sum[k] = sum[k*2+1] + sum[k*2+2];}public void add(int begin,int end,int x) {add(begin,end,x,0,0,n);}public void add(int begin,int end,int x,int k,int l,int r) {propagate(k);if (r <= begin || end <= l) {return;}if (begin <= l && r <= end) {sum[k] += x * weight[k];lazy[k] = 2;lazyValue[k] = x;propagate(k);return;}add(begin,end,x,k*2+1,l,(l+r)>>>1);add(begin,end,x,k*2+2,(l+r)>>>1,r);sum[k] = sum[k*2+1] + sum[k*2+2];}public long sum(int begin,int end) {return sum(begin,end,0,0,n);}private long sum(int begin,int end,int k,int l,int r) {propagate(k);if (r <= begin || end <= l) {return 0;}if (begin <= l && r <= end) {return sum[k];}long ret = sum(begin,end,k*2+1,l,(l+r)/2) + sum(begin,end,k*2+2,(l+r)/2,r);sum[k] = sum[k*2+1] + sum[k*2+2];return ret;}//debugpublic String toString() {ArrayList<Long> data = new ArrayList<>();for(int i=0;i<size;i++) {data.add(sum(i, i+1));}return data.toString();}}class IO extends PrintWriter {private final InputStream in;private final byte[] buffer = new byte[1024];private int ptr = 0;private int buflen = 0;public IO() { this(System.in);}public IO(InputStream source) { super(System.out); this.in = source;}private boolean hasNextByte() {if (ptr < buflen) {return true;}else{ptr = 0;try {buflen = in.read(buffer);} catch (IOException e) {e.printStackTrace();}if (buflen <= 0) {return false;}}return true;}private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}private static boolean isNewLine(int c) { return c == '\n' || c == '\r';}public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}public boolean hasNextLine() { while(hasNextByte() && isNewLine(buffer[ptr])) ptr++; return hasNextByte();}public String next() {if (!hasNext()) {throw new NoSuchElementException();}StringBuilder sb = new StringBuilder();int b = readByte();while(isPrintableChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}public char[] nextCharArray(int len) {if (!hasNext()) {throw new NoSuchElementException();}char[] s = new char[len];int i = 0;int b = readByte();while(isPrintableChar(b)) {if (i == len) {throw new InputMismatchException();}s[i++] = (char) b;b = readByte();}return s;}public String nextLine() {if (!hasNextLine()) {throw new NoSuchElementException();}StringBuilder sb = new StringBuilder();int b = readByte();while(!isNewLine(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}public long nextLong() {if (!hasNext()) {throw new NoSuchElementException();}long n = 0;boolean minus = false;int b = readByte();if (b == '-') {minus = true;b = readByte();}if (b < '0' || '9' < b) {throw new NumberFormatException();}while(true){if ('0' <= b && b <= '9') {n *= 10;n += b - '0';}else if(b == -1 || !isPrintableChar(b)){return minus ? -n : n;}else{throw new NumberFormatException();}b = readByte();}}public int nextInt() {long nl = nextLong();if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {throw new NumberFormatException();}return (int) nl;}public char nextChar() {if (!hasNext()) {throw new NoSuchElementException();}return (char) readByte();}public double nextDouble() { return Double.parseDouble(next());}public int[] nextIntArray(int n) { int[] a = new int[n]; for(int i=0;i<n;i++) a[i] = nextInt(); return a;}public long[] nextLongArray(int n) { long[] a = new long[n]; for(int i=0;i<n;i++) a[i] = nextLong(); return a;}public double[] nextDoubleArray(int n) { double[] a = new double[n]; for(int i=0;i<n;i++) a[i] = nextDouble(); return a;}public void nextIntArrays(int[]... a) { for(int i=0;i<a[0].length;i++) for(int j=0;j<a.length;j++) a[j][i] = nextInt();}public int[][] nextIntMatrix(int n,int m) { int[][] a = new int[n][]; for(int i=0;i<n;i++) a[i] = nextIntArray(m); return a;}public char[][] nextCharMap(int n,int m) { char[][] a = new char[n][]; for(int i=0;i<n;i++) a[i] = nextCharArray(m); return a;}public void close() { super.close(); try {in.close();} catch (IOException e) {}}}