avatar
文章
24
标签
19
首页
时间轴
标签
友链
关于
ruogu's blog
首页
时间轴
标签
友链
关于
JOISC2020
阅读量:|评论数:

https://cms.ioi-jp.org/ranking/Ranking.html

https://loj.ac/problems/search?keyword=joisc+2020

https://blog.csdn.net/zhouyuyang233/article/details/105010508

打的很差。

Day 1

100+2+11100+2+11。C还会1111分。

A

我竟然做了90min90min。。swk开局就秒了。

我在20min20min的时候其实想到了，但是比较模糊，否定了。

先从左往右尽力匹配，然后再从右往左依次贪心考虑是否调整。

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define MOD 1000000007
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();	
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
//ruogu_alter
const int N = 1e6 + 5;
int n, f[N], a[2][N], cc, c[N], to[N];
bool ok[N];
//
int main() {
  n = getint();
  rep(i, n << 1) a[0][i] = getint();
  rep(i, n << 1) a[1][i] = getint();
  c[0] = (a[0][0] < a[1][0] ? 0 : 1); cc = c[0];
  for (int i = 1; i < n * 2; i++) {
    int mn = min(a[0][i], a[1][i]);
    if (mn < a[c[i - 1]][i - 1]) mn = max(a[0][i], a[1][i]);
    if (mn < a[c[i - 1]][i - 1]) return !printf("%d\n", -1);
    c[i] = (a[1][i] == mn); cc += c[i];
  }
  a[0][n << 1] = a[1][n << 1] = INF;
  for (int i = 2 * n - 1; i >= 0; i--) {
    if (cc == n) break;
    bool fg = true;
    {
    if (a[1 - c[i]][i] <= a[c[i + 1]][i + 1]) {
      f[i] = 1 - c[i] - c[i];
      to[i] = i;
    }
    else if (a[1 - c[i]][i] <= a[1 - c[i + 1]][i + 1] && ok[i + 1]) {
      f[i] = 1 - c[i] - c[i] + f[i + 1];
      to[i] = to[i + 1];
    }
    else fg = false;
    }
    if (a[1 - c[i]][i] < a[c[i]][i]) fg = false;
    ok[i] = fg;
    if (fg && abs(cc + f[i] - n) < abs(cc - n)) {
      ok[i] = false;
      cc += f[i];
      for (int j = i; j <= to[i]; j++) c[j] = 1 - c[j];
      f[i] = 0;
    }
  }
  if (cc != n) return !printf("%d\n", -1);
  rep(i, n << 1) printf("%c",'A' + c[i]);
  return 0;
}

B

只会22分。

ouuan写了随机化得了100100，好厉害。。

C

我现场会前三个subtask。第三个写不完了。

方法11(https://blog.csdn.net/qq_39972971/article/details/105074209)：

考虑没有插入的情况，但凡被影响过一次，一定满足subtask3的限制！

简要的说明，就是每做一次操作，点都至少在那个矩形的边界上，感性理解一下。

至于有插入操作，可以直接在外面套一个线段树分治，来保证操作一段区间的时候，这些点不会中途插入。O(nlog2n)O(nlog^2n)。

我的提交：https://loj.ac/submission/776068

方法2JOISCd1t3

UOJ上有有关提交。。

方法2既好写又好调qaq。。

Day 2

40+100+040+100+0

A

凡是交互题，大抵都很可能与二分有关系。可我没想到。

询问两个点，如果是11连一条边。那么每个点的度数要么11要么33。

连边以后，怎么匹配可以很容易的O(n)O(n)判断。

先想到O(n2)O(n^2)做法。然后考虑，这张图原来是个二分图！

看看代码大抵就懂了，大概是用并查集暴力维护是男还是女。

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
#include <bits/stdc++.h>
#include "chameleon.h"
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define MOD 1000000007
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
using namespace std;
//ruogu_alter
const int N = 1005;
vector<int> g[N], v[2];
int par[N], col[N];
bool ban[N][N];
//
vector<int> doit(vector<int> &v, int x, int y) {
  vector<int> ans;
  ans.emplace_back(y);
  rep(i, v.size()) if (i != x) ans.emplace_back(v[i]);
  return ans;
}
int findset(int x) {
  if (par[x] == x) return x;
  int to = findset(par[x]);
  col[x] ^= col[par[x]];
  return par[x] = to;
}
void unite(int x, int y) {
  int tx = findset(x), ty = findset(y);
  if (tx == ty) return;
  col[ty] = (col[x] == col[y]);
  par[ty] = tx;
}
bool qry(int x, vector<int> &v, int l, int r) {
  vector<int> ans;
  ans.emplace_back(x);
  for (int i = l; i < r; i++) ans.emplace_back(v[i]);
  return Query(ans) != ans.size();
}
void Solve(int n) {
  for (int i = 1; i <= 2 * n; i++) par[i] = i;
  for (int i = 1; i <= 2 * n; i++) {
    rep(j, 2) v[j].clear();
    for (int j = 1; j < i; j++) {
      findset(j);
      v[col[j]].emplace_back(j);
    }
    rep(j, 2) if (v[j].size()) {
      int c = 0;
      while (v[j].size() && qry(i, v[j], 0, v[j].size())) {
        ++c;
        int lb = 0, rb = v[j].size();
        while (rb - lb > 1) {
          int mid = (lb + rb) >> 1;
          if (qry(i, v[j], mid, v[j].size())) lb = mid;
          else rb = mid;
        }
        unite(v[j][lb], i);
        g[v[j][lb]].emplace_back(i);
        g[i].emplace_back(v[j][lb]);
        assert(qry(i, v[j], lb, lb + 1));
        while (v[j].size() > lb) {
          v[j].pop_back();
        }
      }
    }
  }
  for (int i = 1; i <= 2 * n; i++) {
    assert(g[i].size() == 3 || g[i].size() == 1);
  }
  for (int i = 1; i <= 2 * n; i++) if (g[i].size() == 1) {
    if (g[i][0] < i) continue;
    Answer(i, g[i][0]);
  }
  for (int i = 1; i <= 2 * n; i++) if (g[i].size() == 3) {
    rep(j, 3) {
      if (Query(doit(g[i], j, i)) == 1) {
        ban[i][g[i][j]] = ban[g[i][j]][i] = true;
        break;
      }
    }
  }
  for (int i = 1; i <= 2 * n; i++) if (g[i].size() == 3) {
    rep(j, 3) if (!ban[i][g[i][j]]) {
      if (i < g[i][j]) Answer(i, g[i][j]);
    }
  }
}

B

把有双向边的并起来。大力维护就行了。

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define MOD 1000000007
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();	
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
//ruogu_alter
const int N = 1e5 + 5;
ll res;
set<int> g[N], og[N], G[N], OG[N], s[N];
int n, q, par[N], sz[N];
//
int findset(int x) {
  return par[x] == x ? x : par[x] = findset(par[x]);
}
inline void del(int x, int y) {
  if (G[x].find(y) != G[x].end()) G[x].erase(y);
  if (OG[x].find(y) != OG[x].end()) OG[x].erase(y);
}
void solve(int x, int y) {
  assert(x != y);
  if (sz[x] < sz[y]) swap(x, y);
  for (auto &i : s[y]) {
    if (g[i].find(x) != g[i].end()) {
      res -= sz[x];
      g[i].erase(x);
      og[x].erase(i);
    }
    s[x].insert(i);
  }
  for (auto &i : og[y]) {
    g[i].erase(y); res -= sz[y];
    if (findset(i) != x && g[i].find(x) == g[i].end()) {
      og[x].insert(i);
      g[i].insert(x);
      res += sz[x];
    }
  }
  og[y].clear();
  res += 1ll * og[x].size() * sz[y];
  res += 2ll * sz[x] * sz[y];
  sz[x] += sz[y]; par[y] = x;
  vector<int> v;
  del(x, y); del(y, x);
  for (auto &e : G[y]) {
    if (G[e].find(x) != G[e].end()) {
      v.emplace_back(e);
    }
    OG[e].erase(y);
    G[x].insert(e);
    OG[e].insert(x);
  }
  G[y].clear();
  for (auto &e : OG[y]) {
    if (OG[e].find(x) != OG[e].end()) {
      v.emplace_back(e);
    }
    G[e].erase(y);
    OG[x].insert(e);
    G[e].insert(x);
  }
  OG[y].clear();
  for (auto &e : v) {
    int z = findset(e); x = findset(x);
    if (z != x) solve(x, z);
  }
}
int main() {
  n = getint(); q = getint();
  rep(i, n) par[i] = i, sz[i] = 1, s[i].insert(i);
  rep(qq, q) {
    int x = getint() - 1, y = getint() - 1;
    int wx = findset(x), wy = findset(y);
    if (wx == wy) {
      printf("%lld\n", res);
      continue;
    }
    if (G[wy].find(wx) != G[wy].end()) {
      solve(wx, wy);
      printf("%lld\n", res);
      continue;
    }
    if (g[x].find(wy) != g[x].end()) {
      printf("%lld\n", res);
      continue;
    }
    G[wx].insert(wy);
    OG[wy].insert(wx);
    g[x].insert(wy);
    og[wy].insert(x);
    res += sz[wy];
    printf("%lld\n", res);
  }
  return 0;
}

C

真是一道神仙题，感觉是非容斥题里面非常难的一种题了。

步骤：

1.1.考虑问题的本质。

2.2.属于先确定一些，别的到时候再确定的dp。

https://blog.csdn.net/qq_39972971/article/details/105074251

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define MOD 1000000007
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();	
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
//ruogu_alter
const int mod = MOD;
const int inv2 = (mod + 1) / 2;
const int N = 605;
bool a[N];
int n, c[N][N], g[N][N], f[N << 1][N];
//
void reduce(int &x) { x += x >> 31 & mod; }
int mul(int x, int y) { return 1ll * x * y % mod; }
int main() {
  n = getint(); 
  for (int i = 1; i <= n; i++) a[getint()] = true;
  rep(i, n + 1) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      reduce(c[i][j] += c[i - 1][j - 1] - mod);
      reduce(c[i][j] += c[i - 1][j] - mod);
    }
  }
  g[0][0] = 1;
  for (int i = 1; i <= n; i++) rep(j, i + 1) {
    g[i][j] = g[i - 1][j];
    if (j) reduce(g[i][j] += mul(2 * j, g[i - 1][j - 1]) - mod);
    if (j > 1) reduce(g[i][j] += mul(j * (j - 1), g[i - 1][j - 2]) - mod);
  }
  f[2 * n + 1][0] = 1;
  int cx = 0, cy = 0;
  for (int i = 2 * n; i >= 1; i--) {
    if (a[i]) {
      ++cx;
      rep(j, cx + 1) {
        f[i][j] = f[i + 1][j];
        for (int k = 1; k <= j; k++) {
          reduce(f[i][j] += mul(mul(g[k - 1][k - 1], f[i + 1][j - k]), mul(k + 1, c[cx - 1 - (j - k)][k - 1])) - mod);
        }
      }
    }
    else {
      rep(j, cx + 1) f[i][j] = mul(f[i + 1][j], j - cy);
      ++cy;
    }
  }
  rep(i, n) f[1][n] = mul(f[1][n], inv2);
  cout << f[1][n] << endl;
  return 0;
}

