oj.uz

Submission #782682

# Submission time Handle Problem Language Result Execution time Memory
782682 2023-07-14T07:32:21 Z Trumling Wall (IOI14_wall) C++14
100 / 100
 594 ms 193340 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std; 
 
typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
long long INF=99999999999999;
#define MOD 1000000007
#define all(x) x.begin(),x.end()


struct node
{
ll m=INF;
ll M=0;
};
ll ans[3000000];
node seg[9000000];

void lazy(int idx)
{
  seg[idx*2].m=max(seg[idx].M,seg[idx*2].m);
  seg[idx*2].M=max(seg[idx].M,seg[idx*2].M);

  seg[idx*2].m=min(seg[idx].m,seg[idx*2].m);
  seg[idx*2].M=min(seg[idx].m,seg[idx*2].M);


  seg[idx*2+1].m=max(seg[idx].M,seg[idx*2+1].m);
  seg[idx*2+1].M=max(seg[idx].M,seg[idx*2+1].M);

  seg[idx*2+1].m=min(seg[idx].m,seg[idx*2+1].m);
  seg[idx*2+1].M=min(seg[idx].m,seg[idx*2+1].M);

  seg[idx]={INF,0};

  return ;
}

void up(int l,int r,int idx,int op,ll u,int L,int  R)
{
  if(l>R || r<L)
  return ;

  if(L<=l && r<=R)
  {
    if(op==1)
    {
      seg[idx].m=max(seg[idx].m,u);
      seg[idx].M=max(seg[idx].M,u);
    }
    else
    {
      seg[idx].m=min(seg[idx].m,u);
      seg[idx].M=min(seg[idx].M,u);
    }
    return ;
  }
  lazy(idx);
  up(l,(l+r)/2,idx*2,op,u,L,R);
  up((l+r)/2+1,r,idx*2+1,op,u,L,R);
}

void fin(int l,int  r,int idx)
{
  if(l==r)
  {
    ans[l]=seg[idx].M;
    return ;
  }

  lazy(idx);
  fin(l,(l+r)/2,idx*2);
  fin((l+r)/2+1,r,idx*2+1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
  for(int i=0;i<k;i++)
    up(0,n-1,1,op[i],height[i],left[i],right[i]);

  fin(0,n-1,1);
  for(int i=0;i<n;i++)
  finalHeight[i]=ans[i];
 
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 141128 KB Output is correct
2 Correct 49 ms 141296 KB Output is correct
3 Correct 50 ms 141208 KB Output is correct
4 Correct 53 ms 141512 KB Output is correct
5 Correct 55 ms 141424 KB Output is correct
6 Correct 55 ms 141540 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 141124 KB Output is correct
2 Correct 162 ms 149316 KB Output is correct
3 Correct 175 ms 145028 KB Output is correct
4 Correct 400 ms 150712 KB Output is correct
5 Correct 270 ms 151216 KB Output is correct
6 Correct 261 ms 151220 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 141188 KB Output is correct
2 Correct 52 ms 141264 KB Output is correct
3 Correct 61 ms 141152 KB Output is correct
4 Correct 55 ms 141496 KB Output is correct
5 Correct 54 ms 141496 KB Output is correct
6 Correct 54 ms 141460 KB Output is correct
7 Correct 53 ms 141196 KB Output is correct
8 Correct 147 ms 149408 KB Output is correct
9 Correct 169 ms 145032 KB Output is correct
10 Correct 480 ms 150708 KB Output is correct
11 Correct 259 ms 151244 KB Output is correct
12 Correct 278 ms 151244 KB Output is correct
13 Correct 49 ms 141128 KB Output is correct
14 Correct 149 ms 149396 KB Output is correct
15 Correct 69 ms 142268 KB Output is correct
16 Correct 408 ms 150960 KB Output is correct
17 Correct 259 ms 150964 KB Output is correct
18 Correct 260 ms 151020 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 141132 KB Output is correct
2 Correct 52 ms 141312 KB Output is correct
3 Correct 52 ms 141192 KB Output is correct
4 Correct 55 ms 141408 KB Output is correct
5 Correct 54 ms 141516 KB Output is correct
6 Correct 55 ms 141500 KB Output is correct
7 Correct 52 ms 141176 KB Output is correct
8 Correct 169 ms 149420 KB Output is correct
9 Correct 183 ms 145100 KB Output is correct
10 Correct 386 ms 150708 KB Output is correct
11 Correct 305 ms 151220 KB Output is correct
12 Correct 265 ms 151204 KB Output is correct
13 Correct 52 ms 141192 KB Output is correct
14 Correct 150 ms 149420 KB Output is correct
15 Correct 71 ms 142284 KB Output is correct
16 Correct 427 ms 150960 KB Output is correct
17 Correct 352 ms 150964 KB Output is correct
18 Correct 261 ms 151020 KB Output is correct
19 Correct 543 ms 193108 KB Output is correct
20 Correct 539 ms 190760 KB Output is correct
21 Correct 543 ms 193340 KB Output is correct
22 Correct 542 ms 190760 KB Output is correct
23 Correct 539 ms 190664 KB Output is correct
24 Correct 594 ms 190640 KB Output is correct
25 Correct 534 ms 190728 KB Output is correct
26 Correct 566 ms 193172 KB Output is correct
27 Correct 561 ms 193248 KB Output is correct
28 Correct 538 ms 190708 KB Output is correct
29 Correct 580 ms 190712 KB Output is correct
30 Correct 556 ms 190644 KB Output is correct