oj.uz

Submission #761222

# Submission time Handle Problem Language Result Execution time Memory
761222 2023-06-19T11:17:37 Z coloboxx Wall (IOI14_wall) C++17
61 / 100
 3000 ms 202644 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]);
      }
 
      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;
      }
};

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 52 ms 106904 KB Output is correct
2 Correct 53 ms 107028 KB Output is correct
3 Correct 54 ms 107028 KB Output is correct
4 Correct 64 ms 107648 KB Output is correct
5 Correct 64 ms 107560 KB Output is correct
6 Correct 64 ms 107472 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 106964 KB Output is correct
2 Correct 182 ms 116972 KB Output is correct
3 Correct 313 ms 124372 KB Output is correct
4 Correct 1010 ms 156800 KB Output is correct
5 Correct 401 ms 125340 KB Output is correct
6 Correct 393 ms 125116 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 106968 KB Output is correct
2 Correct 54 ms 107084 KB Output is correct
3 Correct 55 ms 107004 KB Output is correct
4 Correct 64 ms 107656 KB Output is correct
5 Correct 64 ms 107440 KB Output is correct
6 Correct 64 ms 107544 KB Output is correct
7 Correct 54 ms 106956 KB Output is correct
8 Correct 185 ms 116924 KB Output is correct
9 Correct 305 ms 124384 KB Output is correct
10 Correct 986 ms 156896 KB Output is correct
11 Correct 416 ms 125352 KB Output is correct
12 Correct 404 ms 125012 KB Output is correct
13 Correct 54 ms 106992 KB Output is correct
14 Correct 186 ms 116992 KB Output is correct
15 Correct 99 ms 110100 KB Output is correct
16 Correct 1210 ms 157252 KB Output is correct
17 Correct 364 ms 124804 KB Output is correct
18 Correct 372 ms 124652 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 106920 KB Output is correct
2 Correct 52 ms 107084 KB Output is correct
3 Correct 61 ms 107072 KB Output is correct
4 Correct 82 ms 107644 KB Output is correct
5 Correct 61 ms 107516 KB Output is correct
6 Correct 61 ms 107508 KB Output is correct
7 Correct 57 ms 106988 KB Output is correct
8 Correct 197 ms 117000 KB Output is correct
9 Correct 315 ms 124456 KB Output is correct
10 Correct 1022 ms 156816 KB Output is correct
11 Correct 407 ms 125320 KB Output is correct
12 Correct 404 ms 125264 KB Output is correct
13 Correct 54 ms 106944 KB Output is correct
14 Correct 186 ms 117000 KB Output is correct
15 Correct 102 ms 110160 KB Output is correct
16 Correct 1229 ms 157248 KB Output is correct
17 Correct 350 ms 124824 KB Output is correct
18 Correct 358 ms 124728 KB Output is correct
19 Execution timed out 3082 ms 202644 KB Time limit exceeded
20 Halted 0 ms 0 KB -