noip模拟34

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

#include <bits/stdc++.h>
#define For(i, l, r) for (long long i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (long long i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const long long maxn = 1000010;

template<typename type>
type read() {
  type s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}

struct LINE {
  long long k, b;
} lne[maxn];
long long n, m;
long long S, maxp;
long long maxx[maxn];
bool cmp(long long a, long long b) {
  return a > b;
}
bool chk(long long pos) {
  long long val;
  For(i, 1, n) {
    val = 1ll * lne[i].k * pos + lne[i].b;
    maxx[i] = max(0ll, val);
  }
  nth_element(maxx + 1, maxx + 1 + m, maxx + 1 + n, greater<long long>());
  val = 0;
  For(i, 1, m) {
    val += maxx[i];
    if (val >= S) return 1;
  }
  return val >= S;
}
int main() {
  n = read<long long>();
  m = read<long long>();
  S = read<long long>();
  For(i, 1, n) {
    lne[i].k = read<long long>();
    lne[i].b = read<long long>();
    if (lne[i].b > S) {
      puts("0");
      return 0;
    }
  }
  if(chk(0)) {
    puts("0");
    return 0;
  }
  long long l = 0, r = 1e9, mid = (l + r) / 2;
  while (r - l > 1) {
    if (chk(mid)) r = mid;
    else l = mid;
    mid = (l + r) / 2;
  }
  cout << r << endl;
  return 0;
}

  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
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

#include <bits/stdc++.h>
#define For(i, l, r) for (long long i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (long long i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const long long maxn = 1001000;

template<typename type>
type read() {
  type s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}

struct EDGE {
  long long to, nxt, w;
} edge[maxn];
long long head[maxn], tote;
void addEdge(long long from, long long to) {
  edge[++tote].to = to;
  edge[tote].nxt = head[from];
  head[from] = tote;
}

long long qz[maxn], w[maxn];

long long TMSP, dep[maxn], l[maxn], r[maxn];
void dfs(long long id) {
  l[id] = ++TMSP;
  for(long long i = head[id]; i; i = edge[i].nxt) {
    long long to = edge[i].to;
    dep[to] = dep[id] + 1;
    qz[to] = w[to] - qz[id];
    dfs(to);
  }
  r[id] = TMSP;
}

class tree {
public:
  long long v[maxn], v1[maxn];
  
  long long n;
  long long lowbit(long long x) { return x & -x; }
  void add(long long x, long long y) {
    for (; x <= n; x += lowbit(x)) v[x] += y;
  }
  long long getsum(long long x) {
    long long ans = 0;
    long long org = x;
    x = l[x];
    for (; x; x -= lowbit(x)) ans += v[x];
    if(dep[org] & 1)
      return ans;
    else
      return -ans;
  }
  void add(long long l, long long r, long long v) {
    add(l, v);
    add(r + 1, -v);
  }
} tr;

long long n, q;
int main() {
  n = read<long long>();
  q = read<long long>();
  tr.n = n;
  For(i, 2, n) {
    long long from;
    from = read<long long>();
    w[i] = read<long long>();
    addEdge(from, i);
  }
  dep[1] = 1;
  dfs(1);
  For(i, 1, q) {
    long long type;
    type = read<long long>();
    if (type == 1) {
      long long u, v, s;
      u = read<long long>();
      v = read<long long>();
      s = read<long long>();
      long long tmpu, tmpv;
      tmpu = qz[u] + tr.getsum( u);
      tmpv = qz[v] + tr.getsum( v);
      if ((dep[u] & 1) && (dep[v] & 1)) {
        long long lft = s - (tmpu + tmpv);
        if (lft & 1) {
          puts("none");
        } else {
          cout << lft / 2 << endl;
        }
      } else {
        if(!(dep[u] & 1) && !(dep[v] & 1)) {
          long long lft = (tmpu + tmpv) - s;
          if (lft & 1) {
            puts("none");
          } else {
            cout << lft / 2 << endl;
          }
        } else {
            if (tmpu + tmpv == s) puts("inf");
          else puts("none");
        }
      }
    }
    if (type == 2) {
      long long u, v;
      u = read<long long>();
      v = read<long long>();
      long long dlt = v - w[u];
      w[u] = v;
      if (dep[u] % 2 == 0) dlt *= -1;
      tr.add(l[u], r[u], dlt);
    }
  }
  return 0;
}