oj.uz

Submission #46861

# Submission time Handle Problem Language Result Execution time Memory
46861 2018-04-24T05:42:36 Z OneSubmissionMan Wall (IOI14_wall) C++11
61 / 100
 634 ms 219276 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

struct segtree {
  int n;
  int mx[Sz], mn[Sz];     
  int add[Sz];
  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 5 ms 4600 KB Output is correct
2 Correct 6 ms 4840 KB Output is correct
3 Correct 6 ms 4840 KB Output is correct
4 Correct 11 ms 5384 KB Output is correct
5 Correct 10 ms 5600 KB Output is correct
6 Correct 10 ms 5688 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5688 KB Output is correct
2 Correct 177 ms 18964 KB Output is correct
3 Correct 214 ms 18964 KB Output is correct
4 Correct 255 ms 35020 KB Output is correct
5 Correct 237 ms 45780 KB Output is correct
6 Correct 275 ms 54348 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 54348 KB Output is correct
2 Correct 7 ms 54348 KB Output is correct
3 Correct 7 ms 54348 KB Output is correct
4 Correct 11 ms 54348 KB Output is correct
5 Correct 10 ms 54348 KB Output is correct
6 Correct 10 ms 54348 KB Output is correct
7 Correct 5 ms 54348 KB Output is correct
8 Correct 190 ms 57524 KB Output is correct
9 Correct 106 ms 57524 KB Output is correct
10 Correct 313 ms 73476 KB Output is correct
11 Correct 236 ms 84236 KB Output is correct
12 Correct 284 ms 92836 KB Output is correct
13 Correct 5 ms 92836 KB Output is correct
14 Correct 189 ms 95480 KB Output is correct
15 Correct 37 ms 95480 KB Output is correct
16 Correct 634 ms 108568 KB Output is correct
17 Correct 317 ms 117760 KB Output is correct
18 Correct 322 ms 126712 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 126712 KB Output is correct
2 Correct 7 ms 126712 KB Output is correct
3 Correct 6 ms 126712 KB Output is correct
4 Correct 11 ms 126712 KB Output is correct
5 Correct 10 ms 126712 KB Output is correct
6 Correct 10 ms 126712 KB Output is correct
7 Correct 5 ms 126712 KB Output is correct
8 Correct 179 ms 130064 KB Output is correct
9 Correct 103 ms 130064 KB Output is correct
10 Correct 267 ms 146196 KB Output is correct
11 Correct 232 ms 156744 KB Output is correct
12 Correct 492 ms 165396 KB Output is correct
13 Correct 5 ms 165396 KB Output is correct
14 Correct 184 ms 167984 KB Output is correct
15 Correct 37 ms 167984 KB Output is correct
16 Correct 623 ms 181092 KB Output is correct
17 Correct 318 ms 190140 KB Output is correct
18 Correct 386 ms 199308 KB Output is correct
19 Runtime error 214 ms 219276 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -