oj.uz

Submission #761214

# Submission time Handle Problem Language Result Execution time Memory
761214 2023-06-19T11:12:23 Z coloboxx Wall (IOI14_wall) C++17
61 / 100
 1273 ms 93240 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 << 18;
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 17 ms 33108 KB Output is correct
2 Correct 18 ms 33232 KB Output is correct
3 Correct 18 ms 33236 KB Output is correct
4 Correct 29 ms 33788 KB Output is correct
5 Correct 29 ms 33672 KB Output is correct
6 Correct 28 ms 33640 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33072 KB Output is correct
2 Correct 135 ms 43132 KB Output is correct
3 Correct 289 ms 50620 KB Output is correct
4 Correct 1163 ms 91916 KB Output is correct
5 Correct 411 ms 61944 KB Output is correct
6 Correct 408 ms 60132 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 33108 KB Output is correct
2 Correct 19 ms 33228 KB Output is correct
3 Correct 19 ms 33240 KB Output is correct
4 Correct 29 ms 33808 KB Output is correct
5 Correct 29 ms 33632 KB Output is correct
6 Correct 29 ms 33644 KB Output is correct
7 Correct 17 ms 33108 KB Output is correct
8 Correct 142 ms 43080 KB Output is correct
9 Correct 291 ms 50664 KB Output is correct
10 Correct 1178 ms 91984 KB Output is correct
11 Correct 416 ms 62148 KB Output is correct
12 Correct 401 ms 60236 KB Output is correct
13 Correct 18 ms 33108 KB Output is correct
14 Correct 141 ms 48880 KB Output is correct
15 Correct 71 ms 36740 KB Output is correct
16 Correct 1266 ms 92268 KB Output is correct
17 Correct 356 ms 60264 KB Output is correct
18 Correct 356 ms 60160 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33108 KB Output is correct
2 Correct 19 ms 33252 KB Output is correct
3 Correct 19 ms 33180 KB Output is correct
4 Correct 29 ms 33800 KB Output is correct
5 Correct 28 ms 33620 KB Output is correct
6 Correct 30 ms 33636 KB Output is correct
7 Correct 17 ms 33108 KB Output is correct
8 Correct 135 ms 43072 KB Output is correct
9 Correct 298 ms 50620 KB Output is correct
10 Correct 1117 ms 92004 KB Output is correct
11 Correct 421 ms 62028 KB Output is correct
12 Correct 405 ms 60236 KB Output is correct
13 Correct 18 ms 33028 KB Output is correct
14 Correct 146 ms 48964 KB Output is correct
15 Correct 71 ms 36740 KB Output is correct
16 Correct 1273 ms 92268 KB Output is correct
17 Correct 357 ms 60360 KB Output is correct
18 Correct 361 ms 60316 KB Output is correct
19 Runtime error 162 ms 93240 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -