oj.uz

Submission #995055

# Submission time Handle Problem Language Result Execution time Memory
995055 2024-06-08T11:44:36 Z wood Wall (IOI14_wall) C++17
0 / 100
 123 ms 15984 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

   constexpr int N = 1e6;

struct segtree
{
    int size = 1, ops[N] = {0}, val[N] = {0};
    segtree(int n){ while(size<n) size*=2;}

    void propagate(int x, int s){
        if(s==1){
            if(ops[x]<0) val[x] = max(val[x],-ops[x]-1);
            else if(ops[x]>0) val[x] = min(val[x],ops[x]-1);
        }
        else{
            if(ops[x]!=0){
                ops[2*x+1] = ops[x];
                ops[2*x+2] = ops[x];
            }
        }
        ops[x] = 0;
    }

    void set(int l, int r, int u){
        set(l,r,u,0,0,size);
    }
    void set(int l, int r,int u, int x, int lx, int rx){
        propagate(x,rx-lx);
        if(rx<=l||lx>=r) return;
        else if(rx<=r&&lx>=l){
            ops[x] = u;
            return;
        }
        int m = (rx+lx)/2;
        set(l,r,u,2*x+1,lx,m);
        set(l,r,u,2*x+2,m,rx);
        propagate(2*x+1,m-lx);
        propagate(2*x+2,m-lx);
    }

    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 val[x];
        int m = (rx+lx)/2;
        if(i<m) return get(i,2*x+1,lx,m);
        else 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++)
    {
        if(op[i]==1) height[i] = -height[i]-1;
        else height[i]++;
        sgt.set(left[i],right[i]+1,height[i]);
    }
    for (size_t i = 0; i < n ; i++)
    {
        finalHeight[i] = sgt.get(i);
    }
}

/*
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/

Compilation message

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8028 KB Output is correct
2 Correct 7 ms 8188 KB Output is correct
3 Incorrect 4 ms 8280 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8024 KB Output is correct
2 Correct 82 ms 15984 KB Output is correct
3 Incorrect 123 ms 11600 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8024 KB Output is correct
2 Correct 6 ms 8284 KB Output is correct
3 Incorrect 5 ms 8140 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8028 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct
3 Incorrect 5 ms 8284 KB Output isn't correct
4 Halted 0 ms 0 KB -