oj.uz

Submission #135691

# Submission time Handle Problem Language Result Execution time Memory
135691 2019-07-24T09:49:49 Z vince Wall (IOI14_wall) C++14
8 / 100
 3000 ms 45344 KB 
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
#include<stack>
#include<queue>
#include<map>
#include<set>

#define fi first
#define se second
#define long long long

using namespace std;

int mn[8000003], mx[8000003];
int lazy[8000003];

void cek_lazy(int pos, int kir, int kan)
{
    if(lazy[pos] != -1)
    {
        mn[pos] = lazy[pos];
        mx[pos] = lazy[pos];
        if(kan-kir) lazy[pos*2] = lazy[pos*2+1] = lazy[pos];
        lazy[pos] = -1;
    }
}

void update(int pos, int kir, int kan, int qkir, int qkan, int op, int val)
{
    
    
    cek_lazy(pos, kir, kan);
//    printf("POS : %d %d %d Q : %d %d\n", pos, kir, kan, qkir, qkan);
    if(kan < qkir || qkan < kir) return;
    if(op == 1 && mx[pos] <= val && qkir <= kir && kan <= qkan)
    {
        lazy[pos] = val;
        cek_lazy(pos, kir, kan);
        return;
    }
    if(op == 2 && mn[pos] >= val && qkir <= kir && kan <= qkan)
    {
        lazy[pos] = val;
        cek_lazy(pos, kir, kan);
        return;
    }
    if(kir == kan) return;
    
    int mid = (kir+kan)/2;
    update(pos*2, kir, mid, qkir, qkan, op, val);
    update(pos*2+1, mid+1, kan, qkir, qkan, op, val);
    mn[pos] = min(mn[pos*2], mn[pos*2+1]);
    mx[pos] = max(mx[pos*2], mx[pos*2+1]);
}

int query(int pos, int kir, int kan, int idx)
{
    cek_lazy(pos, kir, kan);
    
    if(kir == idx && kan == idx) return mx[pos];
    
    int mid = (kir+kan)/2;
    if(idx <= mid) return query(pos*2, kir, mid, idx);
    else return query(pos*2+1, mid+1, kan, idx);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    memset(lazy, -1, sizeof lazy);
    for(int i = 0; i < k; i++)
    {
//        printf("%d %d %d %d\n", op[i], left[i], right[i], height[i]);
        update(1, 0, n-1, left[i], right[i], op[i], height[i]);
    }
    for(int i = 0; i < n; i++)
        finalHeight[i] = query(1, 0, n-1, i);
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31608 KB Output is correct
2 Correct 34 ms 31864 KB Output is correct
3 Correct 31 ms 31652 KB Output is correct
4 Correct 165 ms 32148 KB Output is correct
5 Correct 50 ms 32120 KB Output is correct
6 Correct 52 ms 32248 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31624 KB Output is correct
2 Correct 203 ms 45344 KB Output is correct
3 Execution timed out 3082 ms 39260 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31608 KB Output is correct
2 Correct 34 ms 31720 KB Output is correct
3 Correct 30 ms 31736 KB Output is correct
4 Correct 164 ms 32140 KB Output is correct
5 Correct 49 ms 32148 KB Output is correct
6 Correct 51 ms 32208 KB Output is correct
7 Correct 27 ms 31616 KB Output is correct
8 Correct 202 ms 45268 KB Output is correct
9 Execution timed out 3036 ms 39244 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31672 KB Output is correct
2 Correct 29 ms 31736 KB Output is correct
3 Correct 30 ms 31728 KB Output is correct
4 Correct 164 ms 32248 KB Output is correct
5 Correct 54 ms 32152 KB Output is correct
6 Correct 51 ms 32268 KB Output is correct
7 Correct 28 ms 31592 KB Output is correct
8 Correct 210 ms 45240 KB Output is correct
9 Execution timed out 3008 ms 39244 KB Time limit exceeded
10 Halted 0 ms 0 KB -