oj.uz

Submission #1009193

# Submission time Handle Problem Language Result Execution time Memory
1009193 2024-06-27T09:52:30 Z SonicML Wall (IOI14_wall) C++14
0 / 100
 3000 ms 14048 KB 
#include <iostream>
#include <vector>
#include "wall.h"

using namespace std;

int const INF = 1e5;

struct Node {
  int minn;
  int maxx;
};

Node combineNode(Node a, Node b) {
  Node c;
  c.minn = min(b.maxx, max(a.minn, b.minn));
  c.maxx = max(b.minn, min(a.maxx, b.maxx));
  return c;
}

struct SegmentTree {
  vector <Node> seg;

  SegmentTree(int n) {
    seg.resize(1 + 4 * n);
    for(int i = 1;i <= 4 * n;i++) {
      seg[i] = {0, INF};
    }
  }

  void cleanNode(int node, int from, int to) {
    if(from != to) {
      seg[node * 2] = combineNode(seg[node * 2], seg[node]);
      seg[node * 2 + 1] = combineNode(seg[node * 2 + 1], seg[node]);
      seg[node] = {0, INF};
    }
  }

  void update(int node, int from, int to, int x, int y, Node add) {
    if(from == x && to == y) {
      seg[node] = combineNode(seg[node], add);
      cleanNode(node, from, to);
    } else {
      int mid = (from + to) / 2;
      cleanNode(node * 2, from, mid);
      cleanNode(node * 2 + 1, mid+1, to);
      if(y <= mid) {
        update(node * 2, from, mid, x, y, add);
      } else if(mid < x) {
        update(node * 2 + 1, mid+1, to, x, y, add);
      } else {
        update(node * 2, from, mid, x, mid, add);
        update(node * 2 + 1, mid+1, to, mid+1, y, add);
      }
    }
  }

  Node query(int node, int from, int to, int x) {
    cleanNode(node, from, to);
    if(from == to) {
      return seg[node];
    } else {
      int mid = (from + to) / 2;
      if(x <= mid) {
        return query(node*2, from, mid, x);
      } else {
        return query(node*2+1, mid+1, to, x); 
      }
    }
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  SegmentTree seg(n);
  seg.update(1, 1, n, 1, n, {0, 0});
  for(int j = 1;j <= n;j++) {
    Node print = seg.query(1, 1, n, j);
  }
  for(int i = 0;i < k;i++) {
    int x = left[i]+1, y = right[i]+1;
    Node add;
    if(op[i] == 1) {
      add = {height[i], INF};
    } else {
      add = {0, height[i]};
    }
    seg.update(1, 1, n, x, y, add);
    for(int j = 1;j <= n;j++) {
      Node print = seg.query(1, 1, n, j);
    }
  }
  for(int i = 0;i < n;i++) {
    finalHeight[i] = seg.query(1, 1, n, i+1).minn;
  }
  return;
}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:77:10: warning: variable 'print' set but not used [-Wunused-but-set-variable]
   77 |     Node print = seg.query(1, 1, n, j);
      |          ^~~~~
wall.cpp:89:12: warning: variable 'print' set but not used [-Wunused-but-set-variable]
   89 |       Node print = seg.query(1, 1, n, j);
      |            ^~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 21 ms 604 KB Output is correct
4 Execution timed out 3058 ms 860 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 76 ms 14048 KB Output is correct
3 Execution timed out 3063 ms 8020 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 23 ms 448 KB Output is correct
4 Execution timed out 3066 ms 860 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 20 ms 500 KB Output is correct
4 Execution timed out 3060 ms 856 KB Time limit exceeded
5 Halted 0 ms 0 KB -