oj.uz

Submission #990193

# Submission time Handle Problem Language Result Execution time Memory
990193 2024-05-29T20:20:46 Z teokakabadze Wall (IOI14_wall) C++17
8 / 100
 3000 ms 8272 KB 
#include<bits/stdc++.h>
using namespace std;
#include "wall.h"

const int inf = 1e9;
int lazy[500005], t[500005];

void push(int v, int l, int r, bool type)
{
    if(!type)
    {
        t[v] = max(lazy[v], t[v]);
        if(l != r) lazy[2 * v] = max(lazy[2 * v], lazy[v]), lazy[2 * v + 1] = max(lazy[2 * v + 1], lazy[v]);
        lazy[v] = 0;
    }
    else
    {
        t[v] = min(lazy[v], t[v]);
        if(l != r) lazy[2 * v] = min(lazy[2 * v], lazy[v]), lazy[2 * v + 1] = min(lazy[2 * v + 1], lazy[v]);
        lazy[v] = inf;
    }
}

void upd(int v, int l, int r, int L, int R, int val, bool type)
{
    //cout << type << ' ' << l << ' ' << r << ' ' << L << ' '<< R<< endl;
    push(v, l, r, type);
    if(L > r || l > R) return;
    if(L <= l && r <= R)
    {
        if(!type) lazy[v] = max(lazy[v], val);
        else lazy[v] = min(lazy[v], val);
        return;
    }
    int m = (l + r) / 2;
    upd(v * 2, l, m, L, R, val, type);
    upd(v * 2 + 1, m + 1, r, L, R, val, type);
    if(!type) t[v] = min(t[v * 2], t[v * 2 + 1]);
    else t[v] = max(t[v * 2], t[v * 2 + 1]);
}

int get(int v, int l, int r, int ind, bool type)
{
    push(v, l, r, type);
    if(l == r) return t[v];
    int m = (l + r) / 2;
    if(ind <= m) return get(v * 2, l, m, ind, type);
    return get(v * 2 + 1, m + 1, r, ind, type);
}

void build(int v, int l, int r)
{
    lazy[v] = inf;
    if(l == r) return;
    int m = (l + r) / 2;
    build(v * 2, l, m);
    build(v * 2 + 1, m + 1, r);
    t[v] = max(t[v * 2], t[v * 2 + 1]);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    bool f = 0;
    int i;
   /* for(i = 0; i < k; i++)
    {
        left[i]++, right[i]++;
        if(op[i] == 1) upd(1, 1, n, left[i], right[i], height[i], 0);
        else
        {
            if(!f)
            {
                for(int j = 1; j <= n; j++)
                finalHeight[j - 1] = get(1, 1, n, j, 0);
                build(1, 1, n);
                f = 1;
            }
            //cout << left[i] << ' ' << right[i] << '\n';
            upd(1, 1, n, left[i], right[i], height[i], 1);
        }
    }
    for(i = 1; i <= n; i++)
        finalHeight[i - 1] = get(1, 1, n, i, 1); */
    for(i = 0; i < n; i++)
    for(int j = 0; j < k; j++)
    {
        if(i >= left[j] && i <= right[j])
        {
            if(op[j] == 1) finalHeight[i] = max(finalHeight[i], height[j]);
            else finalHeight[i] = min(finalHeight[i], height[j]);
        }
    }
    return;
}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:62:10: warning: unused variable 'f' [-Wunused-variable]
   62 |     bool f = 0;
      |          ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 91 ms 556 KB Output is correct
5 Correct 69 ms 592 KB Output is correct
6 Correct 59 ms 532 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 77 ms 8256 KB Output is correct
3 Execution timed out 3014 ms 3664 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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 476 KB Output is correct
4 Correct 87 ms 548 KB Output is correct
5 Correct 60 ms 552 KB Output is correct
6 Correct 60 ms 536 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 86 ms 8272 KB Output is correct
9 Execution timed out 3074 ms 3516 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 85 ms 536 KB Output is correct
5 Correct 60 ms 592 KB Output is correct
6 Correct 63 ms 596 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 78 ms 8080 KB Output is correct
9 Execution timed out 3066 ms 3668 KB Time limit exceeded
10 Halted 0 ms 0 KB -