Submission #117444

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
117444	2019-06-15 23:46:35	dragonslayerit	Wall (IOI14_wall)	C++14	61 / 100	682 ms	66268 KiB

wall

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 "wall.h"
#include <climits>
#include <algorithm>
#include <cassert>
#include <vector>
//clamps to [a,b]
struct Node{
  int a,b;
  Node():a(INT_MIN),b(INT_MAX){
  }
  Node(int a,int b):a(a),b(b){
    assert(a<=b);
  }
  int eval(int x){
    return std::max(a,std::min(b,x));
  }
};
//apply l, then r
struct Node combine(struct Node l,struct Node r){
  if(l.b<r.a) return Node(r.a,r.a);
  if(l.a>r.b) return Node(r.b,r.b);
  return Node(std::max(l.a,r.a),std::min(l.b,r.b));
}
struct Node st[1000005];
struct Node alt[500005];
std::vector<int> delta[500005];
int K;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 0 / 39