oj.uz

Submission #765511

# Submission time Handle Problem Language Result Execution time Memory
765511 2023-06-24T16:22:43 Z emad234 Wall (IOI14_wall) C++17
8 / 100
 3000 ms 13920 KB 
#include <bits/stdc++.h>
#define aint(v) ((v).bvin(),(v).end())
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int mxN = 8e6 + 1;
int seg[mxN],lazyMx[mxN],lazyMn[mxN];
int N,s,e,val;
void spread(int l,int r, int ind){
  if(l != r){
    seg[ind * 2] = max(seg[ind * 2],lazyMx[ind]);
    seg[ind * 2] = min(seg[ind * 2],lazyMn[ind]);
    lazyMx[ind * 2] = max(lazyMx[ind * 2],lazyMx[ind]);
    lazyMn[ind * 2] = min(lazyMn[ind * 2],lazyMn[ind]);
    seg[ind * 2 + 1] = max(seg[ind * 2 + 1],lazyMx[ind]);
    seg[ind * 2 + 1] = min(seg[ind * 2 + 1],lazyMn[ind]);
    lazyMx[ind * 2 + 1] = max(lazyMx[ind * 2 + 1],lazyMx[ind]);
    lazyMn[ind * 2 + 1] = min(lazyMn[ind * 2 + 1],lazyMn[ind]);
  }
  lazyMn[ind] = 1e9;
  lazyMx[ind] = 0;
}
void updateMn(int l = 1,int r = N,int ind = 1){
  if(l > e || r < s) return;
  if(l >= s && r <= e){
    spread(l,r,ind);
    lazyMn[ind] = min(lazyMn[ind],val);
    seg[ind] = min(seg[ind],val);
    spread(l,r,ind);
    return;
  }
  int md = (l + r) / 2;
  updateMn(l,md,ind * 2);updateMn(md + 1,r,ind * 2 + 1);
}
void updateMx(int l = 1,int r = N,int ind = 1){
  if(l > e || r < s) return;
  if(l >= s && r <= e){
    spread(l,r,ind);
    lazyMx[ind] = max(lazyMx[ind],val);
    seg[ind] = max(seg[ind],val);
    spread(l,r,ind);
    return;
  }
  int md = (l + r) / 2;
  updateMx(l,md,ind * 2);updateMx(md + 1,r,ind * 2 + 1);
}
int query(int l = 1,int r = N,int ind = 1){
  spread(l,r,ind);
  if(l > e || r < s) return 0;
  if(l >= s && r <= e) {
    spread(l,r,ind);
    return seg[ind];
  }
  int md = (l + r) / 2;
  return max(query(l,md,ind * 2),query(md + 1,r,ind * 2 + 1));
}
void printseg(){
  int p2 = 1;
  for(int i = 1;i <= N;i++){
    spread(1,2,i);
    // cout<<seg[i]<<' ';
    // if(p2 * 2 - 1 == i){
    //   cout<<'\n';
    //   p2 = p2 * 2;
    // }
  }
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
  N = exp2(ceil(log2(n)));
  for(int i = 0; i<= N;i++){
    lazyMn[i] = 1e9;
  }
  for(int i = 0;i < k;i++){
    s = left[i] + 1,e = right[i] + 1;
    val = height[i];
    if(op[i] == 1){
      updateMx();
    }else{
      updateMn();
    }
    printseg();
  }
  for(int i = 0 ; i <n;i++){
    s = e = i + 1;
    finalHeight[i] = query();
  }
}
// main()
// {
//   int n;
//   int k;
// 
//   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 ", finalHeight[j]);
// 
//   return 0;
// }

Compilation message

wall.cpp: In function 'void printseg()':
wall.cpp:58:7: warning: unused variable 'p2' [-Wunused-variable]
   58 |   int p2 = 1;
      |       ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 6 ms 400 KB Output is correct
4 Correct 411 ms 888 KB Output is correct
5 Correct 406 ms 888 KB Output is correct
6 Correct 399 ms 912 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 116 ms 8808 KB Output is correct
3 Execution timed out 3092 ms 4388 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 8 ms 468 KB Output is correct
4 Correct 428 ms 888 KB Output is correct
5 Correct 408 ms 896 KB Output is correct
6 Correct 403 ms 892 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 125 ms 13892 KB Output is correct
9 Execution timed out 3071 ms 8188 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 6 ms 396 KB Output is correct
4 Correct 407 ms 896 KB Output is correct
5 Correct 413 ms 892 KB Output is correct
6 Correct 412 ms 900 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 119 ms 13920 KB Output is correct
9 Execution timed out 3074 ms 8152 KB Time limit exceeded
10 Halted 0 ms 0 KB -