oj.uz

Submission #995570

# Submission time Handle Problem Language Result Execution time Memory
995570 2024-06-09T11:28:42 Z wood Wall (IOI14_wall) C++17
24 / 100
 359 ms 30256 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] = max(value[x],lazymax[x]);
            value[x] = min(value[x],lazymin[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]);
        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:88:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   88 |     for (size_t i = 0; i < k; i++)
      |                        ~~^~~
wall.cpp:90:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |     for (size_t i = 0; i < n; i++)
      |                        ~~^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12124 KB Output is correct
2 Correct 8 ms 12124 KB Output is correct
3 Incorrect 7 ms 12136 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12124 KB Output is correct
2 Correct 91 ms 25356 KB Output is correct
3 Correct 125 ms 18004 KB Output is correct
4 Correct 359 ms 29412 KB Output is correct
5 Correct 230 ms 30256 KB Output is correct
6 Correct 218 ms 29008 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12120 KB Output is correct
2 Correct 8 ms 12124 KB Output is correct
3 Incorrect 8 ms 12124 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12120 KB Output is correct
2 Correct 12 ms 12252 KB Output is correct
3 Incorrect 8 ms 12124 KB Output isn't correct
4 Halted 0 ms 0 KB -