oj.uz

Submission #16031

# Submission time Handle Problem Language Result Execution time Memory
16031 2015-08-09T21:54:57 Z jihoon 수족관 1 (KOI13_aqua1) C++
42 / 100
 4 ms 1416 KB 
#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.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1416 KB Output is correct
2 Correct 0 ms 1416 KB Output is correct
3 Correct 0 ms 1416 KB Output is correct
4 Correct 0 ms 1416 KB Output is correct
5 Correct 0 ms 1416 KB Output is correct
6 Correct 0 ms 1416 KB Output is correct
7 Correct 0 ms 1416 KB Output is correct
8 Correct 0 ms 1416 KB Output is correct
9 Correct 0 ms 1416 KB Output is correct
10 Correct 0 ms 1416 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1416 KB Output is correct
2 Correct 0 ms 1416 KB Output is correct
3 Correct 0 ms 1416 KB Output is correct
4 Correct 0 ms 1416 KB Output is correct
5 Correct 0 ms 1416 KB Output is correct
6 Correct 0 ms 1416 KB Output is correct
7 Correct 0 ms 1416 KB Output is correct
8 Correct 0 ms 1416 KB Output is correct
9 Correct 0 ms 1416 KB Output is correct
10 Correct 0 ms 1416 KB Output is correct

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1416 KB Output is correct
2 Correct 0 ms 1416 KB Output is correct
3 Incorrect 0 ms 1416 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1416 KB Output is correct
2 Correct 0 ms 1416 KB Output is correct
3 Incorrect 0 ms 1416 KB Output isn't correct
4 Halted 0 ms 0 KB -