Day 3

三题都不会，0+0+150+0+15。

绝大多数人秒了AA。sddz们都会CC。

A

先建笛卡尔树，然后线段树合并就行了。

我真tm弱。赛后告诉我建笛卡尔树就有点会了。

黑色部分最短的当做根。dpi,jdp_{i,j}表示树上第ii个节点，子树中黑色部分高度最小的点是jj的最优答案。

线段树合并就完了。

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define MOD 1000000007
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();	
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
//ruogu_alter
#define merge mer
const int N = 2e5 + 5;
int n, rt[N], cnt, a[N], m, ls[40 * N], rs[40 * N];
ll res, dat[40 * N], tag[40 * N];
bool fg[N];
int g[2][N];
vector<pii> v[N];
//
void doit(int k, ll v) {
  if (k) dat[k] += v, tag[k] += v;
}
void pd(int k) {
  if (tag[k]) {
    doit(ls[k], tag[k]);
    doit(rs[k], tag[k]);
    tag[k] = 0;
  }
}
int merge(int x, int y, int l, int r) {
  if (!x || !y) return x + y;
  if (r - l == 1) {
    dat[x] = max(dat[x], dat[y]);
    return x;
  }
  pd(x); pd(y);
  int mid = (l + r) >> 1;
  rs[x] = merge(rs[x], rs[y], mid, r);
  ls[x] = merge(ls[x], ls[y], l, mid);
  dat[x] = max(dat[ls[x]], dat[rs[x]]);
  return x;
}
ll qry(int now, int l, int r, int x, int y) {
  if (!now || l >= y || x >= r) return 0;
  if (x <= l && r <= y) return dat[now];
  int mid = (l + r) >> 1; pd(now);
  return max(qry(ls[now], l, mid, x, y), qry(rs[now], mid, r, x, y));
}
void upd(int &now, int l, int r, int p, ll v) {
  if (!now) now = ++cnt;
  if (r - l == 1) {
    dat[now] = max(dat[now], v);
    return;
  }
  int mid = (l + r) >> 1; pd(now);
  if (p < mid) upd(ls[now], l, mid, p, v);
  else upd(rs[now], mid, r, p, v);
  dat[now] = max(dat[ls[now]], dat[rs[now]]);
}
void dfs(int x) {
  if (g[0][x] >= 0) dfs(g[0][x]);
  if (g[1][x] >= 0) dfs(g[1][x]);
  if (g[0][x] >= 0 && g[1][x] >= 0) {
    ll ansl = qry(rt[g[0][x]], 0, n, a[x], n);
    ll ansr = qry(rt[g[1][x]], 0, n, a[x], n);
    doit(rt[g[0][x]], ansr); doit(rt[g[1][x]], ansl);
  }
  if (g[0][x] >= 0) rt[x] = rt[g[0][x]];
  if (g[1][x] >= 0) rt[x] = merge(rt[x], rt[g[1][x]], 0, n);
  ll ans = qry(rt[x], 0, n, a[x], n);
  for (pii u : v[x]) {
    upd(rt[x], 0, n, u.first, ans + u.second);
  }
}
int main() {
  n = getint();
  rep(i, n) a[i] = n - getint();
  m = getint();
  rep(i, m) {
    int x = getint() - 1, y = n - getint(), z = getint();
    v[x].emplace_back(y, z);
    res += z;
  }
  vector<int> st;
  memset(g, -1, sizeof(g));
  rep(i, n) {
    int now = st.size();
    while (now && a[st[now - 1]] > a[i]) --now;
    if (now) g[1][st[now - 1]] = i;
    if (now < st.size()) g[0][i] = st[now];
    for (int j = st.size(); j > now; --j) st.pop_back();
    st.emplace_back(i);
  }
  int s = -1;
  rep(i, n) rep(j, 2) if (g[j][i] >= 0) fg[g[j][i]] = true;
  rep(i, n) if (!fg[i]) {
    s = i;
    break;
  }
  dfs(s);
  printf("%lld\n", res - dat[rt[s]]);
  return 0;
}

