제출 #761214

#제출 시각아이디문제언어결과실행 시간메모리
761214coloboxx벽 (IOI14_wall)C++17
61 / 100
1273 ms93240 KiB
// #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);
      |                             ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...