oj.uz

Submission #1104269

# Submission time Handle Problem Language Result Execution time Memory
1104269 2024-10-23T11:15:03 Z vjudge1 Wall (IOI14_wall) C++14
100 / 100
 584 ms 100252 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 33264 KB Output is correct
3 Correct 6 ms 33104 KB Output is correct
4 Correct 10 ms 33616 KB Output is correct
5 Correct 8 ms 33540 KB Output is correct
6 Correct 9 ms 33608 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33104 KB Output is correct
2 Correct 88 ms 40776 KB Output is correct
3 Correct 143 ms 37096 KB Output is correct
4 Correct 389 ms 45640 KB Output is correct
5 Correct 195 ms 46152 KB Output is correct
6 Correct 209 ms 46292 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 33228 KB Output is correct
3 Correct 6 ms 33104 KB Output is correct
4 Correct 10 ms 33552 KB Output is correct
5 Correct 10 ms 33616 KB Output is correct
6 Correct 10 ms 33616 KB Output is correct
7 Correct 6 ms 32988 KB Output is correct
8 Correct 98 ms 40936 KB Output is correct
9 Correct 163 ms 37100 KB Output is correct
10 Correct 425 ms 45880 KB Output is correct
11 Correct 218 ms 46300 KB Output is correct
12 Correct 231 ms 46152 KB Output is correct
13 Correct 6 ms 33104 KB Output is correct
14 Correct 102 ms 40908 KB Output is correct
15 Correct 33 ms 34376 KB Output is correct
16 Correct 521 ms 46132 KB Output is correct
17 Correct 225 ms 45900 KB Output is correct
18 Correct 222 ms 45996 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33104 KB Output is correct
2 Correct 7 ms 33104 KB Output is correct
3 Correct 7 ms 33104 KB Output is correct
4 Correct 11 ms 33616 KB Output is correct
5 Correct 9 ms 33616 KB Output is correct
6 Correct 9 ms 33632 KB Output is correct
7 Correct 6 ms 33116 KB Output is correct
8 Correct 97 ms 40784 KB Output is correct
9 Correct 147 ms 37080 KB Output is correct
10 Correct 422 ms 45876 KB Output is correct
11 Correct 219 ms 46152 KB Output is correct
12 Correct 229 ms 46152 KB Output is correct
13 Correct 6 ms 33104 KB Output is correct
14 Correct 99 ms 40776 KB Output is correct
15 Correct 33 ms 34188 KB Output is correct
16 Correct 528 ms 46032 KB Output is correct
17 Correct 222 ms 46040 KB Output is correct
18 Correct 223 ms 45872 KB Output is correct
19 Correct 584 ms 100136 KB Output is correct
20 Correct 529 ms 97804 KB Output is correct
21 Correct 496 ms 100168 KB Output is correct
22 Correct 489 ms 97828 KB Output is correct
23 Correct 496 ms 97604 KB Output is correct
24 Correct 530 ms 97612 KB Output is correct
25 Correct 548 ms 97608 KB Output is correct
26 Correct 546 ms 100168 KB Output is correct
27 Correct 554 ms 100252 KB Output is correct
28 Correct 546 ms 97744 KB Output is correct
29 Correct 574 ms 97776 KB Output is correct
30 Correct 555 ms 97608 KB Output is correct