oj.uz

Submission #46862

# Submission time Handle Problem Language Result Execution time Memory
46862 2018-04-24T05:43:42 Z OneSubmissionMan Wall (IOI14_wall) C++11
100 / 100
 840 ms 203244 KB 
# include <bits/stdc++.h>

# define x first    
# define y second
# define mp make_pair
// everything go according to my plan      
# define pb push_back
# define sz(a) (int)(a.size())
# define vec vector         
// shimkenttin kyzdary, dzyn, dzyn, dzyn...
# define y1    Y_U_NO_y1
# define left  Y_U_NO_left
# define right Y_U_NO_right  

using namespace std;

typedef pair <int, int> pii; 
typedef long long ll;
typedef long double ld;

const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const ll MXLL = 4e18;
const int Sz = 1110111;
// a pinch of soul
      
const int N = 2e6 + 1;

struct segtree {
  int n;
  int mx[4*N], mn[4*N];     
  int add[4*N];
  segtree (int n) : n(n) {
    memset (add, -1, sizeof add); 
  }
  void push (int v, int tl, int tr) {
    if (add[v] < 0)
      return;
    if (tl != tr) {
      add[2*v] = add[v];
      add[2*v + 1] = add[v];
    }
    mn[v] = mx[v] = add[v];
    add[v] = -1;
  }                
  int l, r, h, tp;         
  void update (int a, int b, int c, int d) {
    l = a, 
    r = b, 
    h = c,
    tp = d;
    update (1, 1, n);
  }   
  void update (int v, int tl, int tr) {
    
    push (v, tl, tr);

    if (tr < l || tl > r)
      return;

    if ((tp == 1 && mn[v] >= h) || (tp == 2 && mx[v] < h))
      return;

    if (l <= tl && tr <= r && ((tp == 1 && mx[v] <= h) || (tp == 2 && mn[v] >= h))) {
      add[v] = h;
      push (v, tl, tr);
      return;
    }
    int tmid = (tl+tr) >> 1;
    update (2*v, tl, tmid);
    update (2*v + 1, tmid+1, tr);
    recalc (v);
  }   
  void recalc (int v) {
    mx[v] = max (mx[2*v], mx[2*v + 1]);

    mn[v] = min (mn[2*v], mn[2*v + 1]);
  }
  void get (int v, int tl, int tr, int ans[]) {
    push (v, tl, tr);
    if (tl == tr) {
      ans[tl - 1] = mn[v];
      return;
    }
    int tmid = (tl+tr) >> 1;
    get (2*v, tl, tmid, ans);
    get (2*v + 1, tmid+1, tr, ans);
  }
  void get (int ans[]) {
    get (1, 1, n, ans);
  }   
};

void buildWall (int n, int k, int tp[], int l[], int r[], int h[], int ans[]) {
  segtree T (n);  
  for (int i = 0; i < k; i++) {
    //break;
    l[i]++, r[i]++;  
    T.update (l[i], r[i], h[i], tp[i]);
  }                      
  T.get (ans);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 31608 KB Output is correct
2 Correct 25 ms 31720 KB Output is correct
3 Correct 25 ms 31924 KB Output is correct
4 Correct 31 ms 32344 KB Output is correct
5 Correct 29 ms 32360 KB Output is correct
6 Correct 29 ms 32360 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 32360 KB Output is correct
2 Correct 219 ms 39748 KB Output is correct
3 Correct 120 ms 39748 KB Output is correct
4 Correct 267 ms 42416 KB Output is correct
5 Correct 247 ms 42812 KB Output is correct
6 Correct 278 ms 42884 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 42884 KB Output is correct
2 Correct 25 ms 42884 KB Output is correct
3 Correct 26 ms 42884 KB Output is correct
4 Correct 29 ms 42884 KB Output is correct
5 Correct 28 ms 42884 KB Output is correct
6 Correct 33 ms 42884 KB Output is correct
7 Correct 25 ms 42884 KB Output is correct
8 Correct 193 ms 42884 KB Output is correct
9 Correct 120 ms 42884 KB Output is correct
10 Correct 263 ms 42884 KB Output is correct
11 Correct 270 ms 43068 KB Output is correct
12 Correct 289 ms 43068 KB Output is correct
13 Correct 26 ms 43068 KB Output is correct
14 Correct 201 ms 43068 KB Output is correct
15 Correct 60 ms 43068 KB Output is correct
16 Correct 628 ms 43068 KB Output is correct
17 Correct 340 ms 43068 KB Output is correct
18 Correct 354 ms 43068 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 43068 KB Output is correct
2 Correct 26 ms 43068 KB Output is correct
3 Correct 25 ms 43068 KB Output is correct
4 Correct 35 ms 43068 KB Output is correct
5 Correct 31 ms 43068 KB Output is correct
6 Correct 29 ms 43068 KB Output is correct
7 Correct 26 ms 43068 KB Output is correct
8 Correct 200 ms 43068 KB Output is correct
9 Correct 117 ms 43068 KB Output is correct
10 Correct 306 ms 43068 KB Output is correct
11 Correct 249 ms 43068 KB Output is correct
12 Correct 289 ms 43068 KB Output is correct
13 Correct 22 ms 43068 KB Output is correct
14 Correct 218 ms 43068 KB Output is correct
15 Correct 54 ms 43068 KB Output is correct
16 Correct 612 ms 43068 KB Output is correct
17 Correct 358 ms 43068 KB Output is correct
18 Correct 348 ms 43068 KB Output is correct
19 Correct 796 ms 90556 KB Output is correct
20 Correct 783 ms 98540 KB Output is correct
21 Correct 781 ms 111516 KB Output is correct
22 Correct 765 ms 119600 KB Output is correct
23 Correct 804 ms 130008 KB Output is correct
24 Correct 840 ms 140496 KB Output is correct
25 Correct 790 ms 150808 KB Output is correct
26 Correct 792 ms 163700 KB Output is correct
27 Correct 796 ms 174196 KB Output is correct
28 Correct 750 ms 182300 KB Output is correct
29 Correct 767 ms 192780 KB Output is correct
30 Correct 753 ms 203244 KB Output is correct