oj.uz

Submission #782681

# Submission time Handle Problem Language Result Execution time Memory
782681 2023-07-14T07:31:38 Z Trumling Wall (IOI14_wall) C++14
61 / 100
 559 ms 262144 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[1000000];
node seg[8000000];

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 46 ms 125436 KB Output is correct
2 Correct 47 ms 125592 KB Output is correct
3 Correct 52 ms 125476 KB Output is correct
4 Correct 46 ms 125860 KB Output is correct
5 Correct 48 ms 125932 KB Output is correct
6 Correct 45 ms 125792 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 125532 KB Output is correct
2 Correct 142 ms 139108 KB Output is correct
3 Correct 160 ms 132812 KB Output is correct
4 Correct 391 ms 144308 KB Output is correct
5 Correct 304 ms 145332 KB Output is correct
6 Correct 258 ms 143860 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 125536 KB Output is correct
2 Correct 44 ms 125660 KB Output is correct
3 Correct 44 ms 125516 KB Output is correct
4 Correct 47 ms 125772 KB Output is correct
5 Correct 47 ms 125776 KB Output is correct
6 Correct 48 ms 125804 KB Output is correct
7 Correct 42 ms 125532 KB Output is correct
8 Correct 144 ms 139208 KB Output is correct
9 Correct 186 ms 132772 KB Output is correct
10 Correct 384 ms 144356 KB Output is correct
11 Correct 261 ms 145356 KB Output is correct
12 Correct 285 ms 143784 KB Output is correct
13 Correct 44 ms 125512 KB Output is correct
14 Correct 146 ms 139144 KB Output is correct
15 Correct 64 ms 126796 KB Output is correct
16 Correct 397 ms 144600 KB Output is correct
17 Correct 280 ms 143948 KB Output is correct
18 Correct 264 ms 143976 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 125532 KB Output is correct
2 Correct 49 ms 125780 KB Output is correct
3 Correct 46 ms 125588 KB Output is correct
4 Correct 49 ms 125828 KB Output is correct
5 Correct 48 ms 125792 KB Output is correct
6 Correct 47 ms 125784 KB Output is correct
7 Correct 46 ms 125420 KB Output is correct
8 Correct 144 ms 139128 KB Output is correct
9 Correct 167 ms 132808 KB Output is correct
10 Correct 389 ms 144276 KB Output is correct
11 Correct 263 ms 145336 KB Output is correct
12 Correct 256 ms 143788 KB Output is correct
13 Correct 44 ms 125524 KB Output is correct
14 Correct 146 ms 139088 KB Output is correct
15 Correct 74 ms 126824 KB Output is correct
16 Correct 400 ms 144532 KB Output is correct
17 Correct 264 ms 143964 KB Output is correct
18 Correct 275 ms 143936 KB Output is correct
19 Runtime error 559 ms 262144 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -