Submission #302405

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
302405	2020-09-18 16:23:27	user202729	Palembang Bridges (APIO15_bridge)	C++17	78 / 100	1082 ms	17124 KiB

bridge

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
// might be fast enough. Still log^terrible.
#if not LOCAL
//#define NDEBUG 1
#endif
#include<bits/stdc++.h>
std::vector<int> positions; // it's more convenient to make it global. It's not changed very frequently anyway
/*
 * stores a convex piecewise linear function.
 * the cuts must be in positions.
 */
struct Tree{
  using Data=std::array<int64_t, 2>; // sort of parallel data tuple. Can be used for anything.
  std::vector<Data> data; // "lazy"
  Tree(std::size_t number): data(number*2){}
  static void add1(Data& first, Data sec){
    first[0]+=sec[0];
    first[1]+=sec[1];
  }
  int offset() const{return int(data.size()/2);}
  // get raw {a, b} value at a particular position.
  Data rawGet(int index)const{
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37