Submission #349136

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
349136	2021-01-16 19:13:11	FlowerOfSorrow	Game (IOI13_game)	C++17	0 / 100	3 ms	1232 KiB

game

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "game.h"
#include<bits/stdc++.h>
using namespace std;
template<class B, class T>
struct persistent_dynamic_segment_tree_2d{
  B n, m; // exclusive upper bound of coordinate
  vector<int> xleft, xright, yleft, yright;
  vector<T> data;
  function<T(T, T)> TT; // monoid operation (always adjacent)
  T T_id; // monoid identity
  function<T(B, B, B, B)> T_init; // monoid default element for the interval [xl, xr) x [yl, yr)
  persistent_dynamic_segment_tree_2d(){ }
  persistent_dynamic_segment_tree_2d(B n, B m, function<T(T, T)> TT, T T_id): persistent_dynamic_segment_tree_2d(n, m, TT, T_id, [&](auto, auto, auto, auto){ return 0LL; }){ }
  persistent_dynamic_segment_tree_2d(B n, B m, function<T(T, T)> TT, T T_id, function<T(B, B, B, B)> T_init): n(n), m(m), TT(TT), T_id(T_id), T_init(T_init){
    new_state(-1, -1, -1, -1, T_init(0, n, 0, m));
  }
  int last_state(){
    return (int)data.size() - 1;
  }
  int new_state(int xv, int xw, int yv, int yw, T x){
    xleft.push_back(xv), xright.push_back(xw), yleft.push_back(yv), yright.push_back(yw), data.push_back(x);
    return last_state();
  }
  void xextend(int u, B xl, B xr){
    if(!~xleft[u]){
      B xm = xl + (xr - xl >> 1);
      xleft[u] = new_state(-1, -1, -1, -1, T_init(xl, xm, 0, m)); // Separate this on C++14 or below to avoid UB
      xright[u] = new_state(-1, -1, -1, -1, T_init(xm, xr, 0, m)); // Separate this on C++14 or below to avoid UB
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

game.cpp: In instantiation of 'int persistent_dynamic_segment_tree_2d<B, T>::set(int, B, B, T) [with B = int; T = long long int]':
game.cpp:95:33:   required from here
game.cpp:44:21: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   44 |     B ym = yl + (yr - yl >> 1);
      |                  ~~~^~~~
game.cpp:52:20: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   52 |    B xm = xl + (xr - xl >> 1);
      |                 ~~~^~~~
game.cpp: In instantiation of 'T persistent_dynamic_segment_tree_2d<B, T>::query(int, B, B, B, B) [with B = int; T = long long int]':
game.cpp:99:53:   required from here
game.cpp:67:21: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   67 |     B ym = yl + (yr - yl >> 1);
      |                  ~~~^~~~
game.cpp:72:20: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   72 |    B xm = xl + (xr - xl >> 1);
      |                 ~~~^~~~
game.cpp: In instantiation of 'void persistent_dynamic_segment_tree_2d<B, T>::yextend(int, B, B, B, B) [with B = int; T = long long int]':
game.cpp:43:5:   required from 'int persistent_dynamic_segment_tree_2d<B, T>::set(int, B, B, T) [with B = int; T = long long int]'
game.cpp:95:33:   required from here
game.cpp:34:20: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   34 |    B ym = yl + (yr - yl >> 1);
      |                 ~~~^~~~
game.cpp: In instantiation of 'void persistent_dynamic_segment_tree_2d<B, T>::xextend(int, B, B) [with B = int; T = long long int]':
game.cpp:51:4:   required from 'int persistent_dynamic_segment_tree_2d<B, T>::set(int, B, B, T) [with B = int; T = long long int]'
game.cpp:95:33:   required from here
game.cpp:27:20: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   27 |    B xm = xl + (xr - xl >> 1);
      |                 ~~~^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20