oj.uz

Submission #135701

# Submission time Handle Problem Language Result Execution time Memory
135701 2019-07-24T09:52:26 Z vince Wall (IOI14_wall) C++14
100 / 100
 1075 ms 100980 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 && mn[pos] > val) return;
    if(op == 2 && mx[pos] < val) 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 29 ms 31736 KB Output is correct
3 Correct 28 ms 31736 KB Output is correct
4 Correct 34 ms 32080 KB Output is correct
5 Correct 33 ms 31992 KB Output is correct
6 Correct 39 ms 32120 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31592 KB Output is correct
2 Correct 194 ms 39472 KB Output is correct
3 Correct 127 ms 35544 KB Output is correct
4 Correct 286 ms 51740 KB Output is correct
5 Correct 403 ms 52728 KB Output is correct
6 Correct 394 ms 51420 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31612 KB Output is correct
2 Correct 29 ms 31736 KB Output is correct
3 Correct 28 ms 31608 KB Output is correct
4 Correct 34 ms 32120 KB Output is correct
5 Correct 34 ms 32120 KB Output is correct
6 Correct 33 ms 31992 KB Output is correct
7 Correct 27 ms 31736 KB Output is correct
8 Correct 196 ms 39480 KB Output is correct
9 Correct 126 ms 35576 KB Output is correct
10 Correct 288 ms 51832 KB Output is correct
11 Correct 403 ms 52788 KB Output is correct
12 Correct 403 ms 51240 KB Output is correct
13 Correct 32 ms 31608 KB Output is correct
14 Correct 204 ms 45404 KB Output is correct
15 Correct 60 ms 33400 KB Output is correct
16 Correct 659 ms 52092 KB Output is correct
17 Correct 404 ms 51448 KB Output is correct
18 Correct 412 ms 51484 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31608 KB Output is correct
2 Correct 42 ms 31736 KB Output is correct
3 Correct 28 ms 31736 KB Output is correct
4 Correct 34 ms 32120 KB Output is correct
5 Correct 38 ms 32120 KB Output is correct
6 Correct 33 ms 32120 KB Output is correct
7 Correct 27 ms 31608 KB Output is correct
8 Correct 194 ms 39548 KB Output is correct
9 Correct 126 ms 35680 KB Output is correct
10 Correct 294 ms 51960 KB Output is correct
11 Correct 399 ms 52856 KB Output is correct
12 Correct 414 ms 51300 KB Output is correct
13 Correct 31 ms 31608 KB Output is correct
14 Correct 206 ms 45404 KB Output is correct
15 Correct 60 ms 33400 KB Output is correct
16 Correct 656 ms 52016 KB Output is correct
17 Correct 404 ms 51384 KB Output is correct
18 Correct 405 ms 51372 KB Output is correct
19 Correct 1054 ms 100820 KB Output is correct
20 Correct 1038 ms 98476 KB Output is correct
21 Correct 1048 ms 100852 KB Output is correct
22 Correct 1040 ms 98460 KB Output is correct
23 Correct 1075 ms 98444 KB Output is correct
24 Correct 1047 ms 98508 KB Output is correct
25 Correct 1059 ms 98424 KB Output is correct
26 Correct 1046 ms 100872 KB Output is correct
27 Correct 1048 ms 100980 KB Output is correct
28 Correct 1040 ms 98604 KB Output is correct
29 Correct 1058 ms 98420 KB Output is correct
30 Correct 1040 ms 98424 KB Output is correct