oj.uz

Submission #109042

# Submission time Handle Problem Language Result Execution time Memory
109042 2019-05-04T05:53:01 Z dantoh000 Wall (IOI14_wall) C++14
100 / 100
 1668 ms 214156 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 (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 = flag = 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{
            if (flag) 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{
            if (flag) 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:39: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:55: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 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 13 ms 1632 KB Output is correct
6 Correct 9 ms 1536 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 158 ms 8376 KB Output is correct
3 Correct 226 ms 5496 KB Output is correct
4 Correct 1140 ms 18424 KB Output is correct
5 Correct 310 ms 18808 KB Output is correct
6 Correct 257 ms 18936 KB Output is correct

Subtask #3
29.0 / 29.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 16 ms 1436 KB Output is correct
5 Correct 9 ms 1536 KB Output is correct
6 Correct 13 ms 1536 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 152 ms 8224 KB Output is correct
9 Correct 262 ms 5624 KB Output is correct
10 Correct 1202 ms 18296 KB Output is correct
11 Correct 315 ms 18808 KB Output is correct
12 Correct 253 ms 18792 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 147 ms 8384 KB Output is correct
15 Correct 52 ms 2680 KB Output is correct
16 Correct 962 ms 18648 KB Output is correct
17 Correct 277 ms 18524 KB Output is correct
18 Correct 313 ms 18552 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 16 ms 1536 KB Output is correct
5 Correct 9 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 154 ms 8380 KB Output is correct
9 Correct 234 ms 5624 KB Output is correct
10 Correct 1020 ms 18272 KB Output is correct
11 Correct 262 ms 18808 KB Output is correct
12 Correct 255 ms 18832 KB Output is correct
13 Correct 3 ms 256 KB Output is correct
14 Correct 145 ms 8316 KB Output is correct
15 Correct 45 ms 2680 KB Output is correct
16 Correct 1035 ms 18552 KB Output is correct
17 Correct 273 ms 18552 KB Output is correct
18 Correct 293 ms 18656 KB Output is correct
19 Correct 1547 ms 214096 KB Output is correct
20 Correct 1391 ms 211440 KB Output is correct
21 Correct 1354 ms 213980 KB Output is correct
22 Correct 1310 ms 211660 KB Output is correct
23 Correct 1387 ms 211644 KB Output is correct
24 Correct 1385 ms 211756 KB Output is correct
25 Correct 1474 ms 211608 KB Output is correct
26 Correct 1668 ms 214156 KB Output is correct
27 Correct 1475 ms 214008 KB Output is correct
28 Correct 1420 ms 211576 KB Output is correct
29 Correct 1355 ms 211644 KB Output is correct
30 Correct 1474 ms 211588 KB Output is correct