oj.uz

Submission #697226

# Submission time Handle Problem Language Result Execution time Memory
697226 2023-02-09T00:00:12 Z ToroTN Wall (IOI14_wall) C++14
100 / 100
 803 ms 103288 KB 
#include<bits/stdc++.h>
using namespace std;
#define X first 
#define Y second
#define mp make_pair
#include "wall.h"
pair<int,int> lz[8000005],seg[8000005];
int ans[2000005];
pair<int,int> merge(pair<int,int> lz1,pair<int,int> lz2)
{
    if(lz2.X>lz1.Y)return mp(lz2.X,lz2.X);
    if(lz2.Y<lz1.X)return mp(lz2.Y,lz2.Y);
    return mp(max(lz1.X,lz2.X),min(lz1.Y,lz2.Y));
}
void update(int tree,int st,int ed,int l,int r,int x,int y)
{
    int md=(st+ed)/2;
    if(st>=l&&ed<=r)
    {
        lz[tree]=merge(lz[tree],mp(x,y));
    }
    if(st!=ed)
    {
        lz[2*tree]=merge(lz[2*tree],lz[tree]);
        lz[2*tree+1]=merge(lz[2*tree+1],lz[tree]);
    }
    seg[tree]=merge(seg[tree],lz[tree]);
    lz[tree].X=0,lz[tree].Y=1e9;
    if(st>r||ed<l)return;
    if(st>=l&&ed<=r)return;
    update(2*tree,st,md,l,r,x,y);
    update(2*tree+1,md+1,ed,l,r,x,y);
}
void dfs(int tree,int st,int ed)
{
    int md=(st+ed)/2;
    if(st!=ed)
    {
        lz[2*tree]=merge(lz[2*tree],lz[tree]);
        lz[2*tree+1]=merge(lz[2*tree+1],lz[tree]);
    }
    seg[tree]=merge(seg[tree],lz[tree]);
    lz[tree].X=0,lz[tree].Y=1e9;
    if(st==ed)
    {
        ans[st]=seg[tree].X;
        return;
    }
    dfs(2*tree,st,md);
    dfs(2*tree+1,md+1,ed);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for(int i=0;i<=2000000;i++)lz[i].X=0,lz[i].Y=1e9,seg[i].X=0,seg[i].Y=0;
    for(int i=0;i<k;i++)
    {
        left[i]+=1,right[i]+=1;
        if(op[i]==1)
        {
            update(1,1,n,left[i],right[i],height[i],1e9);
        }else
        {
            update(1,1,n,left[i],right[i],0,height[i]);
        }
    }
    dfs(1,1,n);
    for(int i=0;i<n;i++)finalHeight[i]=ans[i+1];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31536 KB Output is correct
2 Correct 17 ms 31692 KB Output is correct
3 Correct 16 ms 31688 KB Output is correct
4 Correct 21 ms 31828 KB Output is correct
5 Correct 20 ms 31896 KB Output is correct
6 Correct 20 ms 31828 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31552 KB Output is correct
2 Correct 142 ms 39780 KB Output is correct
3 Correct 195 ms 35520 KB Output is correct
4 Correct 563 ms 44404 KB Output is correct
5 Correct 329 ms 44836 KB Output is correct
6 Correct 346 ms 44876 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31572 KB Output is correct
2 Correct 17 ms 31700 KB Output is correct
3 Correct 16 ms 31572 KB Output is correct
4 Correct 26 ms 31824 KB Output is correct
5 Correct 19 ms 31828 KB Output is correct
6 Correct 20 ms 31908 KB Output is correct
7 Correct 14 ms 31572 KB Output is correct
8 Correct 148 ms 43356 KB Output is correct
9 Correct 197 ms 38848 KB Output is correct
10 Correct 558 ms 44324 KB Output is correct
11 Correct 340 ms 44836 KB Output is correct
12 Correct 388 ms 44876 KB Output is correct
13 Correct 14 ms 31572 KB Output is correct
14 Correct 147 ms 43320 KB Output is correct
15 Correct 52 ms 32844 KB Output is correct
16 Correct 724 ms 44716 KB Output is correct
17 Correct 350 ms 44460 KB Output is correct
18 Correct 387 ms 44456 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31540 KB Output is correct
2 Correct 15 ms 31696 KB Output is correct
3 Correct 17 ms 31572 KB Output is correct
4 Correct 24 ms 31880 KB Output is correct
5 Correct 20 ms 31932 KB Output is correct
6 Correct 19 ms 31820 KB Output is correct
7 Correct 19 ms 31576 KB Output is correct
8 Correct 154 ms 43236 KB Output is correct
9 Correct 189 ms 38860 KB Output is correct
10 Correct 528 ms 44072 KB Output is correct
11 Correct 324 ms 44636 KB Output is correct
12 Correct 320 ms 44584 KB Output is correct
13 Correct 14 ms 31572 KB Output is correct
14 Correct 148 ms 43176 KB Output is correct
15 Correct 55 ms 32804 KB Output is correct
16 Correct 736 ms 44508 KB Output is correct
17 Correct 341 ms 44412 KB Output is correct
18 Correct 357 ms 44428 KB Output is correct
19 Correct 756 ms 103160 KB Output is correct
20 Correct 789 ms 100900 KB Output is correct
21 Correct 756 ms 103288 KB Output is correct
22 Correct 742 ms 100380 KB Output is correct
23 Correct 800 ms 100336 KB Output is correct
24 Correct 771 ms 100260 KB Output is correct
25 Correct 765 ms 100012 KB Output is correct
26 Correct 736 ms 102016 KB Output is correct
27 Correct 747 ms 101784 KB Output is correct
28 Correct 803 ms 99052 KB Output is correct
29 Correct 788 ms 98776 KB Output is correct
30 Correct 745 ms 98664 KB Output is correct