oj.uz

Submission #995572

# Submission time Handle Problem Language Result Execution time Memory
995572 2024-06-09T11:36:18 Z wood Wall (IOI14_wall) C++17
61 / 100
 453 ms 50512 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 = 1e6;
#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 7 ms 12120 KB Output is correct
2 Correct 10 ms 12124 KB Output is correct
3 Correct 7 ms 12124 KB Output is correct
4 Correct 12 ms 12380 KB Output is correct
5 Correct 10 ms 12380 KB Output is correct
6 Correct 12 ms 12380 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12124 KB Output is correct
2 Correct 110 ms 25608 KB Output is correct
3 Correct 152 ms 18064 KB Output is correct
4 Correct 451 ms 30036 KB Output is correct
5 Correct 276 ms 31056 KB Output is correct
6 Correct 287 ms 29520 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12124 KB Output is correct
2 Correct 7 ms 12100 KB Output is correct
3 Correct 8 ms 12124 KB Output is correct
4 Correct 12 ms 12300 KB Output is correct
5 Correct 12 ms 12376 KB Output is correct
6 Correct 18 ms 12380 KB Output is correct
7 Correct 7 ms 12120 KB Output is correct
8 Correct 94 ms 25764 KB Output is correct
9 Correct 156 ms 19304 KB Output is correct
10 Correct 426 ms 30100 KB Output is correct
11 Correct 277 ms 30996 KB Output is correct
12 Correct 274 ms 29524 KB Output is correct
13 Correct 6 ms 12120 KB Output is correct
14 Correct 89 ms 25684 KB Output is correct
15 Correct 32 ms 13144 KB Output is correct
16 Correct 453 ms 30340 KB Output is correct
17 Correct 286 ms 29844 KB Output is correct
18 Correct 311 ms 29780 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12120 KB Output is correct
2 Correct 7 ms 12092 KB Output is correct
3 Correct 7 ms 12124 KB Output is correct
4 Correct 12 ms 12372 KB Output is correct
5 Correct 12 ms 12380 KB Output is correct
6 Correct 15 ms 12380 KB Output is correct
7 Correct 7 ms 12124 KB Output is correct
8 Correct 91 ms 25748 KB Output is correct
9 Correct 160 ms 19284 KB Output is correct
10 Correct 440 ms 30056 KB Output is correct
11 Correct 275 ms 31064 KB Output is correct
12 Correct 264 ms 29524 KB Output is correct
13 Correct 10 ms 12120 KB Output is correct
14 Correct 100 ms 25684 KB Output is correct
15 Correct 31 ms 13148 KB Output is correct
16 Correct 437 ms 30328 KB Output is correct
17 Correct 279 ms 29656 KB Output is correct
18 Correct 269 ms 29812 KB Output is correct
19 Runtime error 127 ms 50512 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -