oj.uz

Submission #959642

# Submission time Handle Problem Language Result Execution time Memory
959642 2024-04-08T14:52:52 Z vjudge1 Wall (IOI14_wall) C++17
32 / 100
 3000 ms 19216 KB 
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e6, inf = INT_MAX;
 
struct node {
  int mx, mn;
};
 
int n, lazMx[N*4], lazMn[N*4];
node seg[N*4];
 
void build(int p=1, int l=0, int r=n-1) {
  if (l == r) {
    seg[p].mx = 0;
    seg[p].mn = 0;
    return;
  }
  int mid = (l+r) >> 1;
  seg[p].mx = seg[p].mn = 0;
}
 
void updateMx(int a, int b, int c, int p=1, int l=0, int r=n-1) {
  if (seg[p].mn >= c) return;
  else if (l == r) {
    seg[p].mx = max(seg[p].mx, c);
    seg[p].mn = max(seg[p].mn, c); 
    return;
  }
  int mid = (l+r) >> 1;
  if (a <= mid) updateMx(a, b, c, p*2, l, mid);
  if (mid+1 <= b) updateMx(a, b, c, p*2+1, mid+1, r);
  seg[p].mx = max(seg[p*2].mx, seg[p*2+1].mx);
  seg[p].mn = min(seg[p*2].mn, seg[p*2+1].mn);
}
 
void updateMn(int a, int b, int c, int p=1, int l=0, int r=n-1) {
  if (seg[p].mx <= c) return;
  else if (l == r) {
    seg[p].mx = min(seg[p].mx, c);
    seg[p].mn = min(seg[p].mn, c); 
    return;
  }
  int mid = (l+r) >> 1;
  if (a <= mid) updateMn(a, b, c, p*2, l, mid);
  if (mid+1 <= b) updateMn(a, b, c, p*2+1, mid+1, r);
  seg[p].mx = max(seg[p*2].mx, seg[p*2+1].mx);
  seg[p].mn = min(seg[p*2].mn, seg[p*2+1].mn);
}
 
int query(int a, int p=1, int l=0, int r=n-1) {
  if (l == r) {
    return seg[p].mx;
  }
  //pushDown(p);
  int mid = (l+r) >> 1;
  if (a <= mid) return query(a, p*2, l, mid);
  else return query(a, p*2+1, mid+1, r);
}
 
void buildWall(int NN, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  n = NN;
 
  build();
  for (int i = 0; i < k; i++) {
    if (op[i] == 1) updateMx(left[i], right[i], height[i]);
    else updateMn(left[i], right[i], height[i]);
  }
 
  for (int i = 0; i < n; i++) {
    finalHeight[i] = query(i);
  }
}

Compilation message

wall.cpp: In function 'void build(int, int, int)':
wall.cpp:22:7: warning: unused variable 'mid' [-Wunused-variable]
   22 |   int mid = (l+r) >> 1;
      |       ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 444 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 68 ms 896 KB Output is correct
5 Correct 146 ms 856 KB Output is correct
6 Correct 126 ms 860 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 120 ms 13288 KB Output is correct
3 Correct 59 ms 6736 KB Output is correct
4 Correct 195 ms 18516 KB Output is correct
5 Correct 142 ms 19216 KB Output is correct
6 Correct 149 ms 18320 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 68 ms 880 KB Output is correct
5 Correct 129 ms 1104 KB Output is correct
6 Correct 128 ms 1112 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 111 ms 12720 KB Output is correct
9 Correct 59 ms 7248 KB Output is correct
10 Correct 162 ms 18448 KB Output is correct
11 Correct 149 ms 19184 KB Output is correct
12 Correct 149 ms 18300 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 120 ms 12872 KB Output is correct
15 Correct 752 ms 2000 KB Output is correct
16 Execution timed out 3095 ms 17868 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 576 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 70 ms 900 KB Output is correct
5 Correct 140 ms 856 KB Output is correct
6 Correct 131 ms 880 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 112 ms 12880 KB Output is correct
9 Correct 59 ms 7204 KB Output is correct
10 Correct 164 ms 18360 KB Output is correct
11 Correct 152 ms 19164 KB Output is correct
12 Correct 148 ms 18256 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 114 ms 12736 KB Output is correct
15 Correct 709 ms 2000 KB Output is correct
16 Execution timed out 3018 ms 17884 KB Time limit exceeded
17 Halted 0 ms 0 KB -