제출 #761214

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
761214		coloboxx	벽 (IOI14_wall)	C++17	61 / 100	1273 ms	93240 KiB

wall

// #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;
// }

컴파일 시 표준 에러 (stderr) 메시지

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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 0 / 39