oj.uz

Submission #308195

# Submission time Handle Problem Language Result Execution time Memory
308195 2020-09-30T09:00:06 Z daniel920712 Wall (IOI14_wall) C++14
100 / 100
 1667 ms 171384 KB 
#include "wall.h"
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <assert.h>
using namespace std;
int all[1000005]={0};
struct A
{
    int l,r;
    int nxl,nxr;
    int big;
    int small;

    //int bbig1
    //int ssmall;
    int which;
    int last;
    int ok;
}Node[8000005];
int now=1;
vector < int > tt;
void build(int l,int r,int here)
{
    Node[here].l=l;
    Node[here].r=r;
    Node[here].small=0;
    Node[here].big=0;
    Node[here].last=1;
    Node[here].ok=0;
    if(l==r)
    {
        Node[here].which=0;
        return ;
    }
    Node[here].nxl=now++;
    Node[here].nxr=now++;
    build(l,(l+r)/2,Node[here].nxl);
    build((l+r)/2+1,r,Node[here].nxr);
}
void UPD(int here)
{
    if(Node[here].last==1)
    {
        if(Node[Node[here].nxl].big>Node[here].big)
        {
            Node[Node[here].nxl].big=Node[here].big;
            Node[Node[here].nxl].last=2;
        }
        if(Node[Node[here].nxl].small<Node[here].small)
        {
            Node[Node[here].nxl].small=Node[here].small;
            Node[Node[here].nxl].last=1;
        }
        if(Node[Node[here].nxl].small>Node[Node[here].nxl].big)
        {
            if(Node[Node[here].nxl].last==1) Node[Node[here].nxl].big=Node[Node[here].nxl].small;
            else Node[Node[here].nxl].small=Node[Node[here].nxl].big;
            //Node[Node[here].nxl].last=1;
        }

        if(Node[Node[here].nxr].big>Node[here].big)
        {
            Node[Node[here].nxr].big=Node[here].big;
            Node[Node[here].nxr].last=2;
        }
        if(Node[Node[here].nxr].small<Node[here].small)
        {
            Node[Node[here].nxr].small=Node[here].small;
            Node[Node[here].nxr].last=1;
        }
        if(Node[Node[here].nxr].small>Node[Node[here].nxr].big)
        {
            if(Node[Node[here].nxr].last==1) Node[Node[here].nxr].big=Node[Node[here].nxr].small;
            else Node[Node[here].nxr].small=Node[Node[here].nxr].big;
        }
    }
    else
    {
        if(Node[Node[here].nxl].small<Node[here].small)
        {
            Node[Node[here].nxl].small=Node[here].small;
            Node[Node[here].nxl].last=1;
        }
        if(Node[Node[here].nxl].big>Node[here].big)
        {
            Node[Node[here].nxl].big=Node[here].big;
            Node[Node[here].nxl].last=2;
        }
        if(Node[Node[here].nxl].small>Node[Node[here].nxl].big)
        {
            if(Node[Node[here].nxl].last==1) Node[Node[here].nxl].big=Node[Node[here].nxl].small;
            else Node[Node[here].nxl].small=Node[Node[here].nxl].big;
        }

        if(Node[Node[here].nxr].small<Node[here].small)
        {
            Node[Node[here].nxr].small=Node[here].small;
            Node[Node[here].nxr].last=1;
        }
        if(Node[Node[here].nxr].big>Node[here].big)
        {
            Node[Node[here].nxr].big=Node[here].big;
            Node[Node[here].nxr].last=2;
        }
        if(Node[Node[here].nxr].small>Node[Node[here].nxr].big)
        {
            if(Node[Node[here].nxr].last==1) Node[Node[here].nxr].big=Node[Node[here].nxr].small;
            else Node[Node[here].nxr].small=Node[Node[here].nxr].big;
        }
    }
}
int Find(int where,int here)
{
    if(where==Node[here].l&&where==Node[here].r)
    {
        if(Node[here].last==1) return Node[here].small;
        return Node[here].big;
    }
    UPD(here);
    if(where<=(Node[here].l+Node[here].r)/2) return Find(where,Node[here].nxl);
    else return Find(where,Node[here].nxr);
}
void cha(int l,int r,int con,int what,int here)
{
    if(Node[here].l==l&&Node[here].r==r)
    {
        if(what==1)
        {
            if(con>Node[here].small)
            {
                Node[here].small=con;
                Node[here].last=what;

            }
            if(Node[here].small>Node[here].big)
            {
                Node[here].big=Node[here].small;
                Node[here].last=what;
            }
        }
        else
        {
            if(con<Node[here].big)
            {
                Node[here].big=con;
                Node[here].last=what;

            }
            if(Node[here].small>Node[here].big)
            {
                Node[here].small=Node[here].big;
                Node[here].last=what;
            }
        }
        return ;
    }
    UPD(here);
    if(r<=(Node[here].l+Node[here].r)/2) cha(l,r,con,what,Node[here].nxl);
    else if(l>(Node[here].l+Node[here].r)/2) cha(l,r,con,what,Node[here].nxr);
    else
    {
        cha(l,(Node[here].l+Node[here].r)/2,con,what,Node[here].nxl);
        cha((Node[here].l+Node[here].r)/2+1,r,con,what,Node[here].nxr);
    }
    Node[here].big=max(Node[Node[here].nxl].big,Node[Node[here].nxr].big);
    Node[here].small=min(Node[Node[here].nxl].small,Node[Node[here].nxr].small);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    int i,j;
    build(0,n-1,0);
    for(i=0;i<k;i++) cha(left[i],right[i],height[i],op[i],0);

    for(i=0;i<n;i++) finalHeight[i]=Find(i,0);
    return;
}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:172:11: warning: unused variable 'j' [-Wunused-variable]
  172 |     int i,j;
      |           ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 11 ms 1280 KB Output is correct
