oj.uz

Submission #7547

# Submission time Handle Problem Language Result Execution time Memory
7547 2014-08-11T03:03:33 Z Namnamseo Wall (IOI14_wall) C++
0 / 100
 432 ms 205584 KB 
#include "wall.h"
#include <cstdio>

const int inf = 2147480000;

struct Node {
    int rangel,ranger;
    Node *lc, *rc;
    int minval,maxval;
    Node(int left,int right) {
        minval=0; maxval=inf;
        rangel = left; ranger = right;
        if(left==right) return;
        int mid = (left+right)>>1;
        lc = new Node(left,mid);
        rc = new Node(mid+1,right);
    }
    void applyRange(int nmin,int nmax){
        if(minval<nmin){
            minval = nmin;
            if(maxval<nmin) maxval=nmin;
        }
        if(nmax<maxval){
            maxval=nmax;
            if(nmax<minval) minval=nmax;
        }
    }
    void updateRange(int l,int r,int newmin,int newmax){
        if(l<=rangel && ranger <= r){
            applyRange(newmin,newmax);
        } else {
            if(r<rangel || ranger < l) return;
            lc->applyRange(minval,maxval);
            rc->applyRange(minval,maxval);
            minval=0; maxval=inf;
            lc->updateRange(l,r,newmin,newmax);
            rc->updateRange(l,r,newmin,newmax);
        }
    }
    int answer(int pos){
        if(pos==rangel && pos==ranger) return minval;
        int ret = ((pos<=((rangel+ranger)/2))?lc:rc)->answer(pos);
        if(ret<minval) return minval;
        if(maxval<ret) return maxval;
        return ret;
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    Node* root = new Node(0,2097151);
    int i;
    for(i=0;i<k;i++) {
        if(op[i]) root->updateRange(left[i],right[i],height[i],inf);
        else root->updateRange(left[i],right[i],0,height[i]);
    }
    for(i=0;i<n;i++){
        finalHeight[i]=root->answer(i);
    }
    return;
}

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 197760 KB Output is correct
2 Incorrect 144 ms 197892 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 197760 KB Output is correct
2 Incorrect 432 ms 205584 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 197760 KB Output is correct
2 Incorrect 164 ms 197892 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 197760 KB Output is correct
2 Incorrect 176 ms 197892 KB Output isn't correct
3 Halted 0 ms 0 KB -