(TIOJ) 1045 . A.細菌培養

http://tioj.ck.tp.edu.tw/problems/1045

這題出得還不錯！

一開始，想說對每個row，掃過已經有的node, 按照左界排序，認真維護需要的指數倍一番，複雜度O(10^4 n lg n) ，結果TLE！！！(時限卡超緊，只超過0.87ms)

之後，我想想，好想很多條row的結果是一樣的，於是優化一番(主要是球其中某一些的row記好 )，就OK了。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <assert.h>
#include <queue>
#include <vector>
using namespace std;

const int MAX_N = 203;
const int MAX_P = 10002;
long long int pow2[64];

struct Node {
    int l;
    int t;
    int r;
    int b;
} query[MAX_N];

struct NODE {
    int l;
    int r;
} node[MAX_P];

bool in(Node n1,int q) {
    if (n1.t<q && q<=n1.b) return true;
    else return false;
}

bool operator<(const NODE& n1, const NODE& n2) {
    return (n1.l<n2.l || n1.l==n2.l && n1.r<n2.r);
}

priority_queue<int, vector<int> , greater<int> > que;
vector<int> v;

long long int Find (int x,int n) {
    long long sum=0;
    int id=0;
    for (int y=0;n>y;y++) {       //篩選 
        if (in(query[y],x)) {
            node[id].l=query[y].l;
            node[id].r=query[y].r;
            id++;
        }
    }
    sort(node,node+id);
    int s=1;
    int num=0;  //指數倍 
    while (!que.empty()) que.pop();
    for (int y=0;id>y;y++) {
        int L=node[y].l;
        int R=node[y].r;
        if (que.empty()==true) {
            
            sum+=(L-1 - s + 1) * pow2[num];
            num++;
            s=L;
            que.push(R);
        }
        else {
            while (que.empty()==false && que.top()<L) {
                int t=que.top();
                sum+=(t - s + 1) * pow2[num];
                num--;
                s=t+1;
                que.pop();
            }
            sum += (L-1 - s + 1) * pow2[num];
            s=L;
            num++;
            que.push(R);        }
    }
    while (que.empty()==false) {
        int t=que.top();
        sum+= (t - s + 1) * pow2[num];
        num--;
        s=t+1;
        que.pop();
    }
    sum+= (10000 - s + 1) * pow2[num];
    return sum;
}

int main () {
    pow2[0]=1;
    int n;
    for (int x=1;200>x;x++) pow2[x]=pow2[x-1]*2;
    while (scanf("%d",&n) != EOF) {
        if (!n) return 0;
        v.clear();
        for (int x=0;n>x;x++) {
            scanf("%d %d %d %d",&query[x].l,&query[x].t,&query[x].r,&query[x].b);
            query[x].l++;
            if (query[x].t !=0)v.push_back(query[x].t);
            if (query[x].t > 1)v.push_back(query[x].t-1);
            if (query[x].t != 10000)v.push_back(query[x].t+1);
            if (query[x].b!=0)v.push_back(query[x].b);
            if (query[x].b != 10000)v.push_back(query[x].b+1);
            if (query[x].b > 1)v.push_back(query[x].b-1);
        }
        v.push_back(1);
        v.push_back(10000);
        sort(v.begin(),v.end());
        v.resize(unique(v.begin(),v.end()) - v.begin());
        int len=v.size();
        long long sum=0;
        long long ans[len];
        ans[0]=Find(v[0],n);
        sum=ans[0];
        for (int x=1;len>x;x++) {
            ans[x]=Find(v[x],n);
            if (ans[x]==ans[x-1]) {
                sum+=(v[x] - v[x-1]) * ans[x];
            }
            else {
                sum+=ans[x];
            }
        }
        
        
        printf("%lld\n",sum);
    }
    return 0;
}