5 Correct 9 ms 1152 KB Output is correct
6 Correct 9 ms 1152 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 186 ms 8440 KB Output is correct
3 Correct 254 ms 4984 KB Output is correct
4 Correct 800 ms 15900 KB Output is correct
5 Correct 439 ms 20092 KB Output is correct
6 Correct 418 ms 18552 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 11 ms 1280 KB Output is correct
5 Correct 9 ms 1152 KB Output is correct
6 Correct 9 ms 1152 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 175 ms 8188 KB Output is correct
9 Correct 249 ms 4984 KB Output is correct
10 Correct 804 ms 19020 KB Output is correct
11 Correct 432 ms 20216 KB Output is correct
12 Correct 415 ms 18424 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 179 ms 9188 KB Output is correct
15 Correct 51 ms 2680 KB Output is correct
16 Correct 949 ms 19452 KB Output is correct
17 Correct 443 ms 18680 KB Output is correct
18 Correct 435 ms 18680 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 11 ms 1280 KB Output is correct
5 Correct 9 ms 1152 KB Output is correct
6 Correct 9 ms 1152 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 173 ms 8184 KB Output is correct
9 Correct 242 ms 4984 KB Output is correct
10 Correct 784 ms 19012 KB Output is correct
11 Correct 435 ms 20216 KB Output is correct
12 Correct 411 ms 18424 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 179 ms 9084 KB Output is correct
15 Correct 51 ms 2808 KB Output is correct
16 Correct 951 ms 19320 KB Output is correct
17 Correct 433 ms 18680 KB Output is correct
18 Correct 430 ms 18680 KB Output is correct
19 Correct 1636 ms 171384 KB Output is correct
20 Correct 1633 ms 168808 KB Output is correct
21 Correct 1667 ms 171236 KB Output is correct
22 Correct 1629 ms 168952 KB Output is correct
23 Correct 1622 ms 169080 KB Output is correct
24 Correct 1656 ms 168952 KB Output is correct
25 Correct 1646 ms 168824 KB Output is correct
26 Correct 1650 ms 171256 KB Output is correct
27 Correct 1654 ms 171384 KB Output is correct
28 Correct 1632 ms 168824 KB Output is correct
29 Correct 1644 ms 168980 KB Output is correct
30 Correct 1627 ms 168824 KB Output is correct