oj.uz

Submission #238823

# Submission time Handle Problem Language Result Execution time Memory
238823 2020-06-13T05:37:22 Z Autoratch Wall (IOI14_wall) C++14
100 / 100
 1175 ms 89976 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 1 << 21;

int val[N << 1],mn[N << 1],mx[N << 1];
int an[N];

void pushlz(int l,int r,int idx)
{
    if(l==r) val[idx] = max(val[idx],mn[idx]),val[idx] = min(val[idx],mx[idx]);
    else
    {
        mn[idx*2] = max(mn[idx*2],mn[idx]),mx[idx*2] = max(mx[idx*2],mn[idx]);
        mn[idx*2+1] = max(mn[idx*2+1],mn[idx]),mx[idx*2+1] = max(mx[idx*2+1],mn[idx]);
        mx[idx*2] = min(mx[idx*2],mx[idx]),mn[idx*2] = min(mn[idx*2],mx[idx]);
        mx[idx*2+1] = min(mx[idx*2+1],mx[idx]),mn[idx*2+1] = min(mn[idx*2+1],mx[idx]);
    }
    mn[idx] = INT_MIN,mx[idx] = INT_MAX;
}

void build(int l,int r,int idx)
{
    mn[idx] = INT_MIN,mx[idx] = INT_MAX;
    if(l==r) return;
    int m = (l+r)/2;
    build(l,m,idx*2),build(m+1,r,idx*2+1);
}

void update(int l,int r,int idx,int t,int x,int y,int k)
{
    pushlz(l,r,idx);
    if(x>r or y<l) return;
    if(x<=l and y>=r)
    {
        if(t==1) mn[idx] = k;
        else mx[idx] = k;
        pushlz(l,r,idx);
        return;
    }
    int m = (l+r)/2;
    update(l,m,idx*2,t,x,y,k),update(m+1,r,idx*2+1,t,x,y,k);
}

void push(int l,int r,int idx)
{
    pushlz(l,r,idx);
    if(l==r) return void(an[l] = val[idx]);
    int m = (l+r)/2;
    push(l,m,idx*2),push(m+1,r,idx*2+1);
}

void buildWall(int n,int k,int o[],int l[],int r[],int h[],int ans[])
{   
    build(1,n,1);
    for(int i = 0;i < k;i++) update(1,n,1,o[i],l[i]+1,r[i]+1,h[i]);
    push(1,n,1);
    for(int i = 1;i <= n;i++) ans[i-1] = an[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 13 ms 896 KB Output is correct
5 Correct 11 ms 1024 KB Output is correct
6 Correct 12 ms 960 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 178 ms 8184 KB Output is correct
3 Correct 252 ms 4472 KB Output is correct
4 Correct 762 ms 21624 KB Output is correct
5 Correct 465 ms 22776 KB Output is correct
6 Correct 457 ms 21268 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 14 ms 896 KB Output is correct
5 Correct 13 ms 1024 KB Output is correct
6 Correct 12 ms 1024 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 181 ms 13944 KB Output is correct
9 Correct 268 ms 8312 KB Output is correct
10 Correct 728 ms 21624 KB Output is correct
11 Correct 464 ms 22776 KB Output is correct
12 Correct 441 ms 21216 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 180 ms 14072 KB Output is correct
15 Correct 45 ms 2296 KB Output is correct
16 Correct 739 ms 21932 KB Output is correct
17 Correct 455 ms 21368 KB Output is correct
18 Correct 436 ms 21240 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 416 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 12 ms 896 KB Output is correct
5 Correct 11 ms 1024 KB Output is correct
6 Correct 12 ms 1024 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 185 ms 14072 KB Output is correct
9 Correct 255 ms 8360 KB Output is correct
10 Correct 764 ms 21632 KB Output is correct
11 Correct 457 ms 22648 KB Output is correct
12 Correct 475 ms 21112 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 181 ms 14072 KB Output is correct
15 Correct 45 ms 2296 KB Output is correct
16 Correct 907 ms 21896 KB Output is correct
17 Correct 449 ms 21488 KB Output is correct
18 Correct 457 ms 21368 KB Output is correct
19 Correct 1148 ms 89844 KB Output is correct
20 Correct 1173 ms 87244 KB Output is correct
21 Correct 1172 ms 89976 KB Output is correct
22 Correct 1163 ms 87256 KB Output is correct
23 Correct 1149 ms 87288 KB Output is correct
24 Correct 1158 ms 87372 KB Output is correct
25 Correct 1162 ms 87196 KB Output is correct
26 Correct 1175 ms 89848 KB Output is correct
27 Correct 1143 ms 89848 KB Output is correct
28 Correct 1139 ms 87332 KB Output is correct
29 Correct 1129 ms 87288 KB Output is correct
30 Correct 1142 ms 87376 KB Output is correct