oj.uz

Submission #277046

# Submission time Handle Problem Language Result Execution time Memory
277046 2020-08-21T02:02:22 Z daniel920712 Wall (IOI14_wall) C++14
0 / 100
 3000 ms 8184 KB 
#include "wall.h"
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
int all[1000005]={0};
struct A
{
    int l,r;
    int nxl,nxr;
    int big;
    int small;
    int which;
    int last;
    int ok;
}Node[4000005];
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].ok) return;
    Node[here].ok=0;
    Node[Node[here].nxl].ok=1;
    Node[Node[here].nxr].ok=1;
    Node[Node[here].nxl].big=min(Node[here].big,Node[Node[here].nxl].big);
    Node[Node[here].nxl].small=max(Node[here].small,Node[Node[here].nxl].small);
    Node[Node[here].nxl].last=Node[here].last;
    if(Node[Node[here].nxl].small>Node[Node[here].nxl].big)
    {
        if(Node[here].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].nxr].big=min(Node[here].big,Node[Node[here].nxr].big);
    Node[Node[here].nxr].small=max(Node[here].small,Node[Node[here].nxr].small);
    Node[Node[here].nxr].last=Node[here].last;
    if(Node[Node[here].nxr].small>Node[Node[here].nxr].big)
    {
        if(Node[here].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)
    {
        //printf("%d %d %d\n",where,Node[here].big,Node[here].small);
        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)
    {
        Node[here].last=what;
        Node[here].ok=1;
        if(what==1)
        {
            Node[here].small=max(Node[here].small,con);
            if(Node[here].small>Node[here].big) Node[here].big=Node[here].small;
        }
        else
        {
            Node[here].big=min(Node[here].big,con);
            if(Node[here].small>Node[here].big) Node[here].small=Node[here].big;
        }
        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(j=0;j<n;j++) tt.push_back(Find(j,0));
        //printf("\n");
        for(j=0;j<n;j++) Find(j,0);
        //for(auto i:tt) printf("%d ",i);
        //printf("\n");
        //tt.clear();

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

Subtask #1
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 31 ms 384 KB Output is correct
4 Execution timed out 3056 ms 1280 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 173 ms 8184 KB Output is correct
3 Execution timed out 3060 ms 4856 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.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 34 ms 384 KB Output is correct
4 Execution timed out 3055 ms 1280 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
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 32 ms 428 KB Output is correct
4 Execution timed out 3031 ms 1280 KB Time limit exceeded
5 Halted 0 ms 0 KB -