比赛的时候用treap写，挂成傻逼了！
赛后据说set可以过。。。然后开始了我的挂弱b血泪史！TMD！！
今天又敲了一遍，发现错在一个很很很2的地方！！！！
View Code
#include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <cstring> #include <algorithm> #include <string> #include <set> #include <ctime> #include <queue> #include <map> #include <sstream> #include <stack> #define CL(arr, val) memset(arr, val, sizeof(arr)) #define REP(i, n) for((i) = 0; (i) < (n); ++(i)) #define FOR(i, l, h) for((i) = (l); (i) <= (h); ++(i)) #define FORD(i, h, l) for((i) = (h); (i) >= (l); --(i)) #define L(x) (x) << 1 #define R(x) (x) << 1 | 1 #define MID(l, r) (l + r) >> 1 #define Min(x, y) x < y ? x : y #define Max(x, y) x < y ? y : x #define E(x) (1 << (x)) const int eps = 1e-6; const int inf = ~0u>>2; typedef long long LL; using namespace std; const int N = 100010; set<int> st; int num[N]; int main() { //freopen("data.in", "r", stdin); int t, n, k, cas = 0; int a, b, d; LL ans, p, np, l, r; scanf("%d", &t); while(t--) { scanf("%d%d", &n, &k); st.clear(); st.insert(0); CL(num, 0); p = 0; ans = 0; while(k--) { scanf("%d", &a); if(a == 0) { scanf("%d", &b); num[b]++; st.insert(b); } else { if(num[p]) {num[p]--; continue;} set<int>::iterator it1, it2; it1 = it2 = st.find(p); l = r = -1; if(it1 != st.begin()) l = *--it1; if(++it2 != st.end()) r = *it2; //printf("%lld %lld\n", l, r); if(l == -1 && r == -1) {continue;} if(l == -1) { ans += r - p; d = 1; np = r; num[r]--; } else if(r == -1) { ans += p - l; d = 0; np = l; num[l]--; } else { if(r - p == p - l) { ans += r - p; if(d == 1) {np = r; num[r]--;} else {np = l; num[l]--;} } else if(r - p > p - l) { ans += p - l; np = l; d = 0; num[l]--; } else { ans += r - p; np = r; d = 1; num[r]--; } } st.erase(p); p = np; } } printf("Case %d: ", ++cas); cout << ans << endl; } return 0; }
线段树
View Code
#include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <cstring> #include <algorithm> #include <string> #include <set> #include <ctime> #include <queue> #include <map> #include <sstream> #include <stack> #define CL(arr, val) memset(arr, val, sizeof(arr)) #define REP(i, n) for((i) = 0; (i) < (n); ++(i)) #define FOR(i, l, h) for((i) = (l); (i) <= (h); ++(i)) #define FORD(i, h, l) for((i) = (h); (i) >= (l); --(i)) #define L(x) (x) << 1 #define R(x) (x) << 1 | 1 #define MID(l, r) (l + r) >> 1 #define Min(x, y) x < y ? x : y #define Max(x, y) x < y ? y : x #define E(x) (1 << (x)) const int eps = 1e-6; const int inf = ~0u>>2;; typedef long long LL; using namespace std; const int N = 100020; struct node { int l, r; int col, Max, Min; } tree[N<<2]; void creat(int t, int l, int r) { tree[t].l = l; tree[t].r = r; tree[t].col = 0; tree[t].Max = -inf; tree[t].Min = inf; if(l == r) return ; int mid = MID(l, r); creat(L(t), l, mid); creat(R(t), mid + 1, r); } void updata(int t, int p, int val) { if(tree[t].l == tree[t].r) { tree[t].col += val; if(tree[t].col) {tree[t].Max = tree[t].Min = p;} else {tree[t].Max = -inf; tree[t].Min = inf;} return ; } int mid = MID(tree[t].l, tree[t].r); if(p <= mid) updata(L(t), p, val); else updata(R(t), p, val); tree[t].Max = max(tree[L(t)].Max, tree[R(t)].Max); tree[t].Min = min(tree[L(t)].Min, tree[R(t)].Min); } int get_max(int t, int l, int r) { if(tree[t].l >= l && tree[t].r <= r) { return tree[t].Max; } int mid = MID(tree[t].l, tree[t].r); if(l > mid) return get_max(R(t), l, r); else if(r <= mid) return get_max(L(t), l, r); else { return max(get_max(L(t), l, mid), get_max(R(t), mid + 1, r)); } } int get_min(int t, int l, int r) { if(tree[t].l >= l && tree[t].r <= r) { return tree[t].Min; } int mid = MID(tree[t].l, tree[t].r); if(l > mid) return get_min(R(t), l, r); else if(r <= mid) return get_min(L(t), l, r); else { return min(get_min(L(t), l, mid), get_min(R(t), mid + 1, r)); } } int main() { //freopen("data.in", "r", stdin); int t, n, m, cas = 0;; int p, np, l, r, d, a, b; LL ans; scanf("%d", &t); while(t--) { scanf("%d%d", &n, &m); p = ans = 0; d = 1; creat(1, 0, n + 1); while(m--) { scanf("%d", &a); if(a == 0) { scanf("%d", &b); updata(1, b, 1); } else { l = get_max(1, 0, p); r = get_min(1, p, n); //printf("%d %d\n", l, r); if(l <= -inf && r >= inf) continue; else if(l <= -inf) { ans += r - p; np = r; d = 1; } else if(r >= inf) { ans += p - l; np = l; d = 0; } else { if(r - p == p - l) { ans += r - p; if(d == 1) np = r; else np = l; } else if(r - p > p - l) { ans += p - l; d = 0; np = l; } else { ans += r - p; d = 1; np = r; } } updata(1, np, -1); p = np; } } printf("Case %d: ", ++cas); cout << ans << endl; } return 0; }