B

还不很会。讲一讲看别人题解的大体思路。

https://blog.csdn.net/qq_39972971/article/details/105100433

先把这玩意建成基环森林，按找谁摘了苹果后，下一个摘这个苹果的人是谁。

然后树上的可以离线线段树。就dfndfn在一个区间里，出现时间小于等于一个数的苹果数，就是个二维偏序。

环上的也许也可以类似处理，感觉就是很麻烦。

C

前1515分so easy。

如果一个点度数是33很好，就把往根的路径和别的路径区分开就行。

一条链不舒服。

构造串100110100110，保证走三步以后能确定方向回到原点。

据说不是很好写。

这样的题竟然可以构造。。好妙。

Day 4

31+0+031+0+0。AA写了假做法。三题都不会。

A

tmd为什么我写了并查集！！！明明全图都是单向边！

我的图论那么差吗！

方法11：考虑把一个颜色的虚树建出来。那么要向中间那些点连单向边。就有强连通分量+倍增建边什么的了。

方法2：考虑如果钦定一个点为根必须选，那么一个点选了，他父亲一定选。所以直接考虑点分，点分中心选不选。

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define MOD 1000000007
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();	
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
//ruogu_alter
const int N = 4e5 + 5;
int n, k, a[N], cnt, c[N], res = INF, sz[N], vis[N], par[N];
vector<int> g[N], v[N];
bool is_centroid[N];
//
void init(int x, int p) {
  sz[x] = 1; 
  for (int to : g[x]) if (to != p && !is_centroid[to]) {
    init(to, x);
    sz[x] += sz[to];
  }
}
pii get_centroid(int x, int p, int tot) {
  pii res = mp(INF, -1);
  int ans = 0;
  for (int to : g[x]) if (to != p && !is_centroid[to]) {
    res = min(res, get_centroid(to, x, tot));
    ans = max(ans, sz[to]);
  }
  ans = max(ans, tot - sz[x]);
  return min(res, mp(ans, x));
}
void dfs(int x, int p) {
  par[x] = p; 
  if (vis[a[x]] != cnt) {
    vis[a[x]] = cnt;
    c[a[x]] = 1;
  }
  else ++c[a[x]];
  for (int to : g[x]) if (to != p && !is_centroid[to]) {
    dfs(to, x);
  }
}
void work(int x) {
  init(x, -1);
  int s = get_centroid(x, -1, sz[x]).second;
  is_centroid[s] = true;
  for (int to : g[s]) if (!is_centroid[to]) work(to);
  is_centroid[s] = false; ++cnt;
  dfs(s, -1);
  int ans = 0, st = 0; vector<int> qu;
  qu.emplace_back(a[s] + n); ++cnt; vis[a[s] + n] = cnt;
  while (st < qu.size()) {
    int u = qu[st++];
    if (u >= n) {
      u -= n; ++ans;
      if (c[u] != v[u].size()) return;
      for (int x : v[u]) if (vis[x] != cnt) qu.emplace_back(x);
    }
    else {
      if (par[u] >= 0 && vis[a[par[u]] + n] != cnt) {
        vis[a[par[u]] + n] = cnt;
        qu.emplace_back(a[par[u]] + n);
      }
    }
  }
  res = min(res, ans);
}
int main() {
  n = getint(); k = getint();
  rep(i, n - 1) {
    int x = getint() - 1, y = getint() - 1;
    g[x].emplace_back(y);
    g[y].emplace_back(x);
  }
  rep(i, n) {
    a[i] = getint() - 1;
    v[a[i]].emplace_back(i);
  }
  work(0);
  cout << res - 1 << endl;
  return 0;
}

B

提答，压根没看。

C

赛场上没看。

赛后看了题解，感觉这题就和noi2019d2t1好像。那题我现场很容易的过了（90min90min对拍完了）。这题却毫无思路。

真的挺秒的，不是按时间升序建边，而是按照从左到右覆盖建边的。

可以看一下zhouyuyang的博客。

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define MOD 1000000007
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();	
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
//ruogu_alter
const int N = 1e5 + 5;
const ll inf = 2e18;
struct node {
  int t, l, r, v;
  bool operator < (const node &b) { return t < b.t; }
  void read() { 
    t = getint(); l = getint(); r = getint(); v = getint(); 
  }
} a[N];
int n, m;
ll dis[N];
#define pli pair<ll, int>
priority_queue<pli, vector<pli>, greater<pli>> pq;
//
struct SG {
set<pii> dat[N << 2];
void modify(int l, int r, int p, int k, pii u) {
  dat[k].insert(u);   
  if (r - l == 1) return;
  int mid = (l + r) >> 1;
  if (p < mid) modify(l, mid, p, 2 * k + 1, u);
  else modify(mid, r, p, 2 * k + 2, u);
}
void qry(int l, int r, int x, int y, int k, int t, ll v) {
  if (l >= y || x >= r) return;
  if (x <= l && r <= y) {
    while (dat[k].size() && dat[k].begin() -> first <= t) {
      int x = dat[k].begin() -> second;
      if (v + a[x].v < dis[x]) {
        dis[x] = v + a[x].v;
        pq.emplace(dis[x], x);
      }
      dat[k].erase(dat[k].begin());
    }
    return;
  }
  int mid = (l + r) >> 1;
  qry(l, mid, x, y, 2 * k + 1, t, v);
  qry(mid, r, x, y, 2 * k + 2, t, v);
} 
} sg[2];
int main() {
  n = getint(); m = getint();
  rep(i, m) a[i].read();
  sort(a, a + m);
  rep(i, m) {
    dis[i] = inf;
    if (a[i].l == 1) {
      dis[i] = a[i].v;
      pq.emplace(dis[i], i);
    }
  }
  rep(i, m) {
    sg[0].modify(0, m, i, 0, mp(a[i].l - a[i].t - 1, i));
    sg[1].modify(0, m, i, 0, mp(a[i].l + a[i].t - 1, i));
  }
  while (pq.size()) {
    pii u = pq.top(); pq.pop();
    if (u.first > dis[u.second]) continue;
    int x = u.second; 
    sg[0].qry(0, m, 0, x, 0, a[x].r - a[x].t, dis[x]);
    sg[1].qry(0, m, x + 1, m, 0, a[x].r + a[x].t, dis[x]);
  }
  ll res = inf;
  rep(i, m) if (a[i].r == n) res = min(res, dis[i]);
  if (res == inf) res = -1;
  cout << res << endl;
  return 0;
}

总结

感觉一天一题才有希望进省队啊。

但我还差一些，但是也不是太多。

总体而言，打的非常差。

文章作者: ruogu
文章链接: http://ruogu-alter.github.io/2020/03/31/JOISC2020/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ruogu's blog！
总结
评论
簡