oj.uz

Submission #1104267

# Submission time Handle Problem Language Result Execution time Memory
1104267 2024-10-23T11:09:18 Z vjudge1 Wall (IOI14_wall) C++14
100 / 100
 565 ms 110764 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
struct node{
  int mi;
  node() : mi(0) {}
}sg[8000005];
int lazy1[8000005],lazy2[8000005];
void push(int u,int l,int r)
{
  if(lazy1[u]!=-1)
  {
    sg[u].mi = max(sg[u].mi,lazy1[u]);
    if(l!=r)
    {
      lazy1[2*u] = max(lazy1[2*u],lazy1[u]);
      lazy2[2*u] = max(lazy2[2*u],lazy1[u]);
  
      lazy1[2*u+1] = max(lazy1[2*u+1],lazy1[u]);
      lazy2[2*u+1] = max(lazy2[2*u+1],lazy1[u]); 
        
    }
    lazy1[u] = -1;  
  }
  if(lazy2[u]!=2e9)
  {
    sg[u].mi = min(sg[u].mi,lazy2[u]);
    if(l!=r)
    {
      lazy1[2*u] = min(lazy1[2*u],lazy2[u]);
      lazy2[2*u] = min(lazy2[2*u],lazy2[u]);

      lazy1[2*u+1] = min(lazy1[2*u+1],lazy2[u]);
      lazy2[2*u+1] = min(lazy2[2*u+1],lazy2[u]);
          
    }
    lazy2[u] = 2e9; 
  }
   
}


void update_max(int u,int l,int r,int sl,int sr ,int x)
{
  push(u,l,r);
  if(l>r or l>sr or r<sl) return;
  if(sl<=l and r<=sr) 
  {

    lazy1[u] = x;
    push(u,l,r);
    return;
  }
  int m=(l+r)/2;
  update_max(2*u,l,m,sl,sr,x);
  update_max(2*u+1,m+1,r,sl,sr,x);
}
void update_min(int u,int l,int r,int sl,int sr ,int x)
{
  push(u,l,r);
  if(l>r or l>sr or r<sl) return;
  if(sl<=l and r<=sr)
  {
    lazy2[u] = x;
    push(u,l,r);
    return;
  }
  int m=(l+r)/2;
  update_min(2*u,l,m,sl,sr,x);
  update_min(2*u+1,m+1,r,sl,sr,x);
}
int ans[8000005];
void query(int u,int l,int r)
{
  push(u,l,r);
  if(r<l) return;
  if(l==r)
  {
    ans[l-1] = sg[u].mi;
    return ;
  }
  int m=(l+r)/2;
  query(2*u,l,m);
  query(2*u+1,m+1,r);
  
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for(int i=0;i<k;i++)
  {
    if(op[i]==1)
    {
      update_max(1,1,n,left[i]+1,right[i]+1,height[i]);
    }
    else
    {
      update_min(1,1,n,left[i]+1,right[i]+1,height[i]);
    }
    
  }
  query(1,1,n);
  
  for(int i=0;i<n;i++) finalHeight[i]=ans[i];
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33104 KB Output is correct
2 Correct 6 ms 33304 KB Output is correct
3 Correct 7 ms 33360 KB Output is correct
4 Correct 10 ms 33616 KB Output is correct
5 Correct 8 ms 33736 KB Output is correct
6 Correct 9 ms 33664 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33104 KB Output is correct
2 Correct 91 ms 46220 KB Output is correct
3 Correct 137 ms 40784 KB Output is correct
4 Correct 417 ms 51784 KB Output is correct
5 Correct 205 ms 52040 KB Output is correct
6 Correct 197 ms 49788 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33104 KB Output is correct
2 Correct 6 ms 33248 KB Output is correct
3 Correct 6 ms 33104 KB Output is correct
4 Correct 10 ms 33616 KB Output is correct
5 Correct 9 ms 33784 KB Output is correct
6 Correct 9 ms 33556 KB Output is correct
7 Correct 5 ms 33104 KB Output is correct
8 Correct 97 ms 46664 KB Output is correct
9 Correct 154 ms 40520 KB Output is correct
10 Correct 422 ms 54840 KB Output is correct
11 Correct 246 ms 56396 KB Output is correct
12 Correct 218 ms 53064 KB Output is correct
13 Correct 5 ms 33104 KB Output is correct
14 Correct 93 ms 44256 KB Output is correct
15 Correct 30 ms 34376 KB Output is correct
16 Correct 536 ms 54020 KB Output is correct
17 Correct 220 ms 50872 KB Output is correct
18 Correct 232 ms 54600 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33272 KB Output is correct
2 Correct 6 ms 33104 KB Output is correct
3 Correct 6 ms 33360 KB Output is correct
4 Correct 13 ms 33616 KB Output is correct
5 Correct 9 ms 33692 KB Output is correct
6 Correct 9 ms 33616 KB Output is correct
7 Correct 5 ms 33276 KB Output is correct
8 Correct 100 ms 46152 KB Output is correct
9 Correct 149 ms 40776 KB Output is correct
10 Correct 419 ms 50000 KB Output is correct
11 Correct 214 ms 55880 KB Output is correct
12 Correct 222 ms 54760 KB Output is correct
13 Correct 6 ms 33104 KB Output is correct
14 Correct 105 ms 46648 KB Output is correct
15 Correct 35 ms 34752 KB Output is correct
16 Correct 521 ms 54788 KB Output is correct
17 Correct 217 ms 55112 KB Output is correct
18 Correct 236 ms 54208 KB Output is correct
19 Correct 518 ms 100500 KB Output is correct
20 Correct 503 ms 107848 KB Output is correct
21 Correct 490 ms 110764 KB Output is correct
22 Correct 499 ms 97608 KB Output is correct
23 Correct 565 ms 107280 KB Output is correct
24 Correct 544 ms 107080 KB Output is correct
25 Correct 524 ms 97744 KB Output is correct
26 Correct 537 ms 110664 KB Output is correct
27 Correct 521 ms 101212 KB Output is correct
28 Correct 555 ms 108104 KB Output is correct
29 Correct 516 ms 97812 KB Output is correct
30 Correct 540 ms 97608 KB Output is correct