Submission #16031

#	Time	Username	Problem	Language	Result	Execution time	Memory
16031		jihoon	수족관 1 (KOI13_aqua1)	C++98	42 / 100	4 ms	1416 KiB

aqua1

#include<cstdio>
#include<algorithm>
#include<map>
#define base 8192
#define MAX_N 5001
using namespace std;
pair<int,int> su;
map<int,int> wichi;
int n,m,k,head;
int sum=0;
int idxtree[base*2]={0};
class badak{
public:
    int from,to,deep;
}info[MAX_N];
class TR{
public:
    int parent,child[2],value;
}tree[MAX_N];

int fndmax(int ss,int ee){
    ss+=base;
    ee+=base;
    bool first=true;
    int res=-1;
    while(1){
        if(ss%2){
            if(first){
                res=idxtree[ss];
                first=false;
            }else{
                if(info[res].deep>info[idxtree[ss]].deep){
                    res=idxtree[ss];
                }
            }
            ss++;
        }
        if(ee%2==0){
            if(first){
                res=idxtree[ee];
                first=false;
            }else{
                if(info[res].deep>info[idxtree[ee]].deep){
                    res=idxtree[ss];
                }
            }
            ee--;
        }
        if(ss>ee) break;
        ss/=2;ee/=2;
    }
    return res;
}

void doidx(int ss,int ee){
    int i;
    while(1){
        if(ss%2){
            idxtree[ss/2]=idxtree[ss];
            ss++;
        }
        if(ee%2==0){
            idxtree[ee/2]=idxtree[ee];
            ee--;
        }
        if(ss>ee) break;
        for(i=ss;i<=ee;i+=2){
            if(info[idxtree[i]].deep<info[idxtree[i+1]].deep){
                idxtree[i/2]=idxtree[i];
            }else{
                idxtree[i/2]=idxtree[i+1];
            }
        }
        ss/=2;ee/=2;
    }
}

void mktree(int parent,int ss,int ee){
    int willhead;
    if(ss>ee) return;
    willhead=fndmax(ss,ee);
    if(parent>=0){
        tree[parent].child[(parent<ss)]=willhead;
        tree[willhead].value=(info[willhead].deep-info[parent].deep)*(info[ee].to-info[ss].from);
    }else{
        head=willhead;
        tree[willhead].value=(info[ee].to-info[ss].from)*info[willhead].deep;
    }
    tree[willhead].parent=parent;
    tree[willhead].child[0]=-1;
    tree[willhead].child[1]=-1;
    mktree(willhead,ss,willhead-1);
    mktree(willhead,willhead+1,ee);
}

int main(){
    int i,ii,ia,ib,ic,id;
    int cnt=0;
    scanf("%d",&n);
    m=(n-2)/2;
    scanf("%d %d",&ia,&ib);
    for(i=0;i<m;i++){
        scanf("%d %d",&ia,&ib);
        scanf("%d %d",&ic,&id);
        info[i].from=ia;
        info[i].to=ic;
        info[i].deep=ib;
        wichi[ia]=i;
        idxtree[base+i]=i;
    }
    scanf("%d %d",&ia,&ib);
    doidx(base,base+m-1);
    mktree(-1,0,m-1);
    for(i=0;i<m;i++){
        sum+=tree[i].value;
    }
    scanf("%d",&k);
    for(i=0;i<k;i++){
        scanf("%d %d %d %d",&ia,&ib,&ic,&id);
        ii=wichi[ia];
        while(ii>-1){
            sum-=tree[ii].value;
            tree[ii].value=0;
            ii=tree[ii].parent;
        }
    }
    printf("%d",sum);
}

• Subtask 1: 23 / 23
• Subtask 2: 19 / 19
• Subtask 3: 0 / 22
• Subtask 4: 0 / 36