oj.uz

Submission #995573

# Submission time Handle Problem Language Result Execution time Memory
995573 2024-06-09T11:36:58 Z wood Wall (IOI14_wall) C++17
100 / 100
 1049 ms 154184 KB 
#include "wall.h"
#include <bits/stdc++.h>  
using namespace std;
 
typedef long long ll;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define vi vector<int>
#define vp32 vector<p32>
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MOD %1000000007
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//never guess
//never debug without reviewing code
//never try adding ones or substracting them
//only step by step debug when necessay

#ifndef _WIN32
    constexpr int N = 1e7;
#else
    constexpr int N = 100;
#endif

struct segtree
{
    int size = 1, lazymin[N], lazymax[N] = {0}, value[N] = {0};
    segtree(int n){while(size<n) size*=2; fill(lazymin,lazymin+N,INT_MAX);}

    void propagate(int x, int s){
        if(s==1){
            value[x] = min(value[x],lazymin[x]);
            value[x] = max(value[x],lazymax[x]);
            lazymin[x] = INT_MAX; lazymax[x] = 0;
            return;
        }
        lazymin[2*x+1] = min(lazymin[2*x+1],lazymin[x]);
        lazymin[2*x+2] = min(lazymin[2*x+2],lazymin[x]);
        lazymax[2*x+1] = max(lazymax[2*x+1],lazymax[x]);
        lazymax[2*x+2] = max(lazymax[2*x+2],lazymax[x]);
        lazymax[2*x+1] = min(lazymax[2*x+1],lazymin[x]);
        lazymax[2*x+2] = min(lazymax[2*x+2],lazymin[x]);
        lazymin[2*x+1] = max(lazymin[2*x+1],lazymax[x]);
        lazymin[2*x+2] = max(lazymin[2*x+2],lazymax[x]);
        lazymin[x] = INT_MAX; lazymax[x] = 0;
    }
    
    void set(int l, int r, int u, bool minimize){
        set(l,r,u,minimize,0,0,size);
    }
    void set(int l, int r, int u, bool minimize, int x, int lx, int rx){
        propagate(x,rx-lx);
        if(rx<=l||lx>=r) return;
        if(rx<=r&&lx>=l){
            if(minimize){
                lazymin[x] = min(lazymin[x],u);
                lazymax[x] = min(lazymin[x],lazymax[x]);
            }
            else{
                lazymax[x] = max(lazymax[x],u);
                lazymin[x] = max(lazymin[x],lazymax[x]);
            }
            return;
        }
        int m = (rx+lx)/2;
        set(l,r,u,minimize,2*x+1,lx,m);
        set(l,r,u,minimize,2*x+2,m,rx);
    }

    int get(int i){
        return get(i,0,0,size);
    }
    int get(int i, int x, int lx, int rx){
        propagate(x,rx-lx);
        if(rx-lx==1) return value[x];
        int m = (rx+lx)/2;
        if(i<m) return get(i,2*x+1,lx,m);
        return get(i,2*x+2,m,rx);
    }
};


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    segtree sgt(n);
    for (size_t i = 0; i < k; i++)
        sgt.set(left[i],right[i]+1,height[i],op[i]==2);
    for (size_t i = 0; i < n; i++)
        finalHeight[i] = sgt.get(i);
}

#ifdef _WIN32
int main()
{
    freopen("sample-2.in", "r", stdin);
    freopen("input.out", "w", stdout);
    int n;
    int k;

    int i, j;  
    int status = 0;

    status = scanf("%d%d", &n, &k);
    assert(status == 2);

    int* op = (int*)calloc(sizeof(int), k);
    int* left = (int*)calloc(sizeof(int), k);
    int* right = (int*)calloc(sizeof(int), k);
    int* height = (int*)calloc(sizeof(int), k);
    int* finalHeight = (int*)calloc(sizeof(int), n);

    for (i = 0; i < k; i++){
        status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
        assert(status == 4);
    }

    buildWall(n, k, op, left, right, height, finalHeight);

    for (j = 0; j < n; j++)
        printf("%d\n", finalHeight[j]);
    
    return 0;
}
#endif

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:92:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |     for (size_t i = 0; i < k; i++)
      |                        ~~^~~
wall.cpp:94:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |     for (size_t i = 0; i < n; i++)
      |                        ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 117584 KB Output is correct
2 Correct 65 ms 117848 KB Output is correct
3 Correct 63 ms 117840 KB Output is correct
4 Correct 69 ms 117836 KB Output is correct
5 Correct 67 ms 117976 KB Output is correct
6 Correct 75 ms 117976 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 117584 KB Output is correct
2 Correct 159 ms 125520 KB Output is correct
3 Correct 220 ms 121144 KB Output is correct
4 Correct 477 ms 126048 KB Output is correct
5 Correct 345 ms 126544 KB Output is correct
6 Correct 319 ms 126708 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 117840 KB Output is correct
2 Correct 64 ms 117812 KB Output is correct
3 Correct 65 ms 117852 KB Output is correct
4 Correct 69 ms 117840 KB Output is correct
5 Correct 66 ms 117840 KB Output is correct
6 Correct 67 ms 117948 KB Output is correct
7 Correct 63 ms 117728 KB Output is correct
8 Correct 144 ms 125520 KB Output is correct
9 Correct 209 ms 121116 KB Output is correct
10 Correct 522 ms 126020 KB Output is correct
11 Correct 319 ms 126548 KB Output is correct
12 Correct 312 ms 126544 KB Output is correct
13 Correct 61 ms 117584 KB Output is correct
14 Correct 138 ms 125552 KB Output is correct
15 Correct 89 ms 118360 KB Output is correct
16 Correct 494 ms 126288 KB Output is correct
17 Correct 319 ms 126292 KB Output is correct
18 Correct 368 ms 126272 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 117660 KB Output is correct
2 Correct 64 ms 117784 KB Output is correct
3 Correct 80 ms 117840 KB Output is correct
4 Correct 70 ms 117840 KB Output is correct
5 Correct 65 ms 117844 KB Output is correct
6 Correct 77 ms 117844 KB Output is correct
7 Correct 64 ms 117744 KB Output is correct
8 Correct 138 ms 125520 KB Output is correct
9 Correct 203 ms 121140 KB Output is correct
10 Correct 494 ms 126296 KB Output is correct
11 Correct 326 ms 126548 KB Output is correct
12 Correct 331 ms 126544 KB Output is correct
13 Correct 66 ms 117824 KB Output is correct
14 Correct 148 ms 125648 KB Output is correct
15 Correct 85 ms 118356 KB Output is correct
16 Correct 488 ms 126376 KB Output is correct
17 Correct 328 ms 126292 KB Output is correct
18 Correct 324 ms 126292 KB Output is correct
19 Correct 973 ms 143696 KB Output is correct
20 Correct 1049 ms 151688 KB Output is correct
21 Correct 982 ms 154184 KB Output is correct
22 Correct 991 ms 151640 KB Output is correct
23 Correct 986 ms 151544 KB Output is correct
24 Correct 983 ms 151828 KB Output is correct
25 Correct 983 ms 151632 KB Output is correct
26 Correct 1002 ms 154088 KB Output is correct
27 Correct 1000 ms 154028 KB Output is correct
28 Correct 972 ms 151724 KB Output is correct
29 Correct 998 ms 151732 KB Output is correct
30 Correct 995 ms 151672 KB Output is correct