oj.uz

Submission #761216

# Submission time Handle Problem Language Result Execution time Memory
761216 2023-06-19T11:13:09 Z coloboxx Wall (IOI14_wall) C++17
61 / 100
 1371 ms 262144 KB 
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx,avx2,sse2,sse3,ssse3,sse4,lzcnt,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define ll long long
#define point pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define show(x) cerr << (#x) << " = " << x << '\n'
#define print(x) if (1) {cerr << (#x) << " = "; for (auto it : x) \
      cerr << it << ' '; cerr << '\n';}
#define fast_io ios_base::sync_with_stdio(0), cin.tie(0)

const int N = 1 << 21;
const int K = 1 << 19;
const int S = 1e7 + 64;
const int INF = 2e9 + 64;
const ll MAX = 2e18 + 64;
const int LOG = 21;
const int MOD = 1e9 + 7; //998244353;
const int P = 79;

using namespace std;

vector<int> t[4 * N];

template <class T, T (*F) (T, T)>
struct segtree{
      int n;
      T def{};
      vector<T> t;
 
      segtree(int n, T def, vector<T> v = {}) : n(n), def(def) {
            t.assign(2 * n, def);

            for (int i = 0; i < min(n, (int)v.size()); ++i)
                  t[i + n] = v[i];

            for (int i = n - 1; i > 0; --i)
                  t[i] = F(t[i << 1], t[i << 1 | 1]);
      }
 
      void update(int p, T val) {
            for (t[p += n] = val; p > 1; p >>= 1)
                  t[p >> 1] = F(t[p], t[p ^ 1]);
      }

      T query(int l, int r) {
            T res = def;
            for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
                  if (l & 1) res = F(res, t[l++]);
                  if (r & 1) res = F(res, t[--r]);
            }
            return res;
      }
};

void add_segment(int v, int tl, int tr, int l, int r, int id) {
      if (max(l, tl) > min(r, tr))
            return;

      if (l <= tl && r >= tr) {
            t[v].pb(id); return;
      }

      int tm = (tl + tr) >> 1;
      add_segment(v << 1, tl, tm, l, r, id);
      add_segment(v << 1 | 1, tm + 1, tr, l, r, id);
}

int Min(int x, int y) { 
      return min(x, y);
}

int Max(int x, int y) {
      return max(x, y);
}

segtree<int, &Min> tmin(K, INF);
segtree<int, &Max> tmax(K, -INF);

int norm(int l, int r, int x) {
      if (x < l) return l;
      if (x > r) return r;
      return x;
}

int n, k;

void dfs(int v, int tl, int tr, int mx_id, int o[], int h[], int ans[]) {
      // show(v);
      for (auto id : t[v]) {
            mx_id = max(mx_id, id);
            if (o[id] == 2)
                  tmin.update(id, h[id]);
            else
                  tmax.update(id, h[id]);
      }

      if (tl == tr) {
            if (mx_id == -INF) {
                  ans[tl] = 0;
            }
            else {
                  int lb = -1, rb = mx_id;

                  while (lb + 1 < rb) {
                        int mid = (lb + rb) >> 1;

                        int l = tmax.query(mid, mx_id);
                        int r = tmin.query(mid, mx_id);

                        (l <= r ? rb : lb) = mid;
                  }

                  int pos = rb;
                  int l = tmax.query(pos, mx_id);
                  int r = tmin.query(pos, mx_id);

                  // show(l), show(r);

                  if (pos == 0)
                        ans[tl] = norm(l, r, 0);
                  else {
                        int pl = tmax.query(pos - 1, pos - 1);
                        int pr = tmin.query(pos - 1, pos - 1);

                        // if (max(l, pl) <= min(r, pr))
                        //       exit(0);
                        // show(pl), show(pr);

                        if (pr < l)
                              ans[tl] = l;
                        else
                              ans[tl] = r;
                  }
                  //cerr << "BBB\n";
            }

            // for (int j = 0; j < k; ++j)
            //       cerr << "{" << tmax.query(j, j) << ", " << tmin.query(j, j) << "}\n";
      }
      else {
            int tm = (tl + tr) >> 1;
            dfs(v << 1, tl, tm, mx_id, o, h, ans);
            dfs(v << 1 | 1, tm + 1, tr, mx_id, o, h, ans);
      }

      for (int id : t[v]) {
            if (o[id] == 2)
                  tmin.update(id, INF);
            else
                  tmax.update(id, -INF);
      }
}

