Submission #1105752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105752		andrewp	Wall (IOI14_wall)	C++14	100 / 100	761 ms	89012 KiB

wall

//Dedicated to my love, ivaziva
#pragma GCC optimize("Ofast") 
#include <bits/stdc++.h> 
// #include "wall.h"     
using namespace std;  
using ll=int64_t; 
using pii=pair<int,int>;
using pll=pair<int,int>;    
#define pb push_back
#define fi first
#define se second
#define mp make_pair 
#define ldb double
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()     
void rd(int&x){scanf("%i",&x);}
void rd(ll&x){scanf("%lld",&x);} 
void rd(char*x){scanf("%s",x);}
void rd(ldb&x){scanf("%lf",&x);}
void rd(string&x){scanf("%s",&x);}
int ri(){int x;rd(x);return x;}  
// #ifndef ONLINE_JUDGE
// #include "C:\Users\andre\Downloads\cpp-dump-0.7.0\cpp-dump-0.7.0\cpp-dump.hpp" 
// #define dbg(...) cpp_dump(__VA_ARGS__)
// #else
// #define dump(...)
// #endif  
template<typename T1,typename T2>void rd(pair<T1,T2>&x){rd(x.first);rd(x.second);}
template<typename T>void rd(vector<T>&x){for(T&i:x)rd(i);}
template<typename T,typename...A>void rd(T&x,A&...args){rd(x);rd(args...);}
template<typename T>void rd(){T x;rd(x);return x;} 
template<typename T>vector<T> rv(int n){vector<T> x(n);rd(x);return x;}  
struct Update {
    int min_val = 0;
    int max_val = INT_MAX;
};
class Segtree {
    const int sz;
    vector<Update> t;

    void apply(int v, const Update &x) {
        t[v].min_val = max(t[v].min_val, x.min_val);
        t[v].max_val = max(t[v].max_val, t[v].min_val);
        t[v].max_val = min(t[v].max_val, x.max_val);
        t[v].min_val = min(t[v].min_val, t[v].max_val);
    }

    void push_down(int v) {
        apply(2 * v, t[v]);
        apply(2 * v + 1, t[v]);
        t[v] = Update();
    }

    void update(int v, int l, int r, int ql, int qr, const Update &x) {
        if (qr < l || ql > r) { return; }
        if (ql <= l && r <= qr) {
            apply(v, x);
        } else {
            push_down(v);
            int m = (l + r) / 2;
            update(2 * v, l, m, ql, qr, x);
            update(2 * v + 1, m + 1, r, ql, qr, x);
        }
    }

    Update query(int v, int l, int r, int idx) {
        if (l == r) {
            return t[v];
        } else {
            push_down(v);
            int m = (l + r) / 2;
            return (idx <= m) ? query(2 * v, l, m, idx)
                              : query(2 * v + 1, m + 1, r, idx);
        }
    }

  public:
    Segtree(int n) : sz(n), t(4 * n) {}

    void update(int ql, int qr, const Update &x) { update(1, 0, sz - 1, ql, qr, x); }

    Update get(int idx) { return query(1, 0, sz - 1, idx); }
};
void buildWall(int n,int q,int* op,int* left,int* right,int* height,int* finalHeight) { 
    Segtree st(n);
    for(int i=0;i<q;i++){
        if(op[i]==1){ 
            st.update(left[i],right[i],{height[i],INT_MAX});
        }else{
            st.update(left[i],right[i],{0,height[i]});
        }
    } 
    for(int i=0;i<n;i++){
        finalHeight[i]=st.get(i).min_val; 
    }
    // for(int i=0;i<n;i++){
    //     printf("%d ",finalHeight[i]);
    // }
    // printf("\n");
} 

Compilation message (stderr)

wall.cpp: In function 'void rd(ll&)':
wall.cpp:17:25: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'll*' {aka 'long int*'} [-Wformat=]
   17 | void rd(ll&x){scanf("%lld",&x);}
      |                      ~~~^  ~~
      |                         |  |
      |                         |  ll* {aka long int*}
      |                         long long int*
      |                      %ld
wall.cpp: In function 'void rd(std::string&)':
wall.cpp:20:27: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'std::string*' {aka 'std::__cxx11::basic_string<char>*'} [-Wformat=]
   20 | void rd(string&x){scanf("%s",&x);}
      |                          ~^  ~~
      |                           |  |
      |                           |  std::string* {aka std::__cxx11::basic_string<char>*}
      |                           char*
wall.cpp: In function 'void rd(int&)':
wall.cpp:16:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 | void rd(int&x){scanf("%i",&x);}
      |                ~~~~~^~~~~~~~~
wall.cpp: In function 'void rd(ll&)':
wall.cpp:17:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 | void rd(ll&x){scanf("%lld",&x);}
      |               ~~~~~^~~~~~~~~~~
wall.cpp: In function 'void rd(char*)':
wall.cpp:18:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 | void rd(char*x){scanf("%s",x);}
      |                 ~~~~~^~~~~~~~
wall.cpp: In function 'void rd(double&)':
wall.cpp:19:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 | void rd(ldb&x){scanf("%lf",&x);}
      |                ~~~~~^~~~~~~~~~
wall.cpp: In function 'void rd(std::string&)':
wall.cpp:20:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 | void rd(string&x){scanf("%s",&x);}
      |                   ~~~~~^~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39