oj.uz

Submission #412549

# Submission time Handle Problem Language Result Execution time Memory
412549 2021-05-27T05:56:22 Z Karliver Wall (IOI14_wall) C++14
100 / 100
 897 ms 107344 KB 
#include "wall.h"
    
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;

const int INF = 1e9 + 1;
const int N = 2e6 + 10;
const double eps = 1e-7;

template <class T> using V = vector<T>;  // from yosupo 
template <class T> using VV = V<V<T>>;  // from yosupo

template <typename XPAX>
void ckma(XPAX &x, XPAX y) {
    x = (x < y ? y : x);
}
template <typename XPAX>
void ckmi(XPAX &x, XPAX y) {
    x = (x > y ? y : x);
}

struct node{
    int up = 0, down = INF;
    node(){}
} d[4*N];
void apply(int ind, int up, int down){
    if(ind>=0&&ind<4*N){
        d[ind].down = min(d[ind].down,down);
        d[ind].down = max(d[ind].down,up);
        d[ind].up = max(d[ind].up,up);
        d[ind].up = min(d[ind].up,down);
    }
}
void range_modify(int mode, int ml, int mr, int val, int ind = 1, int l = 0, int r = N-1){
    if(ml>r||mr<l) return;
    if(ml<=l&&mr>=r){
        if(mode){
            d[ind].down = min(d[ind].down,val);
            d[ind].up = min(d[ind].up,val);
        }
        else{
            d[ind].down = max(d[ind].down,val);
            d[ind].up = max(d[ind].up,val);
        }
        return;
    }
    int mid = (l+r)/2;
    apply(ind<<1,d[ind].up,d[ind].down);
    apply(ind<<1|1,d[ind].up,d[ind].down);
    d[ind].up = 0, d[ind].down = INF;
    range_modify(mode,ml,mr,val,ind<<1,l,mid);
    range_modify(mode,ml,mr,val,ind<<1|1,mid+1,r);
}
int n,k;
V<int> ans(n);
void query(int ind, int l, int r){
    if(l==r){
        if(l!=n) ans.push_back(min(d[ind].up,d[ind].down));
        return;
    }
    apply(ind<<1,d[ind].up,d[ind].down);
    apply(ind<<1|1,d[ind].up,d[ind].down);
    d[ind].up = 0, d[ind].down = INF;
    int mid = l+r>>1;
    query(ind<<1,l,mid);
    query(ind<<1|1,mid+1,r);
}

void buildWall(int X, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    
    n = X;

    for(int i = 0;i < k;++i) {
        
        op[i]--;
        
            
        range_modify(op[i], left[i], right[i], height[i],1,0,n);
    }
    query(1,0,n);
    forn(i, n) finalHeight[i] = ans[i];
    
    // 

  return;
}

Compilation message

wall.cpp: In function 'void query(int, int, int)':
wall.cpp:73:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |     int mid = l+r>>1;
      |               ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 62788 KB Output is correct
2 Correct 43 ms 62884 KB Output is correct
3 Correct 39 ms 62860 KB Output is correct
4 Correct 43 ms 63180 KB Output is correct
5 Correct 42 ms 63180 KB Output is correct
6 Correct 45 ms 63048 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 62792 KB Output is correct
2 Correct 206 ms 70724 KB Output is correct
3 Correct 221 ms 66376 KB Output is correct
4 Correct 540 ms 71872 KB Output is correct
5 Correct 380 ms 72372 KB Output is correct
6 Correct 364 ms 72276 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 62892 KB Output is correct
2 Correct 39 ms 62920 KB Output is correct
3 Correct 39 ms 62820 KB Output is correct
4 Correct 43 ms 63248 KB Output is correct
5 Correct 42 ms 63140 KB Output is correct
6 Correct 43 ms 63092 KB Output is correct
7 Correct 37 ms 62844 KB Output is correct
8 Correct 212 ms 70696 KB Output is correct
9 Correct 218 ms 66476 KB Output is correct
10 Correct 528 ms 71844 KB Output is correct
11 Correct 381 ms 72404 KB Output is correct
12 Correct 376 ms 72252 KB Output is correct
13 Correct 38 ms 62820 KB Output is correct
14 Correct 202 ms 70644 KB Output is correct
15 Correct 66 ms 63712 KB Output is correct
16 Correct 535 ms 72096 KB Output is correct
17 Correct 397 ms 72096 KB Output is correct
18 Correct 365 ms 72016 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 62788 KB Output is correct
2 Correct 38 ms 62972 KB Output is correct
3 Correct 39 ms 62900 KB Output is correct
4 Correct 43 ms 63176 KB Output is correct
5 Correct 46 ms 63132 KB Output is correct
6 Correct 43 ms 63152 KB Output is correct
7 Correct 41 ms 62884 KB Output is correct
8 Correct 212 ms 70644 KB Output is correct
9 Correct 215 ms 66368 KB Output is correct
10 Correct 540 ms 71768 KB Output is correct
11 Correct 375 ms 72348 KB Output is correct
12 Correct 381 ms 72340 KB Output is correct
13 Correct 44 ms 62796 KB Output is correct
14 Correct 208 ms 70736 KB Output is correct
15 Correct 65 ms 63672 KB Output is correct
16 Correct 542 ms 72024 KB Output is correct
17 Correct 369 ms 72100 KB Output is correct
18 Correct 395 ms 72100 KB Output is correct
19 Correct 827 ms 96828 KB Output is correct
20 Correct 810 ms 104704 KB Output is correct
21 Correct 829 ms 107228 KB Output is correct
22 Correct 850 ms 104744 KB Output is correct
23 Correct 834 ms 104668 KB Output is correct
24 Correct 897 ms 104944 KB Output is correct
25 Correct 818 ms 104660 KB Output is correct
26 Correct 887 ms 107344 KB Output is correct
27 Correct 821 ms 107244 KB Output is correct
28 Correct 859 ms 104672 KB Output is correct
29 Correct 798 ms 104740 KB Output is correct
30 Correct 842 ms 104740 KB Output is correct