oj.uz

Submission #287125

# Submission time Handle Problem Language Result Execution time Memory
287125 2020-08-31T12:20:25 Z Atill83 Wall (IOI14_wall) C++14
8 / 100
 3000 ms 8192 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
const int MAXN = (int) 2e6 + 5;
typedef pair<int, int> pii;
int * an;

struct node{
    int deg = 0;
    node * l = NULL; 
    node * r = NULL;
};
typedef node * pn;

void upd(pn cur, int tl, int tr, int ll, int rr, int dg, int op){
    //cerr<<ll<<" "<<rr<<" "<<cur->deg<<endl;
    if(ll > rr) return;
    if(tl == ll && tr == rr){
        if(cur->l == NULL){
            if(op == 1){
                cur->deg = max(cur->deg, dg);
            }else{
                cur->deg = min(cur->deg, dg);
            }
        }else{
            assert((cur->r) != NULL);
            int tm = (tl + tr) / 2;
            upd(cur->l, tl, tm, ll, tm, dg, op);
            upd(cur->r, tm + 1, tr, tm + 1, rr, dg, op);
        }
    }else{
        int tm = (tl + tr) / 2;
        if(cur->l == NULL){
            cur->l = new node;
            cur->r = new node;
            cur->l->deg = cur->deg;
            cur->r->deg = cur->deg;
        }
        upd(cur->l, tl, tm, ll, min(tm, rr), dg, op);
        upd(cur->r, tm + 1, tr, max(ll, tm + 1), rr, dg, op);
    }
}

void fina(pn cur, int tl , int tr){
    if(cur->l == NULL){
        for(int i = tl; i <= tr; i++){
            an[i] = cur->deg;
        }
    }else{
        assert(cur->r != NULL);
        int tm = (tl + tr) / 2;
        fina(cur->l, tl, tm);
        fina(cur->r, tm + 1, tr);
    }
}



void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    pn root = new node;
    root->deg = 0;
    an = finalHeight;
    for(int i = 0; i < k; i++){
        upd(root, 0, n - 1, left[i], right[i], height[i], op[i]);
    }
    fina(root, 0, n - 1);
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 148 ms 992 KB Output is correct
5 Correct 5 ms 896 KB Output is correct
6 Correct 5 ms 896 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 176 ms 8188 KB Output is correct
3 Execution timed out 3056 ms 5152 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 147 ms 980 KB Output is correct
5 Correct 6 ms 1024 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 173 ms 8192 KB Output is correct
9 Execution timed out 3071 ms 4984 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 150 ms 944 KB Output is correct
5 Correct 6 ms 1024 KB Output is correct
6 Correct 6 ms 1024 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 179 ms 8144 KB Output is correct
9 Execution timed out 3078 ms 4976 KB Time limit exceeded
10 Halted 0 ms 0 KB -