oj.uz

Submission #202549

# Submission time Handle Problem Language Result Execution time Memory
202549 2020-02-17T01:13:44 Z DavidDamian Wall (IOI14_wall) C++11
32 / 100
 3000 ms 21880 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int segm_tree[5000000];
int leftNode(int i)
{
    return i*2;
}
int rightNode(int i)
{
    return i*2+1;
}
void recompute(int i)
{
    segm_tree[i]=max(segm_tree[leftNode(i)],segm_tree[rightNode(i)]);
}
struct ura
{
    int type;
    int var1;
    int var2;
} lazy[5000000];
#define a 1 //Add
#define r 2 //Remove
#define c 3 //Change
#define b 4 //Bound
void propagate(int i,int L,int R)
{
    int mid=(L+R)/2;
    if(lazy[i].type==0) return;
    if(lazy[i].type==a) segm_tree[i]=max(segm_tree[i],lazy[i].var1);
    if(lazy[i].type==r) segm_tree[i]=min(segm_tree[i],lazy[i].var1);
    if(L<R){
        if(lazy[i].type!=lazy[leftNode(i)].type) {
            propagate(leftNode(i),L,mid);
            lazy[leftNode(i)]=lazy[i];
        }
        else{
            if(lazy[i].type==a){
                lazy[leftNode(i)].var1=max(lazy[leftNode(i)].var1,lazy[i].var1);
            }
            else{
                lazy[leftNode(i)].var1=min(lazy[leftNode(i)].var1,lazy[i].var1);
            }
        }
        if(lazy[i].type!=lazy[rightNode(i)].type) {
            propagate(rightNode(i),mid+1,R);
            lazy[rightNode(i)]=lazy[i];
        }
        else{
            if(lazy[i].type==a){
                lazy[rightNode(i)].var1=max(lazy[rightNode(i)].var1,lazy[i].var1);
            }
            else{
                lazy[rightNode(i)].var1=min(lazy[rightNode(i)].var1,lazy[i].var1);
            }
        }
    }
    lazy[i].type=0;
}
void update(int i,int L,int R,int x,int y,int type,int h)
{
    propagate(i,L,R);
    if(x<=L && R<=y)
        lazy[i].type=type,lazy[i].var1=h;
    else{
        int mid=(L+R)/2;
        if(x<=mid)
            update(leftNode(i),L,mid,x,y,type,h);
        if(mid+1<=y)
            update(rightNode(i),mid+1,R,x,y,type,h);
        propagate(leftNode(i),L,mid);
        propagate(rightNode(i),mid+1,R);
        recompute(i);
    }
}
int query(int i,int L,int R,int x)
{
    propagate(i,L,R);
    if(L==R){
        return segm_tree[i];
    }
    else{
        int mid=(L+R)/2;
        if(x<=mid)
            return query(leftNode(i),L,mid,x);
        else
            return query(rightNode(i),mid+1,R,x);
    }
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    if(k<=5001){
        for(int i=0;i<k;i++){
            for(int j=left[i];j<=right[i];j++){
                if(op[i]==1){
                    finalHeight[j]=max(finalHeight[j],height[i]);
                }
                else{
                    finalHeight[j]=min(finalHeight[j],height[i]);
                }
            }
        }
        return;
    }
    for(int i=0;i<k;i++){
        update(1,1,n,left[i]+1,right[i]+1,op[i],height[i]);
    }
    for(int i=0;i<n;i++){
        finalHeight[i]=query(1,1,n,i+1);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 28 ms 508 KB Output is correct
5 Correct 28 ms 504 KB Output is correct
6 Correct 28 ms 632 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 183 ms 8568 KB Output is correct
3 Correct 400 ms 5352 KB Output is correct
4 Correct 1151 ms 13864 KB Output is correct
5 Correct 445 ms 14072 KB Output is correct
6 Correct 409 ms 14072 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 28 ms 632 KB Output is correct
5 Correct 28 ms 628 KB Output is correct
6 Correct 28 ms 632 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 184 ms 8824 KB Output is correct
9 Correct 380 ms 5368 KB Output is correct
10 Correct 1157 ms 17272 KB Output is correct
11 Execution timed out 146 ms 12572 KB Time limit exceeded (wall clock)
12 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 30 ms 504 KB Output is correct
5 Correct 28 ms 504 KB Output is correct
6 Correct 28 ms 504 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 182 ms 8824 KB Output is correct
9 Correct 386 ms 5368 KB Output is correct
10 Correct 1167 ms 14008 KB Output is correct
11 Correct 437 ms 14072 KB Output is correct
12 Correct 423 ms 14200 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 181 ms 8824 KB Output is correct
15 Correct 1331 ms 2552 KB Output is correct
16 Execution timed out 3082 ms 21880 KB Time limit exceeded
17 Halted 0 ms 0 KB -