oj.uz

Submission #761226

# Submission time Handle Problem Language Result Execution time Memory
761226 2023-06-19T11:19:28 Z coloboxx Wall (IOI14_wall) C++17
61 / 100
 3000 ms 207012 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[2 * 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]);
      }
 
      inline void update(int p, T val) {
            for (t[p += n] = val; p > 1; p >>= 1)
                  t[p >> 1] = F(t[p], t[p ^ 1]);
      }

      inline 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;
      }
};

int n, k;

void add_segment(int v, int tl, int tr, int l, int r, int id) {
      for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) t[l].pb(id), ++l;
            if (r & 1) --r, t[r].pb(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;
}


void dfs(int v, 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 (v >= n) {
            int tl = v - n;
            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 {
            dfs(v << 1, mx_id, o, h, ans);
            dfs(v << 1 | 1, 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, -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*)':
wall.cpp:126:29: warning: unused variable 'pl' [-Wunused-variable]
  126 |                         int pl = tmax.query(pos - 1, pos - 1);
      |                             ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 106988 KB Output is correct
2 Correct 55 ms 107112 KB Output is correct
3 Correct 57 ms 107016 KB Output is correct
4 Correct 64 ms 107584 KB Output is correct
5 Correct 71 ms 107576 KB Output is correct
6 Correct 67 ms 107508 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 106964 KB Output is correct
2 Correct 175 ms 117000 KB Output is correct
3 Correct 246 ms 124360 KB Output is correct
4 Correct 944 ms 156876 KB Output is correct
5 Correct 386 ms 125244 KB Output is correct
6 Correct 374 ms 125184 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 106952 KB Output is correct
2 Correct 58 ms 107124 KB Output is correct
3 Correct 59 ms 107112 KB Output is correct
4 Correct 66 ms 107688 KB Output is correct
5 Correct 67 ms 107512 KB Output is correct
6 Correct 72 ms 107576 KB Output is correct
7 Correct 58 ms 106968 KB Output is correct
8 Correct 177 ms 116944 KB Output is correct
9 Correct 257 ms 124408 KB Output is correct
10 Correct 840 ms 156844 KB Output is correct
11 Correct 392 ms 125324 KB Output is correct
12 Correct 390 ms 125056 KB Output is correct
13 Correct 57 ms 106892 KB Output is correct
14 Correct 183 ms 116928 KB Output is correct
15 Correct 100 ms 110164 KB Output is correct
16 Correct 954 ms 157248 KB Output is correct
17 Correct 337 ms 124856 KB Output is correct
18 Correct 338 ms 124744 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 106948 KB Output is correct
2 Correct 58 ms 107052 KB Output is correct
3 Correct 61 ms 107000 KB Output is correct
4 Correct 69 ms 107608 KB Output is correct
5 Correct 76 ms 107740 KB Output is correct
6 Correct 70 ms 107480 KB Output is correct
7 Correct 59 ms 106908 KB Output is correct
8 Correct 177 ms 116904 KB Output is correct
9 Correct 263 ms 124444 KB Output is correct
10 Correct 864 ms 156800 KB Output is correct
11 Correct 379 ms 125264 KB Output is correct
12 Correct 376 ms 125212 KB Output is correct
13 Correct 62 ms 106932 KB Output is correct
14 Correct 184 ms 117020 KB Output is correct
15 Correct 100 ms 110148 KB Output is correct
16 Correct 1018 ms 157144 KB Output is correct
17 Correct 336 ms 124868 KB Output is correct
18 Correct 340 ms 124692 KB Output is correct
19 Execution timed out 3069 ms 207012 KB Time limit exceeded
20 Halted 0 ms 0 KB -