oj.uz

Submission #1026720

# Submission time Handle Problem Language Result Execution time Memory
1026720 2024-07-18T09:36:56 Z dozer Wall (IOI14_wall) C++14
61 / 100
 3000 ms 93016 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];



void push(int node, int l, int r){
  if (l == r) return;
  vector<int> v = {1, 2};
  if (maks[node].nd > mini[node].nd) swap(v[0], v[1]);
  vector<int> child = {LL, 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){
  push(node, l, r);
 // cout<<l<<sp<<r<<endl;
  if (l > sr || r < sl) return;
  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;
  }

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



int query(int node, int l, int r, int sl){
  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 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 17 ms 4696 KB Output is correct
5 Correct 14 ms 4700 KB Output is correct
6 Correct 14 ms 4872 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 83 ms 10136 KB Output is correct
3 Correct 466 ms 8044 KB Output is correct
4 Correct 1529 ms 15100 KB Output is correct
5 Correct 769 ms 15632 KB Output is correct
6 Correct 727 ms 15440 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 16 ms 4840 KB Output is correct
5 Correct 13 ms 4836 KB Output is correct
6 Correct 13 ms 4696 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 105 ms 10108 KB Output is correct
9 Correct 425 ms 8020 KB Output is correct
10 Correct 1387 ms 15112 KB Output is correct
11 Correct 819 ms 15444 KB Output is correct
12 Correct 777 ms 15440 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 83 ms 10280 KB Output is correct
15 Correct 80 ms 5208 KB Output is correct
16 Correct 1463 ms 15424 KB Output is correct
17 Correct 770 ms 15440 KB Output is correct
18 Correct 745 ms 15444 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 23 ms 4828 KB Output is correct
5 Correct 13 ms 4696 KB Output is correct
6 Correct 14 ms 4840 KB Output is correct
7 Correct 0 ms 2392 KB Output is correct
8 Correct 84 ms 10324 KB Output is correct
9 Correct 458 ms 8020 KB Output is correct
10 Correct 1384 ms 14956 KB Output is correct
11 Correct 742 ms 15628 KB Output is correct
12 Correct 795 ms 15648 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 83 ms 10152 KB Output is correct
15 Correct 84 ms 5212 KB Output is correct
16 Correct 1500 ms 15444 KB Output is correct
17 Correct 743 ms 15448 KB Output is correct
18 Correct 749 ms 15440 KB Output is correct
19 Execution timed out 3059 ms 93016 KB Time limit exceeded
20 Halted 0 ms 0 KB -