oj.uz

Submission #109040

# Submission time Handle Problem Language Result Execution time Memory
109040 2019-05-04T05:47:17 Z dantoh000 Wall (IOI14_wall) C++14
100 / 100
 1879 ms 224560 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(){
        //printf("\t\tvalue %d %d %d %d %d\n",i,s,e,omin,omax);
        if (s != e){
            //printf("%d %d , ",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){
            //printf("range match %d %d, applying first\n",qs,qe);
            omin = min(omin,x);
            omax = min(omax,omin);
        }
        else{
           // printf("min %d %d %d %d %d\n",qs,qe,s,e,x);
            value();
            //printf("%d %d %d %d\n",qs,qe,s,e);
            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){
            //printf("range match %d %d, applying first\n",qs,qe);
            omax = max(x,omax);
            omin = max(omax,omin);
        }
        else{
            //printf("max %d %d %d %d %d\n",qs,qe,s,e,x);
            value();
            //printf("%d %d %d %d\n",qs,qe,s,e);
            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();
        //printf("query %d %d %d\n",s,e,x);
        if (s == e){
            //printf("qu %d %d %d\n",s,omin,omax);
            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++){
        //printf("\t\t\t%d update %d %d %d %d\n",i,op[i],left[i],right[i],height[i]);
        if (op[i] == 1){
            root->maxi(left[i],right[i],height[i]);
        }
        else{
            root ->mini(left[i],right[i],height[i]);
        }
    }
    //printf("updates over %d %d\n",ooo,oo);
    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:43: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:61: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 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 12 ms 1536 KB Output is correct
5 Correct 11 ms 1536 KB Output is correct
6 Correct 10 ms 1536 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 209 ms 8408 KB Output is correct
3 Correct 383 ms 5708 KB Output is correct
4 Correct 1153 ms 27928 KB Output is correct
5 Correct 553 ms 28900 KB Output is correct
6 Correct 477 ms 27464 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 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 16 ms 1548 KB Output is correct
5 Correct 13 ms 1536 KB Output is correct
6 Correct 11 ms 1536 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 194 ms 14104 KB Output is correct
9 Correct 269 ms 9336 KB Output is correct
10 Correct 1042 ms 27896 KB Output is correct
11 Correct 407 ms 28876 KB Output is correct
12 Correct 511 ms 27336 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 206 ms 13992 KB Output is correct
15 Correct 69 ms 3196 KB Output is correct
16 Correct 1044 ms 28080 KB Output is correct
17 Correct 438 ms 27608 KB Output is correct
18 Correct 470 ms 27600 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 13 ms 1536 KB Output is correct
5 Correct 10 ms 1536 KB Output is correct
6 Correct 12 ms 1536 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 215 ms 14060 KB Output is correct
9 Correct 298 ms 9396 KB Output is correct
10 Correct 1171 ms 27896 KB Output is correct
11 Correct 483 ms 29020 KB Output is correct
12 Correct 514 ms 27404 KB Output is correct
13 Correct 3 ms 388 KB Output is correct
14 Correct 177 ms 13928 KB Output is correct
15 Correct 52 ms 3192 KB Output is correct
16 Correct 1093 ms 28124 KB Output is correct
17 Correct 531 ms 27492 KB Output is correct
18 Correct 491 ms 27596 KB Output is correct
19 Correct 1826 ms 224372 KB Output is correct
20 Correct 1703 ms 221992 KB Output is correct
21 Correct 1689 ms 224460 KB Output is correct
22 Correct 1824 ms 222072 KB Output is correct
23 Correct 1704 ms 221992 KB Output is correct
24 Correct 1643 ms 221996 KB Output is correct
25 Correct 1731 ms 221972 KB Output is correct
26 Correct 1828 ms 224488 KB Output is correct
27 Correct 1863 ms 224560 KB Output is correct
28 Correct 1879 ms 221980 KB Output is correct
29 Correct 1802 ms 222072 KB Output is correct
30 Correct 1753 ms 222048 KB Output is correct