oj.uz

Submission #7549

# Submission time Handle Problem Language Result Execution time Memory
7549 2014-08-11T03:08:24 Z Namnamseo Wall (IOI14_wall) C++
100 / 100
 1440 ms 213400 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) {
            maxval=0;
            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]==1) 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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 197760 KB Output is correct
2 Correct 148 ms 197892 KB Output is correct
3 Correct 180 ms 197760 KB Output is correct
4 Correct 188 ms 197892 KB Output is correct
5 Correct 228 ms 197892 KB Output is correct
6 Correct 164 ms 197892 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 197760 KB Output is correct
2 Correct 468 ms 205584 KB Output is correct
3 Correct 456 ms 201140 KB Output is correct
4 Correct 1028 ms 205976 KB Output is correct
5 Correct 568 ms 205976 KB Output is correct
6 Correct 548 ms 205976 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 197760 KB Output is correct
2 Correct 160 ms 197892 KB Output is correct
3 Correct 168 ms 197760 KB Output is correct
4 Correct 180 ms 197892 KB Output is correct
5 Correct 164 ms 197892 KB Output is correct
6 Correct 172 ms 197892 KB Output is correct
7 Correct 180 ms 197760 KB Output is correct
8 Correct 484 ms 205584 KB Output is correct
9 Correct 460 ms 201140 KB Output is correct
10 Correct 1040 ms 205976 KB Output is correct
11 Correct 560 ms 205976 KB Output is correct
12 Correct 564 ms 205976 KB Output is correct
13 Correct 192 ms 197760 KB Output is correct
14 Correct 452 ms 205584 KB Output is correct
15 Correct 240 ms 198244 KB Output is correct
16 Correct 1244 ms 205976 KB Output is correct
17 Correct 576 ms 205976 KB Output is correct
18 Correct 596 ms 205976 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 197760 KB Output is correct
2 Correct 164 ms 197892 KB Output is correct
3 Correct 172 ms 197760 KB Output is correct
4 Correct 180 ms 197892 KB Output is correct
5 Correct 164 ms 197892 KB Output is correct
6 Correct 184 ms 197892 KB Output is correct
7 Correct 164 ms 197760 KB Output is correct
8 Correct 464 ms 205584 KB Output is correct
9 Correct 460 ms 201140 KB Output is correct
10 Correct 1048 ms 205976 KB Output is correct
11 Correct 556 ms 205976 KB Output is correct
12 Correct 596 ms 205976 KB Output is correct
13 Correct 156 ms 197760 KB Output is correct
14 Correct 436 ms 205584 KB Output is correct
15 Correct 240 ms 198244 KB Output is correct
16 Correct 1228 ms 205976 KB Output is correct
17 Correct 572 ms 205976 KB Output is correct
18 Correct 556 ms 205976 KB Output is correct
19 Correct 1380 ms 213400 KB Output is correct
20 Correct 1376 ms 213400 KB Output is correct
21 Correct 1400 ms 213400 KB Output is correct
22 Correct 1424 ms 213400 KB Output is correct
23 Correct 1380 ms 213400 KB Output is correct
24 Correct 1416 ms 213400 KB Output is correct
25 Correct 1396 ms 213400 KB Output is correct
26 Correct 1364 ms 213400 KB Output is correct
27 Correct 1364 ms 213400 KB Output is correct
28 Correct 1440 ms 213400 KB Output is correct
29 Correct 1372 ms 213400 KB Output is correct
30 Correct 1416 ms 213400 KB Output is correct