Submission #630974

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
630974	2022-08-17 11:46:44	prvocislo	Radio Towers (IOI22_towers)	C++17	100 / 100	2130 ms	37300 KiB

towers

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 "towers.h"
#include <algorithm>
#include <iostream>
#include <vector>
typedef long long ll;
using namespace std;
const int maxn = 1 << 17, inf = 1e9 + 5;
struct node1 { int mi, mx, dix, dxi; node1() { mi = inf, mx = -inf, dix = 0, dxi = 0; } };
vector<node1> tmx(maxn * 2);
vector<int> h;
node1 merge(node1 l, node1 r)
{
  node1 n;
  n.mi = min(l.mi, r.mi);
  n.mx = max(l.mx, r.mx);
  n.dix = max({ l.dix, r.dix, r.mx - l.mi });
  n.dxi = max({ l.dxi, r.dxi, l.mx - r.mi });
  return n;
}
node1 query(int l, int r)
{
  node1 n1, n2;
  for (l += maxn, r += maxn + 1; l < r; l >>= 1, r >>= 1)
  {
    if (l & 1) n1 = merge(n1, tmx[l++]);
    if (r & 1) n2 = merge(tmx[--r], n2);
  }
  return merge(n1, n2);
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

towers.cpp: In function 'void upd(int, int, int&, int&, int&)':
towers.cpp:42:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  if (i == tr[vr].size()) return;
      |      ~~^~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 17 / 17
• Subtask 6: 19 / 19
• Subtask 7: 23 / 23