Submission #300154

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
300154	2020-09-16T21:48:15 Z	model_code	Comparing Plants (IOI20_plants)	C++17	Compilation error	0 ms	0 KB

plants

// plants-yanhao-k_large
class segtree {
	final int n_bits=18;
	final int inf = (int)1e9;
	int[] arr = new int [1<<(n_bits+1)];
	int[] lazyadd = new int [1<<(n_bits+1)];
    int node = 1;
    int lazy = 0;
	int low(int i) {
		return (i<<(Integer.numberOfLeadingZeros(i)-31+n_bits))-(1<<n_bits);
	}
	int high(int i) {
		return ((i+1)<<(Integer.numberOfLeadingZeros(i)-31+n_bits))-(1<<n_bits)-1;
	}
    void build(int[] v) {
        assert(v.length<(1<<n_bits));
        for(int i=0; i<(1<<n_bits); i++) {
            arr[i+(1<<n_bits)] = (i<v.length ? v[i] : inf);
        }
        for(int i=(1<<n_bits)-1; i>=1; i--) {
            arr[i] = Math.min(arr[2*i], arr[2*i+1]);
        }
        for(int i=0; i<(1<<(n_bits+1)); i++) {
            lazyadd[i] = 0;
        }
    }

    void decr(int left, int right) {
        node = 1;
        while(node != 0) {
            if(right>=high(node) && left<=low(node)) {
                lazyadd[node]--;
                while(node%2==0) {
                    arr[node/2] = Math.min(arr[node]+lazyadd[node], arr[node+1]+lazyadd[node+1]);
                    node = node/2;
                }
                node--;
            } else if(right<low(node) || left>high(node)) {
                while(node%2==0) {
                    arr[node/2] = Math.min(arr[node]+lazyadd[node], arr[node+1]+lazyadd[node+1]);
                    node = node/2;
                }
                node--;
            } else {
                node = node*2+1;
            }
        }
    }

    void pt_update(int x) {
        x += (1<<n_bits);
        arr[x] = (int)1e9;
        while(x!=0) {
            arr[x/2] = Math.min(arr[x]+lazyadd[x], arr[x^1]+lazyadd[x^1]);
            x = x/2;
        }
    }

    int find_zero() {
        node = 1;
        lazy = 0;
        if(lazyadd[1] + arr[1]!=0) return -1;
        while(node < (1<<n_bits)) {
            lazy += lazyadd[node];
            node *= 2;
            if(lazy + lazyadd[node] + arr[node] != 0) node++;
        }
        return node-(1<<n_bits);
    }
};

class plants {
	final int n_max = (int)2e5+5;
	int[] p_lt = new int[n_max];
	int[] p_rg = new int[n_max];
	int[] stash = new int[n_max]; // a manual queue
	int[] tallest = new int[n_max];
	int[] shortest = new int[n_max];
	void lexi_smallest(int k, int[] r, int[] ptr, int[] ord) {
		segtree s = new segtree();
		s.build(r);
		int n = r.length;
		stash[0] = n;
		ord[n] = -1;
		int front = 1;
		int back = 1;
		for(int i=0; i<r.length; i++) {
			int p = s.find_zero();
			while(p==-1) {
				s.decr(stash[front]-k+1+n, n-1);
				front++;
				p = s.find_zero();
			}
			ord[p] = i;
			s.pt_update(p);
			if(p<k-1) {
				s.decr(0, p);
				stash[back] = p;
				back++;
			} else {
				s.decr(p-k+1, p);
			}
			ptr[p] = ord[stash[front-1]];
		}
	}
	
	void init(int k, int[] r) {
		lexi_smallest(k, r, p_lt, tallest);
		for(int i=0; i<r.length; i++) {
			r[i] = k-1-r[i];
		}
		lexi_smallest(k, r, p_rg, shortest);
	}

	int compare_plants(int x, int y) {
		if(x>y) return -compare_plants(y,x);
		if(tallest[x]>tallest[y] || p_rg[y]>=shortest[x]) return -1;
		if(shortest[x]>shortest[y] || p_lt[y]>=tallest[x]) return 1;
		return 0;
	}
}

Compilation message

