oj.uz

Submission #1026723

# Submission time Handle Problem Language Result Execution time Memory
1026723 2024-07-18T09:40:33 Z dozer Wall (IOI14_wall) C++14
100 / 100
 1279 ms 104700 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define sp " "
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt","w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define LL node * 2
#define RR node * 2 + 1
#define mid (l + r) / 2
#define ll long long
#define MAXN 2000005

const int modulo = 1e9 + 7;
const ll INF = 2e18 +7;


pii mini[4 * MAXN], maks[4 * MAXN];


vector<int> v = {1, 2};
vector<int> child = {0, 0};

void push(int node, int l, int r){
  if (l == r) return;
  v[0] = 1, v[1] = 2;

  if (maks[node].nd > mini[node].nd) swap(v[0], v[1]);
  
  child[0] = LL, child[1] = RR;

  for (auto i : v){
    int type = i;
    int val = maks[node].st, time = maks[node].nd;
    if (type == 2) val = mini[node].st, time = mini[node].nd;
    for (auto gh : child){
      if (type == 1){ // max
        if (maks[gh].st <= val){
          maks[gh] = {val, time};
          if (mini[gh].st <= val)
            mini[gh] = maks[gh];
        }
      }

      else{
        if (mini[gh].st >= val){
          mini[gh] = {val, time};
          if (maks[gh].st >= val){
            maks[gh] = mini[gh];
          }
        }
      }
      //cout<<"pushed : "<<maks[gh].st<<sp<<mini[gh].st<<endl;
    }
  }

  mini[node] = {modulo, 0};
  maks[node] = {0, 0};
}

void build(int node, int l, int r){
  maks[node] = {0, 0};
  mini[node] = {modulo, 0};
  if (l == r) return;
  build(LL, l, mid);
  build(RR, mid + 1, r);
}


void update(int node, int l, int r, int sl, int sr, int val, int time, int type){
  if (l > sr || r < sl) return;
  if (l != r) push(node, l, r);
  if (l >= sl && r <= sr){
    if (type == 1){ //max operation
      if (maks[node].st <= val){
        maks[node] = {val, time};
        if (mini[node].st <= val) mini[node] = maks[node];
      }
    }
    else{
      if (mini[node].st >= val){
        mini[node] = {val, time};
        if (maks[node].st >= val) maks[node] = mini[node];
      }
    }
    return;
  }

  if (sl <= mid) update(LL, l, mid, sl, sr, val, time, type);
  if (sr > mid) update(RR, mid + 1, r, sl, sr, val, time, type);
}



int query(int node, int l, int r, int sl){
  if (l != r) push(node, l, r);
  if (l == r) {
    return maks[node].st;
  }
  if (sl <= mid) return query(LL, l, mid, sl);
  return query(RR, mid + 1, r, sl);
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  build(1, 1, n);
  
  for (int i = 0; i < k; i++){
    left[i]++, right[i]++;
    update(1, 1, n, left[i], right[i], height[i], i, op[i]);
  }

  for (int j = 1; j <= n; j++){
    finalHeight[j - 1] = query(1, 1, n, j);
  } 
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 8 ms 4700 KB Output is correct
5 Correct 7 ms 4836 KB Output is correct
6 Correct 6 ms 5092 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 108 ms 10320 KB Output is correct
3 Correct 212 ms 8020 KB Output is correct
4 Correct 639 ms 15184 KB Output is correct
5 Correct 258 ms 15444 KB Output is correct
6 Correct 252 ms 15696 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2568 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 11 ms 4700 KB Output is correct
5 Correct 6 ms 4788 KB Output is correct
6 Correct 6 ms 4656 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 106 ms 10428 KB Output is correct
9 Correct 220 ms 8020 KB Output is correct
10 Correct 596 ms 15040 KB Output is correct
11 Correct 281 ms 15612 KB Output is correct
12 Correct 257 ms 15440 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 86 ms 10356 KB Output is correct
15 Correct 42 ms 5208 KB Output is correct
16 Correct 832 ms 15444 KB Output is correct
17 Correct 271 ms 15280 KB Output is correct
18 Correct 264 ms 15436 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 9 ms 4836 KB Output is correct
5 Correct 6 ms 4700 KB Output is correct
6 Correct 6 ms 4700 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 77 ms 10108 KB Output is correct
9 Correct 223 ms 8020 KB Output is correct
10 Correct 611 ms 15188 KB Output is correct
11 Correct 287 ms 15628 KB Output is correct
12 Correct 253 ms 15468 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 85 ms 10076 KB Output is correct
15 Correct 42 ms 5208 KB Output is correct
16 Correct 773 ms 15444 KB Output is correct
17 Correct 285 ms 15444 KB Output is correct
18 Correct 268 ms 15440 KB Output is correct
19 Correct 1220 ms 94036 KB Output is correct
20 Correct 1248 ms 102132 KB Output is correct
21 Correct 1247 ms 104700 KB Output is correct
22 Correct 1209 ms 102020 KB Output is correct
23 Correct 1243 ms 102224 KB Output is correct
24 Correct 1247 ms 102172 KB Output is correct
25 Correct 1191 ms 102040 KB Output is correct
26 Correct 1212 ms 104664 KB Output is correct
27 Correct 1279 ms 104628 KB Output is correct
28 Correct 1198 ms 102072 KB Output is correct
29 Correct 1251 ms 102012 KB Output is correct
30 Correct 1248 ms 102204 KB Output is correct