30pts? 100pts?
查看原帖
30pts? 100pts?
765958
lottle1212楼主2024/10/17 19:28

一份是一年前的代码 100pts,现在只有 30pts?

但是两份代码有什么区别!?

100pts

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> pii;
struct range { int x, y; } a[N], b[N];
int res1[N], res2[N], n;
bool cmp(const range& a, const range& b) { return a.x < b.x; }
void calc(range* t, int m, int* res) {
  priority_queue<pii, vector<pii>, greater<pii> > lq;
  priority_queue<int, vector<int>, greater<int> > wq;
  for (int i = 1; i <= n; ++ i) wq.push(i);
  for (int i = 1; i <= m; ++ i) {
    while (!lq.empty() && t[i].x >= lq.top().first) { wq.push(lq.top().second); lq.pop(); }
    if (wq.empty()) continue;
    int dest = wq.top();
    wq.pop(), ++ res[dest], lq.push(make_pair(t[i].y, dest));
  }
  for (int i = 1; i <= n; ++ i) res[i] += res[i - 1];
}
signed main() {
  int m1, m2;
  cin >> n >> m1 >> m2;
  for (int i = 1; i <= m1; ++ i) cin >> a[i].x >> a[i].y;
  for (int i = 1; i <= m2; ++ i) cin >> b[i].x >> b[i].y;
  sort(a + 1, a + m1 + 1, cmp);
  sort(b + 1, b + m2 + 1, cmp);
  calc(a, m1, res1);
  calc(b, m2, res2);
  int ans = 0;
  for (int i = 0; i <= n; ++ i) ans = max(ans, res1[i] + res2[n - i]);
  cout << ans << endl;
  return 0;
}

30pts

#include <iostream>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <bitset>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define fst first
#define scd second
#define db double
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector <int>
#define pii pair <int, int>
#define sz(x) ((int)x.size())
#define ms(f, x) memset(f, x, sizeof(f))
#define L(i, j, k) for (int i=(j); i<=(k); ++i)
#define R(i, j, k) for (int i=(j); i>=(k); --i)
#define ACN(i, H_u) for (int i=H_u; i; i=E[i].nxt)
using namespace std;
template <typename INT> void rd(INT &res) {
	res=0; bool f=false; char ch=getchar();
	while (ch<'0'||ch>'9') f|=ch=='-', ch=getchar();
	while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48), ch=getchar();
	res=(f?-res:res);
}
template <typename INT, typename...Args>
void rd(INT &x, Args &...y) { rd(x), rd(y...); }
//dfs
const int maxn=1e5;
const int N=maxn+10;
int a1[N], b1[N], a2[N], b2[N], f1[N], f2[N], n, m1, m2; priority_queue<int, vector <int>, greater <int> > ava; priority_queue <pii, vector <pii>, greater <pii> > una;
//wmr
struct node { int l, r; bool operator < (const node &k) const { return l<k.l; } } p1[N], p2[N];
//incra
void calc(node p[], int m, int f[]) {
	sort(p+1, p+m+1);
	L(i, 1, n) ava.push(i);
	L(i, 1, m) {
		while (!una.empty()&&una.top().fst<=p[i].l) ava.push(una.top().scd), una.pop();
		if (!ava.empty()) ++f[ava.top()], una.push(mp(p[i].r, ava.top())), ava.pop();
	}
	L(i, 1, n) f[i]+=f[i-1];
}
//lottle
signed main() {
//	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	// freopen("P7913.in", "r", stdin);
	// freopen("P7913.out", "w", stdout);
	rd(n, m1, m2);
	L(i, 1, m1) rd(p1[i].l, p1[i].r);
	L(i, 1, m2) rd(p2[i].l, p2[i].r);
	calc(p1, m1, f1); calc(p2, m2, f2);
	int ans=0;
	L(i, 0, n) ans=max(ans, f1[i]+f2[n-i]);
	printf("%d\n", ans);
	return 0;
}
/*
input
3 5 4
1 5
3 8
6 10
9 14
13 18
2 11
4 15
7 17
12 16
output
7
*/
2024/10/17 19:28
加载中...