oj.uz

Submission #109041

# Submission time Handle Problem Language Result Execution time Memory
109041 2019-05-04T05:50:30 Z dantoh000 Wall (IOI14_wall) C++14
100 / 100
 1247 ms 214944 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
struct node{
    int s,e,m,omin,omax,flag;
    node *l, *r;
    node (int _s, int _e){
        s = _s, e = _e, m = (s+e)/2;
        omin = 100005, omax = 0, flag = 0;
        if (s != e){
            l = new node(s,m);
            r = new node(m+1,e);
        }
    }
    void value(){
        if (flag == 0) return;
        flag = 0;
        if (s != e){
            l->mini(s,m,omin);
            l->maxi(s,m,omax);
            r->mini(m+1,e,omin);
            r->maxi(m+1,e,omax);
            omax = 0, omin = 100005;
        }
    }
    int mini(int qs, int qe, int x){
        if (qs == s && qe == e){
            omin = min(omin,x);
            omax = min(omax,omin);
            flag = 1;
        }
        else{
            value();
            if (qe <= m) l->mini(qs,qe,x);
            else if (qs > m) r->mini(qs,qe,x);
            else{
                l->mini(qs,m,x);
                r->mini(m+1,qe,x);
            }
        }
    }
    int maxi(int qs, int qe, int x){
        if (qs == s && qe == e){
            omax = max(x,omax);
            omin = max(omax,omin);
            flag = 1;
        }
        else{
            value();
            if (qe <= m) l->maxi(qs,qe,x);
            else if (qs > m) r->maxi(qs,qe,x);
            else{
                l->maxi(qs,m,x);
                r->maxi(m+1,qe,x);
            }
        }
    }
    int qu(int x){
        value();
        if (s == e){
            return omax;
        }
        if (x <= m){
            return l->qu(x);
        }
        else return r->qu(x);
    }
} *root;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    root = new node(0,n-1);
    for (int i = 0; i < k; i++){
        if (op[i] == 1){
            root->maxi(left[i],right[i],height[i]);
        }
        else{
            root ->mini(left[i],right[i],height[i]);
        }
    }
    for (int i =0;  i < n; i++){
        finalHeight[i] = root->qu(i);
    }
    return;
}

Compilation message

wall.cpp: In member function 'int node::mini(int, int, int)':
wall.cpp:41:5: warning: no return statement in function returning non-void [-Wreturn-type]
     }
     ^
wall.cpp: In member function 'int node::maxi(int, int, int)':
wall.cpp:57:5: warning: no return statement in function returning non-void [-Wreturn-type]
     }
     ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 15 ms 1536 KB Output is correct
5 Correct 9 ms 1536 KB Output is correct
6 Correct 12 ms 1536 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 194 ms 9340 KB Output is correct
3 Correct 295 ms 6604 KB Output is correct
4 Correct 1075 ms 19188 KB Output is correct
5 Correct 308 ms 19964 KB Output is correct
6 Correct 298 ms 19832 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 12 ms 1664 KB Output is correct
5 Correct 12 ms 1536 KB Output is correct
6 Correct 9 ms 1536 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 151 ms 9208 KB Output is correct
9 Correct 281 ms 6520 KB Output is correct
10 Correct 923 ms 19320 KB Output is correct
11 Correct 275 ms 19832 KB Output is correct
12 Correct 251 ms 19832 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 151 ms 9208 KB Output is correct
15 Correct 45 ms 3320 KB Output is correct
16 Correct 1112 ms 19360 KB Output is correct
17 Correct 257 ms 19492 KB Output is correct
18 Correct 271 ms 19480 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 11 ms 1536 KB Output is correct
5 Correct 8 ms 1536 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 150 ms 9208 KB Output is correct
9 Correct 307 ms 6364 KB Output is correct
10 Correct 1125 ms 19184 KB Output is correct
11 Correct 261 ms 19576 KB Output is correct
12 Correct 258 ms 19684 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 167 ms 9208 KB Output is correct
15 Correct 48 ms 3192 KB Output is correct
16 Correct 1119 ms 19448 KB Output is correct
17 Correct 330 ms 19448 KB Output is correct
18 Correct 295 ms 19416 KB Output is correct
19 Correct 1027 ms 214904 KB Output is correct
20 Correct 1018 ms 212516 KB Output is correct
21 Correct 1195 ms 214944 KB Output is correct
22 Correct 1177 ms 212316 KB Output is correct
23 Correct 953 ms 212216 KB Output is correct
24 Correct 1059 ms 212304 KB Output is correct
25 Correct 1100 ms 212300 KB Output is correct
26 Correct 1247 ms 214460 KB Output is correct
27 Correct 976 ms 214392 KB Output is correct
28 Correct 1118 ms 211964 KB Output is correct
29 Correct 1034 ms 211880 KB Output is correct
30 Correct 1094 ms 211596 KB Output is correct