oj.uz

Submission #430788

# Submission time Handle Problem Language Result Execution time Memory
430788 2021-06-17T05:06:44 Z TLP39 Wall (IOI14_wall) C++14
100 / 100
 835 ms 85636 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int INF=1000000000;

struct func{
    int l,r;
};

func compose(func f,func g)
{
    if(f.r<=g.l) return {g.l,g.l};
    if(f.l>=g.r) return {g.r,g.r};
    return {max(f.l,g.l),min(f.r,g.r)};
}

int n,k;

func seg[8000010];
bool marked[8000010],bottom[8000010];
int pos[2000010];

void build(int v,int st,int ed)
{
    marked[v]=false;
    bottom[v]=false;
    seg[v]={-INF,INF};
    if(st==ed)
    {
        pos[st]=v;
        bottom[v]=true;
        return;
    }
    int mid=(st+ed)>>1;
    build(v<<1,st,mid);
    build(1+(v<<1),mid+1,ed);
}

void push_down(int v)
{
    if(!marked[v] || bottom[v]) return;
    marked[v]=false;
    marked[v<<1]=marked[1+(v<<1)]=true;
    seg[v<<1]=compose(seg[v<<1],seg[v]);
    seg[1+(v<<1)]=compose(seg[1+(v<<1)],seg[v]);
    seg[v]={-INF,INF};
}

void upd(int v,int l,int r,int st,int ed,func f)
{
    if(st>ed) return;
    if(l==st && r==ed)
    {
        marked[v]=true;
        seg[v]=compose(seg[v],f);
        return;
    }
    push_down(v);
    int mid=(l+r)>>1;
    upd(v<<1,l,mid,st,min(mid,ed),f);
    upd(1+(v<<1),mid+1,r,max(mid+1,st),ed,f);
}

int que(int x)
{
    int ver=pos[x],res=0;
    while(ver)
    {
        if(res<=seg[ver].l) res=seg[ver].l;
        else if(res>=seg[ver].r) res=seg[ver].r;
        ver>>=1;
    }
    return res;
}

void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
  n=N;
  k=K;
  build(1,0,n-1);
  for(int i=0;i<k;i++)
  {
    if(op[i]==1)
    {
        upd(1,0,n-1,left[i],right[i],{height[i],INF});
    }
    else
    {
        upd(1,0,n-1,left[i],right[i],{-INF,height[i]});
    }
  }
  for(int i=0;i<n;i++) finalHeight[i]=que(i);
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 316 KB Output is correct
4 Correct 7 ms 844 KB Output is correct
5 Correct 5 ms 844 KB Output is correct
6 Correct 5 ms 844 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 171 ms 13980 KB Output is correct
3 Correct 186 ms 8160 KB Output is correct
4 Correct 507 ms 21288 KB Output is correct
5 Correct 296 ms 22476 KB Output is correct
6 Correct 310 ms 20792 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 8 ms 972 KB Output is correct
5 Correct 5 ms 844 KB Output is correct
6 Correct 5 ms 828 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 195 ms 13964 KB Output is correct
9 Correct 183 ms 8136 KB Output is correct
10 Correct 521 ms 21264 KB Output is correct
11 Correct 296 ms 22280 KB Output is correct
12 Correct 344 ms 20756 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 167 ms 13948 KB Output is correct
15 Correct 35 ms 2220 KB Output is correct
16 Correct 683 ms 21584 KB Output is correct
17 Correct 298 ms 20936 KB Output is correct
18 Correct 289 ms 20948 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 844 KB Output is correct
5 Correct 5 ms 844 KB Output is correct
6 Correct 5 ms 844 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 162 ms 14020 KB Output is correct
9 Correct 192 ms 8128 KB Output is correct
10 Correct 531 ms 21308 KB Output is correct
11 Correct 288 ms 22260 KB Output is correct
12 Correct 307 ms 20752 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 172 ms 13920 KB Output is correct
15 Correct 37 ms 2220 KB Output is correct
16 Correct 628 ms 21628 KB Output is correct
17 Correct 285 ms 21000 KB Output is correct
18 Correct 290 ms 20940 KB Output is correct
19 Correct 740 ms 85564 KB Output is correct
20 Correct 770 ms 83144 KB Output is correct
21 Correct 765 ms 85496 KB Output is correct
22 Correct 755 ms 83056 KB Output is correct
23 Correct 835 ms 83092 KB Output is correct
24 Correct 812 ms 82992 KB Output is correct
25 Correct 739 ms 82992 KB Output is correct
26 Correct 738 ms 85636 KB Output is correct
27 Correct 751 ms 85560 KB Output is correct
28 Correct 728 ms 83012 KB Output is correct
29 Correct 741 ms 83060 KB Output is correct
30 Correct 730 ms 83148 KB Output is correct