void buildWall(int _n, int _k, int op[], int left[], int right[], int height[], int finalHeight[]) {
      n = _n, k = _k;

      for (int i = 0; i < k; ++i)
            add_segment(1, 0, n - 1, left[i], right[i], i);

      dfs(1, 0, n - 1, -INF, op, height, finalHeight);
}

#include "wall.h"

// int main()
// {
//       int n;
//       int k;

//       // for (int i = 0; i < 10; ++i)
//       //     show(tmin.query(i, i));
//       //     show(tmin.def);

//       int i, j;  
//       int status = 0;

//       status = scanf("%d%d", &n, &k);
//       assert(status == 2);

//       int* op = (int*)calloc(sizeof(int), k);
//       int* left = (int*)calloc(sizeof(int), k);
//       int* right = (int*)calloc(sizeof(int), k);
//       int* height = (int*)calloc(sizeof(int), k);
//       int* finalHeight = (int*)calloc(sizeof(int), n);

//       for (i = 0; i < k; i++){
//       status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
//       assert(status == 4);
//       }

//       buildWall(n, k, op, left, right, height, finalHeight);

//       for (j = 0; j < n; j++)
//       printf("%d\n", finalHeight[j]);

//       return 0;
// }

Compilation message

wall.cpp: In function 'void dfs(int, int, int, int, int*, int*, int*)':
wall.cpp:130:29: warning: unused variable 'pl' [-Wunused-variable]
  130 |                         int pl = tmax.query(pos - 1, pos - 1);
      |                             ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 205452 KB Output is correct
2 Correct 92 ms 205584 KB Output is correct
3 Correct 93 ms 205532 KB Output is correct
4 Correct 105 ms 206152 KB Output is correct
5 Correct 103 ms 205972 KB Output is correct
6 Correct 102 ms 206036 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 205464 KB Output is correct
2 Correct 208 ms 215488 KB Output is correct
3 Correct 363 ms 223048 KB Output is correct
4 Correct 1279 ms 254644 KB Output is correct
5 Correct 484 ms 224108 KB Output is correct
6 Correct 475 ms 223972 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 205372 KB Output is correct
2 Correct 96 ms 205532 KB Output is correct
3 Correct 94 ms 205492 KB Output is correct
4 Correct 105 ms 206208 KB Output is correct
5 Correct 107 ms 206112 KB Output is correct
6 Correct 103 ms 206032 KB Output is correct
7 Correct 92 ms 205388 KB Output is correct
8 Correct 212 ms 215524 KB Output is correct
9 Correct 387 ms 223124 KB Output is correct
10 Correct 1234 ms 254656 KB Output is correct
11 Correct 478 ms 224204 KB Output is correct
12 Correct 477 ms 223956 KB Output is correct
13 Correct 95 ms 205388 KB Output is correct
14 Correct 213 ms 215488 KB Output is correct
15 Correct 145 ms 208588 KB Output is correct
16 Correct 1371 ms 255184 KB Output is correct
17 Correct 427 ms 223620 KB Output is correct
18 Correct 436 ms 223564 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 205432 KB Output is correct
2 Correct 96 ms 205616 KB Output is correct
3 Correct 97 ms 205564 KB Output is correct
4 Correct 111 ms 206180 KB Output is correct
5 Correct 107 ms 206008 KB Output is correct
6 Correct 106 ms 205944 KB Output is correct
7 Correct 92 ms 205412 KB Output is correct
8 Correct 211 ms 215468 KB Output is correct
9 Correct 363 ms 223008 KB Output is correct
10 Correct 1205 ms 254848 KB Output is correct
11 Correct 483 ms 224140 KB Output is correct
12 Correct 473 ms 223936 KB Output is correct
13 Correct 96 ms 205372 KB Output is correct
14 Correct 214 ms 215488 KB Output is correct
15 Correct 146 ms 208588 KB Output is correct
16 Correct 1337 ms 255072 KB Output is correct
17 Correct 432 ms 223688 KB Output is correct
18 Correct 450 ms 223632 KB Output is correct
19 Runtime error 337 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -