oj.uz

Submission #1026715

# Submission time Handle Problem Language Result Execution time Memory
1026715 2024-07-18T09:33:49 Z dozer Wall (IOI14_wall) C++14
61 / 100
 3000 ms 88920 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<array<int, 3>> v;

  //cout<<"push : "<<l<<sp<<r<<sp<<maks[node].st<<sp<<mini[node].st<<endl;
  v.pb({maks[node].nd, maks[node].st, 1});
  v.pb({mini[node].nd, mini[node].st, 2});
  sort(v.begin(), v.end());
  vector<int> child = {LL, RR};

  for (auto i : v){
    int type = i[2], val = i[1], time = i[0];
   // cout<<"!! "<<type<<sp<<val<<sp<<time<<endl;
    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 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 5 ms 2564 KB Output is correct
4 Correct 29 ms 4920 KB Output is correct
5 Correct 25 ms 4952 KB Output is correct
6 Correct 26 ms 4908 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 90 ms 15980 KB Output is correct
3 Correct 801 ms 11816 KB Output is correct
4 Correct 2387 ms 24740 KB Output is correct
5 Correct 1445 ms 25804 KB Output is correct
6 Correct 1415 ms 24144 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 5 ms 2396 KB Output is correct
4 Correct 29 ms 4740 KB Output is correct
5 Correct 33 ms 4912 KB Output is correct
6 Correct 25 ms 4916 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 82 ms 15960 KB Output is correct
9 Correct 790 ms 11856 KB Output is correct
10 Correct 2352 ms 24740 KB Output is correct
11 Correct 1460 ms 25800 KB Output is correct
12 Correct 1381 ms 24148 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 86 ms 16028 KB Output is correct
15 Correct 154 ms 5760 KB Output is correct
16 Correct 2570 ms 25008 KB Output is correct
17 Correct 1398 ms 24308 KB Output is correct
18 Correct 1556 ms 24416 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2500 KB Output is correct
3 Correct 5 ms 2396 KB Output is correct
4 Correct 30 ms 4912 KB Output is correct
5 Correct 51 ms 4944 KB Output is correct
6 Correct 25 ms 4948 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 82 ms 15960 KB Output is correct
9 Correct 917 ms 11808 KB Output is correct
10 Correct 2655 ms 24740 KB Output is correct
11 Correct 1562 ms 25796 KB Output is correct
12 Correct 1639 ms 24232 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 86 ms 15972 KB Output is correct
15 Correct 164 ms 5760 KB Output is correct
16 Correct 2738 ms 24992 KB Output is correct
17 Correct 1514 ms 24404 KB Output is correct
18 Correct 1574 ms 24420 KB Output is correct
19 Execution timed out 3081 ms 88920 KB Time limit exceeded
20 Halted 0 ms 0 KB -