zoj1391.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include <algorithm>
using namespace std;

const int MAXN = 8010;

struct Line{
    int x, y1, y2;
    bool operator < (const Line &b) const { return x < b.x; }
} l[MAXN];

int n;
int s[MAXN], p[MAXN];
int st[MAXN], ed[MAXN], e[500000];
bool mk[MAXN];

void init(){
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%d %d %d", &l[i].y1, &l[i].y2, &l[i].x);
    }
    sort(l, l + n);
    memset(s, 0xff, sizeof(s));
    memset(p, 0xff, sizeof(p));
    memset(st, 0, sizeof(st));
    memset(e, 0, sizeof(e));
}

void solve(){
    int ans = 0;
    for (int k = 0; k < n; k++){
        int a = l[k].y1, b = l[k].y2;  
        memset(mk, 0, sizeof(mk));
        for (int i = a; i < b; i++){
            if (s[i] != -1) mk[s[i]] = 1;
            if (p[i] != -1) mk[p[i]] = 1;
            s[i] = k; p[i] = k;
        }
        if (p[b] != -1) mk[p[b]] = 1; p[b] = k;
        if (k > 0) st[k] = ed[k] = ed[k-1];
        for (int i = 0; i < k; i++) if (mk[i])
            e[ed[k]++] = i;
        for (int i = st[k]; i < ed[k]; i++)
            for (int j = st[e[i]]; j < ed[e[i]]; j++)
                if (mk[e[j]]) ans++; 
    }   
    printf("%d\n", ans);
}

int main(){
    int cases;  scanf("%d", &cases);
    while (cases--){
        init();
        solve();   
    }
    return 0;   
}