oj.uz

Submission #1105752

# Submission time Handle Problem Language Result Execution time Memory
1105752 2024-10-27T16:06:40 Z andrewp Wall (IOI14_wall) C++14
100 / 100
 761 ms 89012 KB 
//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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 5 ms 848 KB Output is correct
5 Correct 5 ms 848 KB Output is correct
6 Correct 5 ms 848 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 99 ms 11336 KB Output is correct
3 Correct 109 ms 6216 KB Output is correct
4 Correct 324 ms 19440 KB Output is correct
5 Correct 204 ms 21760 KB Output is correct
6 Correct 192 ms 20308 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 5 ms 848 KB Output is correct
5 Correct 5 ms 1020 KB Output is correct
6 Correct 5 ms 848 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 84 ms 8264 KB Output is correct
9 Correct 105 ms 7240 KB Output is correct
10 Correct 310 ms 19400 KB Output is correct
11 Correct 210 ms 21832 KB Output is correct
12 Correct 200 ms 20296 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 92 ms 13868 KB Output is correct
15 Correct 20 ms 1872 KB Output is correct
16 Correct 313 ms 21272 KB Output is correct
17 Correct 197 ms 20680 KB Output is correct
18 Correct 197 ms 20808 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 5 ms 848 KB Output is correct
5 Correct 4 ms 848 KB Output is correct
6 Correct 5 ms 848 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 92 ms 11344 KB Output is correct
9 Correct 104 ms 4168 KB Output is correct
10 Correct 308 ms 19280 KB Output is correct
11 Correct 216 ms 21832 KB Output is correct
12 Correct 201 ms 20296 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 85 ms 14012 KB Output is correct
15 Correct 19 ms 1908 KB Output is correct
16 Correct 300 ms 21372 KB Output is correct
17 Correct 197 ms 20808 KB Output is correct
18 Correct 194 ms 20808 KB Output is correct
19 Correct 686 ms 88904 KB Output is correct
20 Correct 685 ms 89004 KB Output is correct
21 Correct 718 ms 88908 KB Output is correct
22 Correct 745 ms 88904 KB Output is correct
23 Correct 725 ms 89004 KB Output is correct
24 Correct 732 ms 89012 KB Output is correct
25 Correct 713 ms 89004 KB Output is correct
26 Correct 715 ms 89000 KB Output is correct
27 Correct 761 ms 89004 KB Output is correct
28 Correct 717 ms 89004 KB Output is correct
29 Correct 684 ms 89004 KB Output is correct
30 Correct 687 ms 88904 KB Output is correct