oj.uz

Submission #16256

# Submission time Handle Problem Language Result Execution time Memory
16256 2015-08-19T02:34:55 Z CodingBug Wall (IOI14_wall) C++
100 / 100
 1254 ms 141720 KB 
#include "wall.h"
#include <algorithm>
#include <stdio.h>
using namespace std;
struct Node{
    int mn,mx;
    Node *chi[2];
};

Node *r;

void updateTree(int s,int e,Node *no,int ss,int ee,int k,bool m){
    if(ss<=s && e<=ee){
        if(m){
            no->mx=min(no->mx,k);
            no->mn=min(no->mn,no->mx);
        }
        else{
            no->mn=max(no->mn,k);
            no->mx=max(no->mx,no->mn);
        }
        return;
    }
    if(e<ss || ee<s) return;
    int mid=(s+e)/2;
    if(no->chi[0]==NULL) no->chi[0]=new Node();
    if(no->chi[1]==NULL) no->chi[1]=new Node();
    for(int i=0;i<2;i++){
        no->chi[i]->mn=max(min(no->chi[i]->mn,no->mx),no->mn);
        no->chi[i]->mx=min(max(no->chi[i]->mx,no->mn),no->mx);
    }
    updateTree(s,mid,no->chi[0],ss,ee,k,m);
    updateTree(mid+1,e,no->chi[1],ss,ee,k,m);
    no->mn=min(no->chi[0]->mn,no->chi[1]->mn);
    no->mx=max(no->chi[0]->mx,no->chi[1]->mx);
}

void getTree(int s,int e,Node *no,int finalHeight[]){
    if(s==e){
        finalHeight[s]=no->mn;
        return;
    }
    int mid=(s+e)/2;
    if(no->chi[0]==NULL) no->chi[0]=new Node();
    if(no->chi[1]==NULL) no->chi[1]=new Node();
    for(int i=0;i<2;i++){
        no->chi[i]->mn=max(min(no->chi[i]->mn,no->mx),no->mn);
        no->chi[i]->mx=min(max(no->chi[i]->mx,no->mn),no->mx);
    }
    getTree(s,mid,no->chi[0],finalHeight);
    getTree(mid+1,e,no->chi[1],finalHeight);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    int i;
    r=new Node();
    for(i=0;i<k;i++){
        updateTree(0,n-1,r,left[i],right[i],height[i],op[i]-1);
    }
    getTree(0,n-1,r,finalHeight);
    return;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 126 ms 9032 KB Output is correct
3 Correct 256 ms 5644 KB Output is correct
4 Correct 768 ms 15628 KB Output is correct
5 Correct 487 ms 15628 KB Output is correct
6 Correct 482 ms 15628 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 1 ms 1208 KB Output is correct
3 Correct 0 ms 1208 KB Output is correct
4 Correct 7 ms 1868 KB Output is correct
5 Correct 6 ms 1868 KB Output is correct
6 Correct 7 ms 1868 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 148 ms 9032 KB Output is correct
9 Correct 280 ms 5644 KB Output is correct
10 Correct 827 ms 15628 KB Output is correct
11 Correct 548 ms 15628 KB Output is correct
12 Correct 494 ms 15628 KB Output is correct
13 Correct 0 ms 1208 KB Output is correct
14 Correct 187 ms 9032 KB Output is correct
15 Correct 43 ms 2748 KB Output is correct
16 Correct 879 ms 15628 KB Output is correct
17 Correct 406 ms 15628 KB Output is correct
18 Correct 487 ms 15628 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1208 KB Output is correct
3 Correct 0 ms 1208 KB Output is correct
4 Correct 9 ms 1868 KB Output is correct
5 Correct 8 ms 1868 KB Output is correct
6 Correct 6 ms 1868 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 192 ms 9032 KB Output is correct
9 Correct 277 ms 5644 KB Output is correct
10 Correct 772 ms 15628 KB Output is correct
11 Correct 512 ms 15628 KB Output is correct
12 Correct 534 ms 15628 KB Output is correct
13 Correct 0 ms 1208 KB Output is correct
14 Correct 178 ms 9032 KB Output is correct
15 Correct 39 ms 2748 KB Output is correct
16 Correct 928 ms 15628 KB Output is correct
17 Correct 468 ms 15628 KB Output is correct
18 Correct 484 ms 15628 KB Output is correct
19 Correct 1216 ms 141720 KB Output is correct
20 Correct 1233 ms 141720 KB Output is correct
21 Correct 1145 ms 141720 KB Output is correct
22 Correct 1227 ms 141720 KB Output is correct
23 Correct 1162 ms 141720 KB Output is correct
24 Correct 1254 ms 141720 KB Output is correct
25 Correct 1237 ms 141720 KB Output is correct
26 Correct 1221 ms 141720 KB Output is correct
27 Correct 1215 ms 141720 KB Output is correct
28 Correct 1132 ms 141720 KB Output is correct
29 Correct 1215 ms 141720 KB Output is correct
30 Correct 1229 ms 141720 KB Output is correct