oj.uz

Submission #7607

# Submission time Handle Problem Language Result Execution time Memory
7607 2014-08-12T13:42:00 Z dohyun0324 Wall (IOI14_wall) C++
100 / 100
 940 ms 49496 KB 
#include "wall.h"
#include<algorithm>
using namespace std;
int c=1;
struct data
{
    int mini,maxi;
}tree[4194400];

void spread(int k)
{
    if(tree[k*2].mini<tree[k].mini)
    {
        tree[k*2].mini=tree[k].mini;
        tree[k*2].maxi=max(tree[k*2].maxi,tree[k*2].mini);
    }
    if(tree[k*2].maxi>tree[k].maxi)
    {
        tree[k*2].maxi=tree[k].maxi;
        tree[k*2].mini=min(tree[k*2].mini,tree[k*2].maxi);
    }
    if(tree[k*2+1].mini<tree[k].mini)
    {
        tree[k*2+1].mini=tree[k].mini;
        tree[k*2+1].maxi=max(tree[k*2+1].maxi,tree[k*2+1].mini);
    }
    if(tree[k*2+1].maxi>tree[k].maxi)
    {
        tree[k*2+1].maxi=tree[k].maxi;
        tree[k*2+1].mini=min(tree[k*2+1].mini,tree[k*2+1].maxi);
    }
}
void Plus(int k,int x,int y,int s,int e,int h)
{
    if(y<s || x>e) return;
    if(x>=s && y<=e)
    {
        tree[k].mini=max(tree[k].mini,h);
        tree[k].maxi=max(tree[k].maxi,tree[k].mini);
        return;
    }
    spread(k);
    Plus(k*2,x,(x+y)/2,s,e,h);
    Plus(k*2+1,(x+y)/2+1,y,s,e,h);
    tree[k].mini=min(tree[k*2].mini,tree[k*2+1].mini);
    tree[k].maxi=max(tree[k*2].maxi,tree[k*2+1].maxi);
}
void Minus(int k,int x,int y,int s,int e,int h)
{
    if(y<s || x>e) return;
    if(x>=s && y<=e)
    {
        tree[k].maxi=min(h,tree[k].maxi);
        tree[k].mini=min(tree[k].mini,tree[k].maxi);
        return;
    }
    spread(k);
    Minus(k*2,x,(x+y)/2,s,e,h);
    Minus(k*2+1,(x+y)/2+1,y,s,e,h);
    tree[k].mini=min(tree[k*2].mini,tree[k*2+1].mini);
    tree[k].maxi=max(tree[k*2].maxi,tree[k*2+1].maxi);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    int i;
    for(i=1;;i++)
    {
        if(c>=n) break;
        c*=2;
    }
    for(i=0;i<k;i++)
    {
        if(op[i]==1) Plus(1,1,c,left[i]+1,right[i]+1,height[i]);
        else Minus(1,1,c,left[i]+1,right[i]+1,height[i]);
    }
    for(i=1;i<c;i++)
    {
        if(i==11)
        {
            i=11;
        }
        spread(i);
    }
    for(i=c;i<=c+n-1;i++)
    {
        finalHeight[i-c]=tree[i].mini;
    }
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33856 KB Output is correct
2 Correct 0 ms 33856 KB Output is correct
3 Correct 0 ms 33856 KB Output is correct
4 Correct 4 ms 33856 KB Output is correct
5 Correct 4 ms 33856 KB Output is correct
6 Correct 4 ms 33856 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33856 KB Output is correct
2 Correct 172 ms 41680 KB Output is correct
3 Correct 216 ms 37104 KB Output is correct
4 Correct 628 ms 42072 KB Output is correct
5 Correct 424 ms 42072 KB Output is correct
6 Correct 404 ms 42072 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33856 KB Output is correct
2 Correct 0 ms 33856 KB Output is correct
3 Correct 0 ms 33856 KB Output is correct
4 Correct 4 ms 33856 KB Output is correct
5 Correct 8 ms 33856 KB Output is correct
6 Correct 4 ms 33856 KB Output is correct
7 Correct 0 ms 33856 KB Output is correct
8 Correct 168 ms 41680 KB Output is correct
9 Correct 228 ms 37104 KB Output is correct
10 Correct 628 ms 42072 KB Output is correct
11 Correct 432 ms 42072 KB Output is correct
12 Correct 416 ms 42072 KB Output is correct
13 Correct 0 ms 33856 KB Output is correct
14 Correct 164 ms 41680 KB Output is correct
15 Correct 36 ms 34340 KB Output is correct
16 Correct 748 ms 42072 KB Output is correct
17 Correct 416 ms 42072 KB Output is correct
18 Correct 416 ms 42072 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33856 KB Output is correct
2 Correct 0 ms 33856 KB Output is correct
3 Correct 0 ms 33856 KB Output is correct
4 Correct 8 ms 33856 KB Output is correct
5 Correct 4 ms 33856 KB Output is correct
6 Correct 4 ms 33856 KB Output is correct
7 Correct 0 ms 33856 KB Output is correct
8 Correct 192 ms 41680 KB Output is correct
9 Correct 220 ms 37104 KB Output is correct
10 Correct 652 ms 42072 KB Output is correct
11 Correct 412 ms 42072 KB Output is correct
12 Correct 420 ms 42072 KB Output is correct
13 Correct 0 ms 33856 KB Output is correct
14 Correct 184 ms 41680 KB Output is correct
15 Correct 36 ms 34340 KB Output is correct
16 Correct 752 ms 42072 KB Output is correct
17 Correct 420 ms 42072 KB Output is correct
18 Correct 432 ms 42072 KB Output is correct
19 Correct 908 ms 49496 KB Output is correct
20 Correct 904 ms 49496 KB Output is correct
21 Correct 924 ms 49496 KB Output is correct
22 Correct 924 ms 49496 KB Output is correct
23 Correct 928 ms 49496 KB Output is correct
24 Correct 928 ms 49496 KB Output is correct
25 Correct 912 ms 49496 KB Output is correct
26 Correct 936 ms 49496 KB Output is correct
27 Correct 896 ms 49496 KB Output is correct
28 Correct 932 ms 49496 KB Output is correct
29 Correct 940 ms 49496 KB Output is correct
30 Correct 928 ms 49496 KB Output is correct