oj.uz

Submission #761254

# Submission time Handle Problem Language Result Execution time Memory
761254 2023-06-19T12:03:40 Z coloboxx Wall (IOI14_wall) C++17
61 / 100
 3000 ms 217488 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 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;
// }

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 106964 KB Output is correct
2 Correct 57 ms 107092 KB Output is correct
3 Correct 68 ms 107044 KB Output is correct
4 Correct 70 ms 107716 KB Output is correct
5 Correct 69 ms 107544 KB Output is correct
6 Correct 70 ms 107604 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 106972 KB Output is correct
2 Correct 181 ms 122728 KB Output is correct
3 Correct 259 ms 128228 KB Output is correct
4 Correct 918 ms 166448 KB Output is correct
5 Correct 399 ms 135388 KB Output is correct
6 Correct 377 ms 133636 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 106956 KB Output is correct
2 Correct 68 ms 107080 KB Output is correct
3 Correct 58 ms 107064 KB Output is correct
4 Correct 69 ms 107756 KB Output is correct
5 Correct 68 ms 107652 KB Output is correct
6 Correct 74 ms 107592 KB Output is correct
7 Correct 60 ms 106944 KB Output is correct
8 Correct 180 ms 122764 KB Output is correct
9 Correct 278 ms 128208 KB Output is correct
10 Correct 870 ms 166524 KB Output is correct
11 Correct 411 ms 135496 KB Output is correct
12 Correct 384 ms 133596 KB Output is correct
13 Correct 59 ms 106956 KB Output is correct
14 Correct 187 ms 122816 KB Output is correct
15 Correct 101 ms 110656 KB Output is correct
16 Correct 1058 ms 166804 KB Output is correct
17 Correct 349 ms 133836 KB Output is correct
18 Correct 343 ms 133700 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 106956 KB Output is correct
2 Correct 64 ms 107172 KB Output is correct
3 Correct 59 ms 107092 KB Output is correct
4 Correct 69 ms 107772 KB Output is correct
5 Correct 68 ms 107564 KB Output is correct
6 Correct 72 ms 107596 KB Output is correct
7 Correct 61 ms 106932 KB Output is correct
8 Correct 186 ms 122868 KB Output is correct
9 Correct 268 ms 128200 KB Output is correct
10 Correct 889 ms 166456 KB Output is correct
11 Correct 383 ms 135464 KB Output is correct
12 Correct 379 ms 133600 KB Output is correct
13 Correct 58 ms 106956 KB Output is correct
14 Correct 191 ms 122740 KB Output is correct
15 Correct 100 ms 110724 KB Output is correct
16 Correct 1016 ms 166880 KB Output is correct
17 Correct 345 ms 133884 KB Output is correct
18 Correct 379 ms 133800 KB Output is correct
19 Execution timed out 3074 ms 217488 KB Time limit exceeded
20 Halted 0 ms 0 KB -