oj.uz

Submission #109021

# Submission time Handle Problem Language Result Execution time Memory
109021 2019-05-04T04:19:43 Z dantoh000 Wall (IOI14_wall) C++14
0 / 100
 245 ms 8184 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 = flag = 0;
        if (s != e){
            l = new node(s,m);
            r = new node(m+1,e);
        }
    }
    void value(){
        if (s != e && flag == 1){
            flag = 0;
            //printf("propagating %d %d to %d %d\n",omin,omax,s,e);
            l->mini(s,m,omin);
            l->maxi(s,m,omax);
            r->mini(m+1,e,omin);
            r->maxi(m+1,e,omax);
        }
    }
    int mini(int qs, int qe, int x){
        //printf("min %d %d %d %d %d\n",qs,qe,s,e,x);
        if (qs == s && qe == e){
            omin = min(omin,x);
            omax = min(omin,omax);
            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){
        //printf("max %d %d %d %d %d\n",qs,qe,s,e,x);
        if (qs == s && qe == e){
            omax = max(x,omax);
            omin = max(omin,omax);
            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){
        //printf("query %d %d %d\n",s,e,x);
        value();
        if (s == e){
            //printf("%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("%d %d %d %d\n",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\n");
    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:58:5: warning: no return statement in function returning non-void [-Wreturn-type]
     }
     ^

Subtask #1
0 / 8.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 Incorrect 3 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 169 ms 8184 KB Output is correct
3 Incorrect 245 ms 5480 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.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 Incorrect 4 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -