oj.uz

Submission #41275

# Submission time Handle Problem Language Result Execution time Memory
41275 2018-02-15T10:25:38 Z SecretAgent007 Wall (IOI14_wall) C++14
100 / 100
 715 ms 262144 KB 
#include<algorithm>
#include<cstdio>
#include "wall.h"
using namespace std;
const int maxn=2000000+5;
const int INF=(1<<30);
int Max[maxn*6],Min[maxn*6];
inline void add(int id,int val)
{
    if(Max[id]==-1) Min[id]=max(Min[id],val);
    else if(val>=Max[id]) Min[id]=val,Max[id]=-1;
    else if(val>=Min[id]) Min[id]=val;
}
inline void remove(int id,int val)
{
    if(Max[id]==-1) Min[id]=min(Min[id],val);
    else if(val<=Min[id]) Min[id]=val,Max[id]=-1;
    else if(val<=Max[id]) Max[id]=val;
}
inline void push(int id)
{
    if(Max[id]==-1)
    {
        Max[id*2]=Max[id*2+1]=-1;
        Min[id*2]=Min[id*2+1]=Min[id];
        Max[id]=INF,Min[id]=0;
        return;
    }
    if(Min[id]!=0) { add(id*2,Min[id]); add(id*2+1,Min[id]);}
    if(Max[id]!=INF) { remove(id*2,Max[id]); remove(id*2+1,Max[id]); }
    Max[id]=INF,Min[id]=0;
}
void modify(int id,int L,int R,int qL,int qR,int qtype,int qhei)
{
    if(qL<= L && R <=qR)
    {
        if(qtype==1) add(id,qhei); 
        else remove(id,qhei);
        return;
    }
    int M=L+(R-L)/2;
    push(id);
    if(qL<=M) modify(id*2,L,M,qL,qR,qtype,qhei);
    if(qR> M) modify(id*2+1,M+1,R,qL,qR,qtype,qhei);
}
void buildans(int id,int L,int R,int* ans)
{
    if(L==R) {ans[L]=Min[id];return;}
    int M=L+(R-L)/2;
    push(id);
    buildans(id*2,L,M,ans);
    buildans(id*2+1,M+1,R,ans);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
    for(int i=0;i<n*3;i++) Max[i]=INF,Min[i]=0;
    for(int i=0;i<k;i++) modify(1,0,n-1,left[i],right[i],op[i],height[i]);
    buildans(1,0,n-1,finalHeight);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 3 ms 480 KB Output is correct
3 Correct 3 ms 480 KB Output is correct
4 Correct 7 ms 824 KB Output is correct
5 Correct 6 ms 1008 KB Output is correct
6 Correct 7 ms 1028 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1028 KB Output is correct
2 Correct 192 ms 8440 KB Output is correct
3 Correct 219 ms 8440 KB Output is correct
4 Correct 627 ms 11360 KB Output is correct
5 Correct 307 ms 22160 KB Output is correct
6 Correct 284 ms 30720 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 30720 KB Output is correct
2 Correct 3 ms 30720 KB Output is correct
3 Correct 3 ms 30720 KB Output is correct
4 Correct 7 ms 30720 KB Output is correct
5 Correct 7 ms 30720 KB Output is correct
6 Correct 6 ms 30720 KB Output is correct
7 Correct 2 ms 30720 KB Output is correct
8 Correct 187 ms 30720 KB Output is correct
9 Correct 232 ms 30720 KB Output is correct
10 Correct 628 ms 30720 KB Output is correct
11 Correct 321 ms 40896 KB Output is correct
12 Correct 275 ms 49644 KB Output is correct
13 Correct 2 ms 49644 KB Output is correct
14 Correct 192 ms 51868 KB Output is correct
15 Correct 33 ms 51868 KB Output is correct
16 Correct 552 ms 65280 KB Output is correct
17 Correct 294 ms 74432 KB Output is correct
18 Correct 305 ms 83312 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 83312 KB Output is correct
2 Correct 3 ms 83312 KB Output is correct
3 Correct 3 ms 83312 KB Output is correct
4 Correct 7 ms 83312 KB Output is correct
5 Correct 6 ms 83312 KB Output is correct
6 Correct 6 ms 83312 KB Output is correct
7 Correct 1 ms 83312 KB Output is correct
8 Correct 194 ms 83312 KB Output is correct
9 Correct 212 ms 83312 KB Output is correct
10 Correct 620 ms 83312 KB Output is correct
11 Correct 310 ms 93856 KB Output is correct
12 Correct 264 ms 102432 KB Output is correct
13 Correct 2 ms 102432 KB Output is correct
14 Correct 199 ms 104800 KB Output is correct
15 Correct 38 ms 104800 KB Output is correct
16 Correct 520 ms 118340 KB Output is correct
17 Correct 294 ms 127416 KB Output is correct
18 Correct 281 ms 136320 KB Output is correct
19 Correct 668 ms 208528 KB Output is correct
20 Correct 715 ms 216524 KB Output is correct
21 Correct 711 ms 229436 KB Output is correct
22 Correct 672 ms 237348 KB Output is correct
23 Correct 708 ms 247828 KB Output is correct
24 Correct 673 ms 258248 KB Output is correct
25 Correct 702 ms 262144 KB Output is correct
26 Correct 667 ms 262144 KB Output is correct
27 Correct 688 ms 262144 KB Output is correct
28 Correct 707 ms 262144 KB Output is correct
29 Correct 673 ms 262144 KB Output is correct
30 Correct 702 ms 262144 KB Output is correct