plants.cpp:3:2: error: 'final' does not name a type
    3 |  final int n_bits=18;
      |  ^~~~~
plants.cpp:4:2: error: 'final' does not name a type
    4 |  final int inf = (int)1e9;
      |  ^~~~~
plants.cpp:5:5: error: expected unqualified-id before '[' token
    5 |  int[] arr = new int [1<<(n_bits+1)];
      |     ^
plants.cpp:6:5: error: expected unqualified-id before '[' token
    6 |  int[] lazyadd = new int [1<<(n_bits+1)];
      |     ^
plants.cpp:15:22: error: expected ',' or '...' before 'v'
   15 |     void build(int[] v) {
      |                      ^
plants.cpp: In member function 'int segtree::low(int)':
plants.cpp:10:15: error: 'Integer' was not declared in this scope
   10 |   return (i<<(Integer.numberOfLeadingZeros(i)-31+n_bits))-(1<<n_bits);
      |               ^~~~~~~
plants.cpp:10:50: error: 'n_bits' was not declared in this scope
   10 |   return (i<<(Integer.numberOfLeadingZeros(i)-31+n_bits))-(1<<n_bits);
      |                                                  ^~~~~~
plants.cpp: In member function 'int segtree::high(int)':
plants.cpp:13:19: error: 'Integer' was not declared in this scope
   13 |   return ((i+1)<<(Integer.numberOfLeadingZeros(i)-31+n_bits))-(1<<n_bits)-1;
      |                   ^~~~~~~
plants.cpp:13:54: error: 'n_bits' was not declared in this scope
   13 |   return ((i+1)<<(Integer.numberOfLeadingZeros(i)-31+n_bits))-(1<<n_bits)-1;
      |                                                      ^~~~~~
plants.cpp: In member function 'void segtree::build(int*)':
plants.cpp:16:16: error: 'v' was not declared in this scope
   16 |         assert(v.length<(1<<n_bits));
      |                ^
plants.cpp:16:29: error: 'n_bits' was not declared in this scope
   16 |         assert(v.length<(1<<n_bits));
      |                             ^~~~~~
plants.cpp:16:9: error: 'assert' was not declared in this scope
   16 |         assert(v.length<(1<<n_bits));
      |         ^~~~~~
plants.cpp:1:1: note: 'assert' is defined in header '<cassert>'; did you forget to '#include <cassert>'?
  +++ |+#include <cassert>
    1 | // plants-yanhao-k_large
plants.cpp:18:13: error: 'arr' was not declared in this scope
   18 |             arr[i+(1<<n_bits)] = (i<v.length ? v[i] : inf);
      |             ^~~
plants.cpp:18:55: error: 'inf' was not declared in this scope; did you mean 'int'?
   18 |             arr[i+(1<<n_bits)] = (i<v.length ? v[i] : inf);
      |                                                       ^~~
      |                                                       int
plants.cpp:21:13: error: 'arr' was not declared in this scope
   21 |             arr[i] = Math.min(arr[2*i], arr[2*i+1]);
      |             ^~~
plants.cpp:21:22: error: 'Math' was not declared in this scope
   21 |             arr[i] = Math.min(arr[2*i], arr[2*i+1]);
      |                      ^~~~
plants.cpp:24:13: error: 'lazyadd' was not declared in this scope; did you mean 'lazy'?
   24 |             lazyadd[i] = 0;
      |             ^~~~~~~
      |             lazy
plants.cpp: In member function 'void segtree::decr(int, int)':
plants.cpp:32:17: error: 'lazyadd' was not declared in this scope; did you mean 'lazy'?
   32 |                 lazyadd[node]--;
      |                 ^~~~~~~
      |                 lazy
plants.cpp:34:21: error: 'arr' was not declared in this scope
   34 |                     arr[node/2] = Math.min(arr[node]+lazyadd[node], arr[node+1]+lazyadd[node+1]);
      |                     ^~~
plants.cpp:34:35: error: 'Math' was not declared in this scope
   34 |                     arr[node/2] = Math.min(arr[node]+lazyadd[node], arr[node+1]+lazyadd[node+1]);
      |                                   ^~~~
plants.cpp:40:21: error: 'arr' was not declared in this scope
   40 |                     arr[node/2] = Math.min(arr[node]+lazyadd[node], arr[node+1]+lazyadd[node+1]);
      |                     ^~~
plants.cpp:40:35: error: 'Math' was not declared in this scope
   40 |                     arr[node/2] = Math.min(arr[node]+lazyadd[node], arr[node+1]+lazyadd[node+1]);
      |                                   ^~~~
plants.cpp:40:54: error: 'lazyadd' was not declared in this scope; did you mean 'lazy'?
   40 |                     arr[node/2] = Math.min(arr[node]+lazyadd[node], arr[node+1]+lazyadd[node+1]);
      |                                                      ^~~~~~~
      |                                                      lazy
plants.cpp: In member function 'void segtree::pt_update(int)':
plants.cpp:51:18: error: 'n_bits' was not declared in this scope
   51 |         x += (1<<n_bits);
      |                  ^~~~~~
plants.cpp:52:9: error: 'arr' was not declared in this scope
   52 |         arr[x] = (int)1e9;
      |         ^~~
plants.cpp:54:24: error: 'Math' was not declared in this scope
   54 |             arr[x/2] = Math.min(arr[x]+lazyadd[x], arr[x^1]+lazyadd[x^1]);
      |                        ^~~~
plants.cpp:54:40: error: 'lazyadd' was not declared in this scope; did you mean 'lazy'?
   54 |             arr[x/2] = Math.min(arr[x]+lazyadd[x], arr[x^1]+lazyadd[x^1]);
      |                                        ^~~~~~~
      |                                        lazy
plants.cpp: In member function 'int segtree::find_zero()':
plants.cpp:62:12: error: 'lazyadd' was not declared in this scope; did you mean 'lazy'?
   62 |         if(lazyadd[1] + arr[1]!=0) return -1;
      |            ^~~~~~~
      |            lazy
plants.cpp:62:25: error: 'arr' was not declared in this scope
   62 |         if(lazyadd[1] + arr[1]!=0) return -1;
      |                         ^~~
plants.cpp:63:26: error: 'n_bits' was not declared in this scope
   63 |         while(node < (1<<n_bits)) {
      |                          ^~~~~~
plants.cpp:64:21: error: 'lazyadd' was not declared in this scope; did you mean 'lazy'?
   64 |             lazy += lazyadd[node];
      |                     ^~~~~~~
      |                     lazy
plants.cpp:66:39: error: 'arr' was not declared in this scope
   66 |             if(lazy + lazyadd[node] + arr[node] != 0) node++;
      |                                       ^~~
plants.cpp:68:25: error: 'n_bits' was not declared in this scope
   68 |         return node-(1<<n_bits);
      |                         ^~~~~~
plants.cpp: At global scope:
plants.cpp:73:2: error: 'final' does not name a type
   73 |  final int n_max = (int)2e5+5;
      |  ^~~~~
plants.cpp:74:5: error: expected unqualified-id before '[' token
   74 |  int[] p_lt = new int[n_max];
      |     ^
plants.cpp:75:5: error: expected unqualified-id before '[' token
   75 |  int[] p_rg = new int[n_max];
      |     ^
plants.cpp:76:5: error: expected unqualified-id before '[' token
   76 |  int[] stash = new int[n_max]; // a manual queue
      |     ^
plants.cpp:77:5: error: expected unqualified-id before '[' token
   77 |  int[] tallest = new int[n_max];
      |     ^
plants.cpp:78:5: error: expected unqualified-id before '[' token
   78 |  int[] shortest = new int[n_max];
      |     ^
plants.cpp:79:34: error: expected ',' or '...' before 'r'
   79 |  void lexi_smallest(int k, int[] r, int[] ptr, int[] ord) {
      |                                  ^
plants.cpp:107:25: error: expected ',' or '...' before 'r'
  107 |  void init(int k, int[] r) {
      |                         ^
plants.cpp:121:2: error: expected ';' after class definition
  121 | }
      |  ^
      |  ;
plants.cpp: In member function 'void plants::lexi_smallest(int, int*)':
plants.cpp:80:15: error: conversion from 'segtree*' to non-scalar type 'segtree' requested
   80 |   segtree s = new segtree();
      |               ^~~~~~~~~~~~~
plants.cpp:81:11: error: 'r' was not declared in this scope
   81 |   s.build(r);
      |           ^
plants.cpp:83:3: error: 'stash' was not declared in this scope
   83 |   stash[0] = n;
      |   ^~~~~
plants.cpp:84:3: error: 'ord' was not declared in this scope
   84 |   ord[n] = -1;
      |   ^~~
plants.cpp:88:24: error: 'int segtree::find_zero()' is private within this context
   88 |    int p = s.find_zero();
      |                        ^
plants.cpp:59:9: note: declared private here
   59 |     int find_zero() {
      |         ^~~~~~~~~
plants.cpp:92:21: error: 'int segtree::find_zero()' is private within this context
   92 |     p = s.find_zero();
      |                     ^
plants.cpp:59:9: note: declared private here
   59 |     int find_zero() {
      |         ^~~~~~~~~
plants.cpp:95:17: error: 'void segtree::pt_update(int)' is private within this context
   95 |    s.pt_update(p);
      |                 ^
plants.cpp:50:10: note: declared private here
   50 |     void pt_update(int x) {
      |          ^~~~~~~~~
plants.cpp:97:16: error: 'void segtree::decr(int, int)' is private within this context
   97 |     s.decr(0, p);
      |                ^
plants.cpp:28:10: note: declared private here
   28 |     void decr(int left, int right) {
      |          ^~~~
plants.cpp:101:20: error: 'void segtree::decr(int, int)' is private within this context
  101 |     s.decr(p-k+1, p);
      |                    ^
plants.cpp:28:10: note: declared private here
   28 |     void decr(int left, int right) {
      |          ^~~~
plants.cpp:103:4: error: 'ptr' was not declared in this scope
  103 |    ptr[p] = ord[stash[front-1]];
      |    ^~~
plants.cpp: In member function 'void plants::init(int, int*)':
plants.cpp:108:20: error: 'r' was not declared in this scope
  108 |   lexi_smallest(k, r, p_lt, tallest);
      |                    ^
plants.cpp:108:23: error: 'p_lt' was not declared in this scope
  108 |   lexi_smallest(k, r, p_lt, tallest);
      |                       ^~~~
plants.cpp:108:29: error: 'tallest' was not declared in this scope
  108 |   lexi_smallest(k, r, p_lt, tallest);
      |                             ^~~~~~~
plants.cpp:112:23: error: 'p_rg' was not declared in this scope
  112 |   lexi_smallest(k, r, p_rg, shortest);
      |                       ^~~~
plants.cpp:112:29: error: 'shortest' was not declared in this scope; did you mean 'short'?
  112 |   lexi_smallest(k, r, p_rg, shortest);
      |                             ^~~~~~~~
      |                             short
plants.cpp: In member function 'int plants::compare_plants(int, int)':
plants.cpp:117:6: error: 'tallest' was not declared in this scope
  117 |   if(tallest[x]>tallest[y] || p_rg[y]>=shortest[x]) return -1;
      |      ^~~~~~~
plants.cpp:117:31: error: 'p_rg' was not declared in this scope
  117 |   if(tallest[x]>tallest[y] || p_rg[y]>=shortest[x]) return -1;
      |                               ^~~~
plants.cpp:117:40: error: 'shortest' was not declared in this scope; did you mean 'short'?
  117 |   if(tallest[x]>tallest[y] || p_rg[y]>=shortest[x]) return -1;
      |                                        ^~~~~~~~
      |                                        short
plants.cpp:118:6: error: 'shortest' was not declared in this scope; did you mean 'short'?
  118 |   if(shortest[x]>shortest[y] || p_lt[y]>=tallest[x]) return 1;
      |      ^~~~~~~~
      |      short
plants.cpp:118:33: error: 'p_lt' was not declared in this scope
  118 |   if(shortest[x]>shortest[y] || p_lt[y]>=tallest[x]) return 1;
      |                                 ^~~~
plants.cpp:118:42: error: 'tallest' was not declared in this scope
  118 |   if(shortest[x]>shortest[y] || p_lt[y]>=tallest[x]) return 1;
      |                                          ^~~~~~~